Online dominating set

DOI10.1007/s00453-018-0519-1zbMath1421.68239OpenAlexW2893780080WikidataQ129189893 ScholiaQ129189893MaRDI QIDQ1741855

Michal Kotrbčík, Stephan J. Eidenbenz, Kim S. Larsen, Lene Monrad Favrholdt, Joan. Boyar

Publication date: 7 May 2019

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-018-0519-1

zbMATH Keywords

competitive analysisonline algorithmsdominating setirrevocability

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Online algorithms; streaming algorithms (68W27)

Related Items

A heuristic approximation algorithm of minimum dominating set based on rough set theory ⋮ The online broadcast range-assignment problem ⋮ The Online Broadcast Range-Assignment Problem ⋮ On the advice complexity of the online dominating set problem ⋮ Relaxing the irrevocability requirement for online graph algorithms

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On-line algorithms for the dominating set problem
• Connected dominating set. Theory and applications
• Competitive snoopy caching
• Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
• The seat reservation problem
• Two-Bounded-Space Bin Packing Revisited
• A threshold of ln n for approximating set cover
• Online Colored Bin Packing
• A Greedy Heuristic for the Set-Covering Problem
• Approximation algorithms for NP-complete problems on planar graphs
• Fixed-Parameter Tractability and Completeness I: Basic Results
• Total Domination in Graphs
• Reducibility among Combinatorial Problems