A Framework for Exponential-Time-Hypothesis--Tight Algorithms and Lower Bounds in Geometric Intersection Graphs
DOI10.1137/20M1320870zbMath1497.68375OpenAlexW3112807772WikidataQ115525545 ScholiaQ115525545MaRDI QIDQ3387760
Sándor Kisfaludi-Bak, Tom C. van der Zanden, Dániel Marx, Hans L. Bodlaender, Mark T. de Berg
Publication date: 13 January 2021
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/20m1320870
Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph representations (geometric and intersection representations, etc.) (05C62)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Sphere and dot product representations of graphs
- Theory and application of width bounded geometric separators
- A simplified NP-complete satisfiability problem
- Safe reduction rules for weighted treewidth
- Unit disk graphs
- The NP-completeness of the Hamiltonian cycle problem in planar digraphs with degree bound two
- A partial k-arboretum of graphs with bounded treewidth
- Unit disk graph recognition is NP-hard
- Computing the treewidth and the minimum fill-in with the modular decomposition
- Which problems have strongly exponential complexity?
- The complexity of dominating set in geometric intersection graphs
- Tree decompositions with small cost
- Graph minors. XIII: The disjoint paths problem
- Linear time solvable optimization problems on graphs of bounded clique-width
- Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs
- Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
- Rank-width: algorithmic and structural results
- A $c^k n$ 5-Approximation Algorithm for Treewidth
- Optimal Parameterized Algorithms for Planar Facility Location Problems Using Voronoi Diagrams
- A Separator Theorem for Planar Graphs
- Applications of a Planar Separator Theorem
- Planar Formulae and Their Uses
- The Planar Hamiltonian Circuit Problem is NP-Complete
- Sorting on a mesh-connected parallel computer
- The Rectilinear Steiner Tree Problem is $NP$-Complete
- Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs
- The limited blessing of low dimensionality
- The Pathwidth and Treewidth of Cographs
- Hamilton Paths in Grid Graphs
- Geometric separation and exact solutions for the parameterized independent set problem on disk graphs
- Nearly ETH-tight Algorithms for Planar Steiner Tree with Terminals on Few Faces
- Lower Bounds for Dominating Set in Ball Graphs and for Weighted Dominating Set in Unit-Ball Graphs
- Finding, Hitting and Packing Cycles in Subexponential Time on Unit Disk Graphs
- Contraction-Bidimensionality of Geometric Intersection Graphs
- A framework for ETH-tight algorithms and lower bounds in geometric intersection graphs
- ON THE CLIQUE-WIDTH OF SOME PERFECT GRAPH CLASSES
- On the Exact Complexity of Hamiltonian Cycle and q-Colouring in Disk Graphs
- Improved Bounds for the Union of Locally Fat Objects in the Plane
- Parameterized Algorithms
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
- On the complexity of \(k\)-SAT
- ETH-Tight Algorithms for Long Path and Cycle on Unit Disk Graphs
