ETH-tight algorithm for cycle packing on unit disk graphs

DOI10.4230/LIPICS.SOCG.2024.7MaRDI QIDQ6895900zbMATH OpenFDO

Authors Shinwoo An, Eunjin Oh

Publication date 24 November 2025

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.SOCG.2024.7

zbMATH Keywords

cycle packingparameterized algorithmtree decompositionunit-disk graphs

Mathematics Subject Classification ID

Graph representations (geometric and intersection representations, etc.) (05C62) Graph algorithms (graph-theoretic aspects) (05C85) Parameterized complexity, tractability and kernelization (68Q27) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Cites work

• A framework for exponential-time-hypothesis-tight algorithms and lower bounds in geometric intersection graphs
• A Linear Kernel for the k-Disjoint Cycle Problem on Planar Graphs
• An approximation algorithm for maximum triangle packing
• Approximability of packing disjoint cycles
• Approximate shortest paths and distance oracles in weighted unit-disk graphs
• Approximation algorithms and hardness results for cycle packing problems
• Catalan structures and dynamic programming in \(H\)-minor-free graphs
• Decomposition of Map Graphs with Applications.
• Distributed coloring and the local structure of unit-disk graphs
• Efficient exact algorithms on planar graphs: Exploiting sphere cut decompositions
• ETH-Tight Algorithms for Long Path and Cycle on Unit Disk Graphs
• Finding triangles and other small subgraphs in geometric intersection graphs
• Finding, hitting and packing cycles in subexponential time on unit disk graphs
• Fundamentals of parameterized complexity
• scientific article; zbMATH DE number 7053376 (Why is no real title available?)
• scientific article; zbMATH DE number 7799599 (Why is no real title available?)
• scientific article; zbMATH DE number 7788620 (Why is no real title available?)
• Odd cycle packing
• Packing cycles faster than Erdős-Pósa
• Parallel algorithms for minimum general partial dominating set and maximum budgeted dominating set in unit disk graph
• Parameterized Complexity of Independence and Domination on Geometric Graphs
• Parameterized study of Steiner tree on unit disk graphs
• Routing in unit disk graphs
• Shortest paths in intersection graphs of unit disks
• Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
• Structured recursive separator decompositions for planar graphs in linear time
• Subexponential Parameterized algorithms on disk graphs (extended abstract)
• True contraction decomposition and almost ETH-tight bipartization for unit-disk graphs
• Vertex-edge domination in unit disk graphs
• Weighted graph separators and their applications

Cited in

(1)

• Dynamic parameterized problems on unit disk graphs

This page was built for publication: ETH-tight algorithm for cycle packing on unit disk graphs

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