Algorithm Theory -- SWAT 2012
13th Scandinavian Symposium and Workshops, Helsinki, Finland, July 4-6, 2012, Proceedings
Published on 13. June 2012
XIII, 410 pages
978-3-642-31155-0 (ISBN)
Description
This book constitutes the refereed proceedings of the 13th International Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2012, held in Helsinki, Finland, in July 2012, co-located with the 23rd Annual Symposium on Combinatorial Pattern Matching, CPM 2012. The 34 papers were carefully reviewed and selected from a total of 127 submissions. The papers present original research and cover a wide range of topics in the field of design and analysis of algorithms and data structures.
More details
Other editions
Additional editions
Fedor V. Fomin | Petteri Kaski
Algorithm Theory -- SWAT 2012
13th Scandinavian Symposium and Workshops, Helsinki, Finland, July 4-6, 2012, Proceedings
Book
06/2012
1st Edition
Springer
€53.49
Shipment within 7-9 days
Persons
Content
- 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
