Faster algorithms for cycle hitting problems on disk graphs

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

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

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

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)