Improved bounds for online dominating sets of trees

DOI10.4230/LIPICS.ISAAC.2017.52MaRDI QIDQ5136272zbMATH OpenFDO

Authors Koji M. Kobayashi

Publication date 25 November 2020

Full work available at URL https://arxiv.org/abs/1710.11414

zbMATH Keywords

randomized algorithmcompetitive analysisdominating settree graphonline algorithm

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Trees (05C05) Randomized algorithms (68W20) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Recommendations

• Online Dominating Set
• Online dominating set
• scientific article; zbMATH DE number 1302187
• The competitiveness of randomized algorithms for on-line Steiner tree and on-line spanning tree problems
• On the advice complexity of the online dominating set problem

Cites work

• scientific article; zbMATH DE number 5605070 (Why is no real title available?)
• scientific article; zbMATH DE number 1232130 (Why is no real title available?)
• A faster algorithm for dominating set analyzed by the potential method
• A note on the complexity of minimum dominating set
• Connected dominating set. Theory and applications
• Efficiency in exponential time for domination-type problems
• Exact algorithms for dominating set
• Graph-Theoretic Concepts in Computer Science
• Independent domination in graphs: A survey and recent results
• On-line algorithms for the dominating set problem
• Online Dominating Set
• Static competitive facility location: an overview of optimisation approaches.
• Total domination in graphs

Cited in

(3)

• Online dominating set and coloring
• Online Dominating Set
• An analysis of the size of the minimum dominating sets in random recursive trees, using the Cockayne-Goodman-Hedetniemi algorithm

This page was built for publication: Improved bounds for online dominating sets of trees

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