Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs
From MaRDI portal
Publication:3452835
DOI10.1007/978-3-662-48350-3_60zbMath1466.68059arXiv1501.00721OpenAlexW2295092485MaRDI QIDQ3452835
Kent Quanrud, Sariel Har-Peled
Publication date: 19 November 2015
Published in: Algorithms - ESA 2015 (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1501.00721
Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25) Density (toughness, etc.) (05C42)
Related Items
Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs ⋮ An annotated bibliography on 1-planarity ⋮ Computational complexity for the problem of optimal intersection of straight line segments by disks ⋮ Local search is a PTAS for feedback vertex set in minor-free graphs ⋮ Unnamed Item ⋮ Packing and covering with non-piercing regions ⋮ Lossy Kernels for Connected Dominating Set on Sparse Graphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Parameterized complexity of geometric covering problems having conflicts ⋮ Distributed Dominating Set Approximations beyond Planar Graphs ⋮ Lossy Kernels for Connected Dominating Set on Sparse Graphs ⋮ Sublinear Separators in Intersection Graphs of Convex Shapes ⋮ Finding, hitting and packing cycles in subexponential time on unit disk graphs ⋮ A tight analysis of geometric local search
Cites Work
- Unnamed Item
- Unnamed Item
- Sparsity. Graphs, structures, and algorithms
- Approximation algorithms for maximum independent set of pseudo-disks
- Improved results on geometric hitting set problems
- Improved approximation algorithms for geometric set cover
- Motion planning in environments with low obstacle density
- Diameter and treewidth in minor-closed graph families
- Covering a ball with smaller equal balls in \(\mathbb R^n\)
- The complexity of the free space for motion planning amidst fat obstacles
- Simple PTAS's for families of graphs excluding a minor
- Grad and classes with bounded expansion. I: Decompositions
- Grad and classes with bounded expansion. II: Algorithmic aspects
- Local tree-width, excluded minors, and approximation algorithms
- Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
- A Separator Theorem for Planar Graphs
- Applications of a Planar Separator Theorem
- Approximation algorithms for NP-complete problems on planar graphs
- Separators for sphere-packings and nearest neighbor graphs
- Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs
- Quasi-Polynomial Time Approximation Scheme for Sparse Subsets of Polygons
- Deciding First-Order Properties of Nowhere Dense Graphs
- Polynomial-time approximation schemes for packing and piercing fat objects
- Every planar graph is the intersection graph of segments in the plane
- Small-Size $\eps$-Nets for Axis-Parallel Rectangles and Boxes
- Near-Optimal Separators in String Graphs
- Improved Bounds for the Union of Locally Fat Objects in the Plane
- ON CONVEX POLYHEDRA IN LOBAČEVSKIĬ SPACES
- Faster shortest-path algorithms for planar graphs
