Approximation algorithms for polynomial-expansion and low-density graphs
From MaRDI portal
Density (toughness, etc.) (05C42) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)
Recommendations
Cites work
- A QPTAS for maximum weight independent set of polygons with polylogarithmically many vertices
- A Separator Theorem for Planar Graphs
- A tight bound on approximating arbitrary metrics by tree metrics
- Applications of a Planar Separator Theorem
- Approximate greedy clustering and distance selection for graph metrics
- Approximation algorithms for maximum independent set of pseudo-disks
- Approximation algorithms for NP-complete problems on planar graphs
- Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs
- Approximation algorithms for the 0-extension problem
- Brooks' Theorem and Beyond
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- Computational geometry. Algorithms and applications.
- Covering a ball with smaller equal balls in R^n
- Diameter and treewidth in minor-closed graph families
- Efficient Planarity Testing
- Every planar graph is the intersection graph of segments in the plane (extended abstract)
- Exact algorithms and APX-hardness results for geometric packing and covering problems
- Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
- Fast C-K-R partitions of sparse graphs
- Faster shortest-path algorithms for planar graphs
- Grad and classes with bounded expansion. I: Decompositions
- Grad and classes with bounded expansion. II: Algorithmic aspects
- Graph theory with applications
- scientific article; zbMATH DE number 17662 (Why is no real title available?)
- scientific article; zbMATH DE number 1330033 (Why is no real title available?)
- scientific article; zbMATH DE number 1017008 (Why is no real title available?)
- scientific article; zbMATH DE number 2068110 (Why is no real title available?)
- scientific article; zbMATH DE number 1559563 (Why is no real title available?)
- scientific article; zbMATH DE number 3027510 (Why is no real title available?)
- Improved approximation algorithms for geometric set cover
- Improved bounds for the union of locally fat objects in the plane
- Improved bounds on the union complexity of fat objects
- Improved results on geometric hitting set problems
- Local tree-width, excluded minors, and approximation algorithms
- Motion planning in environments with low obstacle density
- Near-optimal separators in string graphs
- Net and prune: a linear time algorithm for Euclidean distance problems
- ON CONVEX POLYHEDRA IN LOBAČEVSKIĬ SPACES
- On the complexity of k-SAT
- On the set multicover problem in geometric settings
- Packing and covering with non-piercing regions
- Polynomial-time approximation schemes for packing and piercing fat objects
- Quasi-polynomial time approximation scheme for sparse subsets of polygons
- Randomized incremental construction of abstract Voronoi diagrams
- Realistic input models for geometric algorithms
- Reducibility among combinatorial problems
- Separators for sphere-packings and nearest neighbor graphs
- Simple PTAS's for families of graphs excluding a minor
- Small-size -nets for axis-parallel rectangles and boxes
- Sparsity. Graphs, structures, and algorithms
- State of the union (of geometric objects)
- Strongly sublinear separators and polynomial expansion
- The complexity of the free space for motion planning amidst fat obstacles
- Two proofs for shallow packings
- Which problems have strongly exponential complexity?
Cited in
(37)- Greedy domination on biclique-free graphs
- Constant round distributed domination on graph classes with bounded expansion
- Treetopes and their graphs
- Constructing planar support for non-piercing regions
- Kernelization and approximation of distance-r independent sets on nowhere dense graphs
- Two lower bounds for p-centered colorings
- A framework for exponential-time-hypothesis-tight algorithms and lower bounds in geometric intersection graphs
- Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs
- Shifting strategy for geometric graphs without geometry
- Local Search Yields Approximation Schemes for k-Means and k-Median in Euclidean and Minor-Free Metrics
- Uncertain measure and its application in minimum weighted maximal matching problem
- Diameter, eccentricities and distance oracle computations on H-minor free graphs and graphs of bounded (distance) Vapnik-Chervonenkis dimension
- Algorithmic properties of sparse digraphs
- Subexponential parameterized algorithms for graphs of polynomial growth
- Domination in Geometric Intersection Graphs
- Erdös-Hajnal properties for powers of sparse graphs
- Balanced line separators of unit disk graphs
- Maximum matchings in geometric intersection graphs
- 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
- Distributed domination on sparse graph classes
- Sweeping arrangements of non-piercing regions in the plane
- On solution discovery via reconfiguration
- A 1.9999-approximation algorithm for vertex cover on string graphs
- Sweeping arrangements of non-piercing regions in the plane
- Computing diameter+2 in truly-subquadratic time for unit-disk graphs
- A clique-based separator for intersection graphs of geodesic disks in \(\mathbb{R}^2\)
- A clique-based separator for intersection graphs of geodesic disks in \(\mathbb{R}^2\)
- A survey of degree-boundedness
- Greedy spanners in Euclidean spaces admit sublinear separators
- An output-sensitive algorithm for computing the union of cubes and fat boxes in 3D
- Shortest path separators in unit disk graphs
- A WSPD, separator and small tree cover for c-packed graphs
- Strongly sublinear separators and bounded asymptotic dimension for sphere intersection graphs
This page was built for publication: Approximation algorithms for polynomial-expansion and low-density graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4593248)
