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
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)
This page was built for publication: A framework for ETH-tight algorithms and lower bounds in geometric intersection graphs