A framework for ETH-tight algorithms and lower bounds in geometric intersection graphs

DOI10.1145/3188745.3188854zbMath1427.68353DBLPconf/stoc/BergBKMZ18arXiv1803.10633OpenAlexW2964067126WikidataQ59567342 ScholiaQ59567342MaRDI QIDQ5230321

Sándor Kisfaludi-Bak, Tom C. van der Zanden, Dániel Marx, Mark T. de Berg, Hans L. Bodlaender

Publication date: 22 August 2019

Published in: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1803.10633

zbMATH Keywords

treewidthgraph minorsgeometric intersection graphsgeometric separatorsubexponential algorithms

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10) Graph minors (05C83) 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 (10)

Lower Bounds for Dominating Set in Ball Graphs and for Weighted Dominating Set in Unit-Ball Graphs ⋮ Reverse shortest path problem for unit-disk graphs ⋮ The homogeneous broadcast problem in narrow and wide strips. I: Algorithms ⋮ The homogeneous broadcast problem in narrow and wide strips. II: Lower bounds ⋮ Grid recognition: classical and parameterized computational perspectives ⋮ Parameterized study of Steiner tree on unit disk graphs ⋮ Near-optimal algorithms for shortest paths in weighted unit-disk graphs ⋮ Unnamed Item ⋮ A Framework for Exponential-Time-Hypothesis--Tight Algorithms and Lower Bounds in Geometric Intersection Graphs ⋮ The fine-grained complexity of multi-dimensional ordering properties

This page was built for publication: A framework for ETH-tight algorithms and lower bounds in geometric intersection graphs