Algorithm Theory -- SWAT 2012

Name: Algorithm Theory -- SWAT 2012 | 13th Scandinavian Symposium and Workshops, Helsinki, Finland, July 4-6, 2012, Proceedings
Brand: Springer
Price: 53.49 EUR
Availability: OnlineOnly

13th Scandinavian Symposium and Workshops, Helsinki, Finland, July 4-6, 2012, Proceedings

Fedor V. Fomin Petteri Kaski(Herausgeber*in)

Springer (Verlag)

Erschienen am 13. Juni 2012

XIII, 410 Seiten

E-Book

PDF mit Wasserzeichen-DRM

Systemvoraussetzungen

978-3-642-31155-0 (ISBN)

53,49 €inkl. 7% MwSt.

Systemvoraussetzungen

für PDF mit Wasserzeichen-DRM

E-Book Einzellizenz

Als Download verfügbar

Beschreibung

Weitere Details

Weitere Ausgaben

Inhalt

Title
Preface
Conference Organization
Table of Contents
a-Visibility
Introduction
Preliminaries
Point Visibility
Segment Visibility
One Arbitrary Query Segment
Complete -Visibility
References
Partial Matching between Surfaces Using Fr´echet Distance
Introduction
Preliminaries
Computing a Valid Set of Neighborhoods
Valid Set of Neighborhoods
Algorithm and Runtime Analysis
Computing a Simple Polygon
Theorem 4 and Related Lemmas
Proof of Theorem 4
Future Work
References
A Polynomial-Time Approximation Scheme for the Geometric Unique Coverage Problem on Unit Squares
Introduction
Past Work and Motivation
Contribution of the Paper
Main Result
Algorithm for a Constant Number of Ribbons
Basic Idea of Our Algorithm
Basic Definitions
Properties on Square Subsets of Di
Properties on Square Subsets of D
Algorithm for the Problem on "426830A PG, D "526930B
Budgeted Version
Conclusion
References
Watchman Routes for Lines and Segments
Introduction
The Watchman Route Problem for Lines
Lines in the Plane
The Watchman Route Problem for Lines in 3D
Segments in the Plane
NP-Hardness
Approximation Algorithm
Light Segments
Simple Arrangements
Almost Simple Grids
Concluding Remarks
References
Kinetic Pie Delaunay Graph and Its Applications
Introduction
Pie Delaunay Graph
The Construction of the Pie Delaunay Graph
Kinetic Pie Delaunay Graph
The Applications
The Constructions
Kinetic Yao Graph
Kinetic EMST
Conclusion
References
Higher Order City Voronoi Diagrams
Introduction
Preliminaries
Complexity
Mixed Vertices
Upper Bound
Lower Bound
Algorithms
Iterative Algorithm for kth-Order City Voronoi Diagrams
Divide-and-Conquer Algorithm for Farthest-Site City Voronoi Diagrams
Conclusion
References
On Minimum Sum of Radii and Diameters Clustering
Introduction
Our Results
MSR Restricted to Unweighted Graphs
PTAS for Euclidean MSD
The Exact Algorithm of Gibson-ksum-radiiSIAMJC12 for Euclidean MSR
A PTAS for Euclidean MSD
Concluding Remarks
References
A Simple Framework for the Generalized Nearest Neighbor Problem
Introduction
Our Contribution
Intuitive Idea of Our Approach
Related Work
A Unified Framework for the GNN Problem
The Framework
Solutions for Concrete Query Collections
Query Lines in 3-Dimensional Space under 2-Norm
Query Lines in 3-Dimensional Space under 1-Norm
Previously Considered Query Collections
Comparison with Generalized Voronoi Diagrams
References
Deterministic Parameterized Connected Vertex Cover
Introduction
Algorithm
Iterative Compression
Compression Algorithm
Combinatorial Bound
Bipartite Steiner Tree
Counting
Polynomial Space
Conclusions and Open Problems
References
Faster Parameterized Algorithms for Deletion to Split Graphs
Introduction
Preliminaries
An Improved Algorithm for Split Vertex Deletion
A Cubic Kernel for Split Vertex Deletion
An Improved Algorithm for SED
A Randomized Subexponential Algorithm for SED
Derandomization with Universal Coloring Families
Improved Kernel for SED
Conclusion
References
A Single-Exponential FPT Algorithm for the K4-Minor Cover Problem
Introduction
Notation and Preliminaries
The Algorithm
A Disjoint Protrusion Reduction Rule
Explicit Reduction Rules
Branching Rules
The Algorithm and Its Complexity Analysis
Conclusion and Open Problems
References
An O(n3 log log n/ log2 n) Time Algorithm for All Pairs Shortest Paths
Introduction
Preparation
The Further Details
Combining Words
Removing Another Factor of loglogn from Complexity
References
Linear Time Algorithm for Computing a Small Biclique in Graphs without Long Induced Paths
Introduction
Computing a Small Biclique in a Graph without Long Induced Paths
Proof of Theorem 1
Connecting Structures
Grid Structures with Large Bicliques
Flowers and Bouquets
Proof of Theorem 3
Directions of Future Research
References
Induced Disjoint Paths in AT-Free Graphs
Introduction
Preliminaries
Induced Disjoint Paths
Phase 1: Preprocessing
Phase 2: Obtaining Structural Results
Phase 3: Dynamic Programming
Induced Topological Minors
Concluding Remarks
References
Effective Computation of Immersion Obstructions for Unions of Graph Classes
Introduction
Preliminaries
Basics
Tree-Width and Linkages
Monadic Second Order Logic
Computing Immersion Obstruction Sets
Tree-Width Bounds for the Obstructions
Conclusions and Further Work
References
Algorithms on Minimizing the Maximum Sensor Movement for Barrier Coverage of a Linear Domain
Introduction
Problem Definitions, Previous Work, and Our Results
Related Work
An Overview of Our Approaches
The Decision Version of the General BCLS
The Algorithm Description
The Algorithm Correctness and Implementation
The Optimization Version of the General BCLS
References
Annotating Simplices with a Homology Basis and Its Applications
Introduction
Background
Efficient Matrix Operations
Annotating Edges
Optimality for 1-Cycles
Shortest Homology Basis
Shortest Homologous Cycle
Annotating p-Simplices
Null Homology and Independence
Conclusions
References
Do Directional Antennas Facilitate in Reducing Interferences?
Introduction
Constant Interference Converge-Cast
Asymmetric Model
Symmetric Model
Interference in 1D
Interference in 2D
Conclusion and Future Work
References
Minimum Convex Partitions and Maximum Empty Polytopes
Introduction
Combinatorial Bounds
Approximating the Minimum Convex Steiner Partition in R2
Approximating the Maximum Empty Convex Body
Handling the Large Volume Case
Finding a Large Empty Convex Polygon
The Higher Dimensional Case
Better Approximations
References
A Probabilistic Analysis of Christofides' Algorithm
Introduction
Preliminaries
Proof of the Main Result
Christofides' Functional
Experimental Evaluation
References
New Approximation Algorithms for the Unsplittable Capacitated Facility Location Problem
Introduction
Related Works
The Main Results and Techniques
Reduction to the Restricted UCFLP
The RUCFLP(12) and RUCFLP(13)
Discussion
References
Non-preemptive Speed Scaling
Introduction
Preliminaries
Special Case: Laminar Family
General Instances
References
A Fast Algorithm for Permutation Pattern Matching Based on Alternating Runs
Introduction
Preliminaries
The Alternating Run Algorithm
W[1]-Hardness for the Parameter run(P)
Future Work
References
Sorted Range Reporting
Introduction
Compact Range Trees
Sorted Reporting in Linear Space
Three-Sided Reporting in Optimal Time
Two-Dimensional Range Reporting in Optimal Time
Applications
Pattern Matching with Variable-Length Don't Cares
Ordered Substring Searching
Maximal Points in a 2D Range and Rectangular Visibility
References
String Indexing for Patterns with Wildcards
Introduction
Preliminaries
The LCP Data Structure
An Unbounded Wildcard Index Using Linear Space
A Time-Space Trade-Off for k-Bounded Wildcard Indexes
A k-Bounded Wildcard Index with Linear Query Time
References
Linear-Space Data Structures for Range Minority Query in Arrays
Introduction
Finding a Least Frequent Element
O(n)-Time Data Structure
Reduction from Boolean Matrix Multiplication
Range Minority
Range Majority
Discussion
References
Asynchronous Rumor Spreading in Preferential Attachment Graphs
Introduction
Precise Model and Preliminaries
Statement of Results
Analysis of the Asynchronous Push-Pull Model
Alternative Model
Useful Nodes
Informing the First Useful Node
Informing Node 1
Conclusion
References
Connectivity Oracles for Planar Graphs
Introduction
Definitions, Notation, and Basic Results
Edge Failures
The Data Structure
Vertex and Edge Failures
Vertex Failures for Triconnected Planar Graphs
The Data Structure
Decremental Subgraph Connectivity
Reductions to Triconnected Graphs
References
Access Graphs Results for LRU versus FIFO under Relative Worst Order Analysis
Introduction
Preliminaries
Paths
Cycles
Separation on a Path of Length k+1
Incomparability
Open Problems
References
Competitive Analysis of Maintaining Frequent Items of a Stream
Introduction
Setting
Organization of the Paper and Results
Worst-Case Bounds
The Classic Majority Algorithm
Weaker Adversarial Models
Lower Bounds for Arbitrary Memory k
Extensions and Future Directions
References
Kernel Bounds for Structural Parameterizations of Pathwidth
Introduction
Preliminaries
Reduction Rules
Vertices of Small Degree
Common Neighbors and Disjoint Paths
Simplicial Vertices
Simplicial Components
Almost Simplicial Vertices
Polynomial Kernelizations
Lower Bounds: Modulator to a Single Clique
Conclusions
References
Kernel Lower BoundsUsing Co-nondeterminism: Finding Induced Hereditary Subgraphs
Introduction
Preliminaries
Co-nondeterminism and Improvement Versions
Kernelization Hardness for Some ?-Induced Subgraph Problems
Polynomial Parameter Transformation from RAMSEY
Conclusion
References
Testing Formula Satisfaction
Introduction
Preliminaries
Formulae, Evaluations and Testing
Basic Formula Simplification and Handling
Observations about Subformulae and Farness
Heavy and Light Children in General Gates
Upper Bound for General Bounded Arity Formula
The Computational Complexity of the Testers and Estimator
References
Reconstructing Strings from Substrings with Quantum Queries
Introduction
Upper Bounds
Basic Ideas and Algorithms
Analysis of MakeOnce
Analysis of Identify
Conclusion
References
Author Index

Systemvoraussetzungen

Als PDF speichern Als Link merken