Faster algorithms for cycle hitting problems on disk graphs

DOI10.1007/978-3-031-38906-1_3MaRDI QIDQ6138985zbMATH OpenOpenAlexFDO

Authors 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

feedback vertex setdisk graphstriangle hitting set

Mathematics Subject Classification ID

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

Cites work

• scientific article; zbMATH DE number 7053376 (Why is no real title available?)
• A framework for exponential-time-hypothesis-tight algorithms and lower bounds in geometric intersection graphs
• A kernelization algorithm for \(d\)-hitting set
• Clique-based separators for geometric intersection graphs
• Decomposition of Map Graphs with Applications.
• Detecting Feedback Vertex Sets of Size k in O*(2.7^k) Time
• EPTAS and Subexponential Algorithm for Maximum Clique on Disk and Unit Ball Graphs
• Faster parameterized algorithms using linear programming
• Finding, hitting and packing cycles in subexponential time on unit disk graphs
• Order-k Voronoi diagrams of sites with additive weights in the plane
• Parameterized algorithms
• Subexponential parameterized algorithms on bounded-genus graphs and \(H\)-minor-free graphs
• Subexponential parameterized odd cycle transversal on planar graphs
• Unit disk graph recognition is NP-hard

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6138985)