Faster algorithms for cycle hitting problems on disk graphs

DOI10.1007/978-3-031-38906-1_3arXiv2311.03665OpenAlexW4385357266MaRDI QIDQ6138985

Shinwoo An, Kyungjin Cho, Eunjin Oh

Publication date: 16 January 2024

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

disk graphsfeedback vertex settriangle hitting set

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Data structures (68P05)

Cites Work

• Unnamed Item
• Unnamed Item
• Order-k Voronoi diagrams of sites with additive weights in the plane
• A kernelization algorithm for \(d\)-hitting set
• Unit disk graph recognition is NP-hard
• Finding, hitting and packing cycles in subexponential time on unit disk graphs
• A Framework for Exponential-Time-Hypothesis--Tight Algorithms and Lower Bounds in Geometric Intersection Graphs
• Subexponential parameterized algorithms on bounded-genus graphs and H -minor-free graphs
• Faster Parameterized Algorithms Using Linear Programming
• EPTAS and Subexponential Algorithm for Maximum Clique on Disk and Unit Ball Graphs
• Decomposition of Map Graphs with Applications.
• Detecting Feedback Vertex Sets of Size k in O*(2.7^k) Time
• Parameterized Algorithms
• Clique-based separators for geometric intersection graphs

This page was built for publication: Faster algorithms for cycle hitting problems on disk graphs