Finding, hitting and packing cycles in subexponential time on unit disk graphs

DOI10.1007/s00454-018-00054-xzbMath1441.68178MaRDI QIDQ2334507

Meirav Zehavi, Fedor V. Fomin, Saket Saurabh, Daniel Lokshtanov, Fahad Panolan

Publication date: 7 November 2019

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2017/7393/

zbMATH Keywords

longest cycle; longest path; feedback vertex set; parameterized complexity; cycle packing; unit disk graph; unit square graph

Mathematics Subject Classification ID

68W40: Analysis of algorithms

68R10: Graph theory (including graph drawing) in computer science

68U05: Computer graphics; computational geometry (digital and algorithmic aspects)

05C62: Graph representations (geometric and intersection representations, etc.)

68Q27: Parameterized complexity, tractability and kernelization

Uses Software

• Algorithm 447