Contraction Decomposition in Unit Disk Graphs and Algorithmic Applications in Parameterized Complexity

DOI10.1137/1.9781611975482.64zbMath1431.68100OpenAlexW4243701360MaRDI QIDQ5236248

Saket Saurabh, Meirav Zehavi, Fahad Panolan

Publication date: 15 October 2019

Published in: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/1.9781611975482.64

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Graph representations (geometric and intersection representations, etc.) (05C62) Parameterized complexity, tractability and kernelization (68Q27)

Related Items

Unnamed Item ⋮ A sub-exponential FPT algorithm and a polynomial kernel for minimum directed bisection on semicomplete digraphs