Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs
From MaRDI portal
Publication:4593248
DOI10.1137/16M1079336zbMath1375.05197OpenAlexW2951040439MaRDI QIDQ4593248
Kent Quanrud, Sariel Har-Peled
Publication date: 22 November 2017
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/16m1079336
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
Diameter, Eccentricities and Distance Oracle Computations on H-Minor Free Graphs and Graphs of Bounded (Distance) Vapnik–Chervonenkis Dimension ⋮ Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs ⋮ Kernelization and approximation of distance-\(r\) independent sets on nowhere dense graphs ⋮ Maximum matchings in geometric intersection graphs ⋮ Two lower bounds for $p$-centered colorings ⋮ On weighted sublinear separators ⋮ Clique-based separators for geometric intersection graphs ⋮ Geometric dominating-set and set-cover via local-search ⋮ Shallow Minors, Graph Products, and Beyond-Planar Graphs ⋮ An ETH-Tight Exact Algorithm for Euclidean TSP ⋮ Treetopes and their graphs ⋮ Uncertain Measure and its Application in Minimum Weighted Maximal Matching Problem ⋮ Constructing planar support for non-piercing regions ⋮ Greedy domination on biclique-free graphs ⋮ Local Search Yields Approximation Schemes for $k$-Means and $k$-Median in Euclidean and Minor-Free Metrics ⋮ Unnamed Item ⋮ Balanced line separators of unit disk graphs ⋮ A Framework for Exponential-Time-Hypothesis--Tight Algorithms and Lower Bounds in Geometric Intersection Graphs ⋮ Erdös--Hajnal Properties for Powers of Sparse Graphs ⋮ Constant round distributed domination on graph classes with bounded expansion
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Exact algorithms and APX-hardness results for geometric packing and covering problems
- Sparsity. Graphs, structures, and algorithms
- Approximation algorithms for maximum independent set of pseudo-disks
- Improved results on geometric hitting set problems
- Randomized incremental construction of abstract Voronoi diagrams
- Two proofs for shallow packings
- Improved approximation algorithms for geometric set cover
- Improved bounds on the union complexity of fat objects
- Motion planning in environments with low obstacle density
- Diameter and treewidth in minor-closed graph families
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- Which problems have strongly exponential complexity?
- Covering a ball with smaller equal balls in \(\mathbb R^n\)
- The complexity of the free space for motion planning amidst fat obstacles
- Realistic input models for geometric algorithms
- 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
- Strongly Sublinear Separators and Polynomial Expansion
- On the set multicover problem in geometric settings
- Net and Prune
- Approximate Greedy Clustering and Distance Selection for Graph Metrics
- Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs
- Brooks' Theorem and Beyond
- Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
- A Separator Theorem for Planar Graphs
- Applications of a Planar Separator Theorem
- Efficient Planarity Testing
- Approximation algorithms for NP-complete problems on planar graphs
- Separators for sphere-packings and nearest neighbor graphs
- Packing and Covering with Non-Piercing Regions
- 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
- Reducibility among Combinatorial Problems
- Every planar graph is the intersection graph of segments in the plane
- A QPTAS for Maximum Weight Independent Set of Polygons with Polylogarithmically Many Vertices
- 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
- A tight bound on approximating arbitrary metrics by tree metrics
- On the complexity of \(k\)-SAT
