Finding, Hitting and Packing Cycles in Subexponential Time on Unit Disk Graphs

DOI10.4230/LIPIcs.ICALP.2017.65zbMath1441.68179arXiv1704.07279OpenAlexW2918931394MaRDI QIDQ5111396

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

Publication date: 27 May 2020

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

zbMATH Keywords

longest cyclefeedback vertex setparameterized complexitycycle packingunit disk graph

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Graph representations (geometric and intersection representations, etc.) (05C62) Parameterized complexity, tractability and kernelization (68Q27)

Related Items (3)

Optimality program in segment and string graphs ⋮ Subexponential algorithms for variants of the homomorphism problem in string graphs ⋮ A Framework for Exponential-Time-Hypothesis--Tight Algorithms and Lower Bounds in Geometric Intersection Graphs

This page was built for publication: Finding, Hitting and Packing Cycles in Subexponential Time on Unit Disk Graphs