Stable approximation algorithms for dominating set and independent set

DOI10.1137/24M1644079MaRDI QIDQ6986950zbMATH OpenFDO

Authors Mark de Berg, Arpan Sadhukhan, Frits C. R. Spieksma

Publication date 7 May 2025

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/24M1644079

zbMATH Keywords

approximation algorithmsbounded recoursedominating setdynamic algorithmsindependent setstability

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25)

Cites work

• A framework for exponential-time-hypothesis-tight algorithms and lower bounds in geometric intersection graphs
• A Separator Theorem for Planar Graphs
• Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs
• Approximation hardness of dominating set problems in bounded degree graphs
• Combinatorics of local search: an optimal 4-local Hall's theorem for planar graphs
• scientific article; zbMATH DE number 1003261 (Why is no real title available?)
• scientific article; zbMATH DE number 1232130 (Why is no real title available?)
• scientific article; zbMATH DE number 7788595 (Why is no real title available?)
• Linear degree extractors and the inapproximability of max clique and chromatic number
• Maintaining assignments online: matching, scheduling, and flows
• On-line algorithms for the dominating set problem
• Online and dynamic algorithms for set cover
• Online Bin Covering with Limited Migration
• Online dominating set
• Online independent set beyond the worst-case: secretaries, prophets, and periods
• Online independent sets.
• Online maximum matching with recourse
• Relaxing the irrevocability requirement for online graph algorithms
• Robust online algorithms for certain dynamic packing problems
• Stable Approximation Algorithms for the Dynamic Broadcast Range-Assignment Problem
• The power of amortized recourse for online graph problems

This page was built for publication: Stable approximation algorithms for dominating set and independent set

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