Dynamic parameterized problems on unit disk graphs

DOI10.4230/LIPICS.ISAAC.2024.6MaRDI QIDQ7260611zbMATH OpenFDO

Authors Shinwoo An, Kyungjin Cho, Leo Jang, Byeonghyeon Jung, Yudam Lee, Eunjin Oh, Donghun Shin, Hyeonjun Shin, Chanho Song

Publication date 8 June 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.ISAAC.2024.6

zbMATH Keywords

kernelizationunit disk graphsdynamic parameterized algorithms

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cites work

• scientific article; zbMATH DE number 7053376 (Why is no real title available?)
• scientific article; zbMATH DE number 7788388 (Why is no real title available?)
• scientific article; zbMATH DE number 7788620 (Why is no real title available?)
• 2-Isomorphic Graphs
• A dynamic data structure for MSO properties in graphs with bounded tree-depth
• A framework for exponential-time-hypothesis-tight algorithms and lower bounds in geometric intersection graphs
• A study on two geometric location problems
• Algorithms for computing maximum cliques in hyperbolic random graphs
• Approximation schemes for covering and packing problems in image processing and VLSI
• Congruent Graphs and the Connectivity of Graphs
• Dynamic Geometric Set Cover and Hitting Set
• Dynamic Parameterized Problems and Algorithms
• Dynamic connectivity: connecting to networks and geometry
• Dynamic geometric connectivity in the plane with constant query time
• Dynamic treewidth
• ETH-tight algorithm for cycle packing on unit disk graphs
• ETH-tight algorithms for long path and cycle on unit disk graphs
• Embedding planar graphs at fixed vertex locations
• Faster algorithms for cycle hitting problems on disk graphs
• Finding, hitting and packing cycles in subexponential time on unit disk graphs
• Fully dynamic maximum independent sets of disks in polylogarithmic update time
• Hamilton Paths in Grid Graphs
• Minimum connected dominating sets and maximal independent sets in unit disk graphs
• On-line approach to off-line coloring problems on graphs with geometric representations
• Parameterized algorithms
• Polynomial-Time Approximation Schemes for Geometric Intersection Graphs
• Reachability problems for transmission graphs
• Sparse outerstring graphs have logarithmic treewidth
• Subexponential Parameterized algorithms on disk graphs (extended abstract)
• Subexponential parameterized algorithms on bounded-genus graphs and H-minor-free graphs
• Unit disk graphs

This page was built for publication: Dynamic parameterized problems on unit disk graphs

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