
Algorithm Theory -- SWAT 2012
Description
Alles über E-Books | Antworten auf Fragen rund um E-Books, Kopierschutz und Dateiformate finden Sie in unserem Info- & Hilfebereich.
More details
Other editions
Additional editions

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
System requirements
File format: PDF
Copy protection: Watermark-DRM (Digital Rights Management)
System requirements:
- Computer (Windows; MacOS X; Linux): Use the free software Adobe Reader, Adobe Digital Editions, or any other PDF viewer of your choice (see eBook Help).
- Tablet/Smartphone (Android; iOS): Install the free app Adobe Digital Editions or another reading app for eBooks, e.g., PocketBook (see eBook Help).
- E-reader: Bookeen, Kobo, Pocketbook, Sony, Tolino and many more (only limited: Kindle).
The file format PDF always displays a book page identically on any hardware. This makes PDF suitable for complex layouts such as those used in textbooks and reference books (images, tables, columns, footnotes). Unfortunately, on the small screens of e-readers or smartphones, PDFs are rather annoying, requiring too much scrolling.
This eBook uses Watermark-DRM, a „soft” copy protection. This means that there are no technical restrictions to prevent illegal distribution. However, there is a personalised watermark embedded in the eBook that can be used to identify the purchaser of the eBook in the event of misuse and to provide evidence for legal purposes.
For more information, see our eBook Help page.