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

DOI10.1007/s00454-018-00054-xzbMath1441.68178OpenAlexW2962872430WikidataQ128616642 ScholiaQ128616642MaRDI QIDQ2334507

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

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 cyclelongest pathfeedback vertex setparameterized complexitycycle packingunit disk graphunit square 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

Computing list homomorphisms in geometric intersection graphs ⋮ Faster algorithms for cycle hitting problems on disk graphs ⋮ Parameterized study of Steiner tree on unit disk graphs ⋮ Decomposition of Map Graphs with Applications.

Uses Software

• Algorithm 447

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Minimum clique partition in unit disk graphs
• Improved approximation algorithms for geometric set cover
• Finding paths of length \(k\) in \(O^{*}(2^k)\) time
• On problems without polynomial kernels
• A study on two geometric location problems
• Unit disk graphs
• Which problems have strongly exponential complexity?
• Efficient exact algorithms on planar graphs: Exploiting sphere cut decompositions
• Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
• Narrow sieves for parameterized paths and packings
• Vertex Cover: Further Observations and Further Improvements
• A $c^k n$ 5-Approximation Algorithm for Treewidth
• A 4 k ² kernel for feedback vertex set
• WEIGHTED GEOMETRIC SET COVER PROBLEMS REVISITED
• Efficient Computation of Representative Families with Applications in Parameterized and Exact Algorithms
• Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs
• Mixing Color Coding-Related Techniques
• Subexponential parameterized algorithms on bounded-genus graphs and H -minor-free graphs
• Faster Algebraic Algorithms for Path and Packing Problems
• Polynomial Kernels for Hard Problems on Disk Graphs
• Approximation schemes for covering and packing problems in image processing and VLSI
• Approximation algorithms for NP-complete problems on planar graphs
• Color-coding
• NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs
• Polynomial-time approximation schemes for packing and piercing fat objects
• Bidimensionality and Geometric Graphs
• Algorithms – ESA 2005
• Parameterized Algorithms
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Subexponential Parameterized Algorithms for Planar and Apex-Minor-Free Graphs via Low Treewidth Pattern Covering