Improved bounds for online dominating sets of trees

DOI10.4230/LIPICS.ISAAC.2017.52zbMATH Open1462.68242arXiv1710.11414MaRDI QIDQ5136272FDOQ5136272

Authors: Koji M. Kobayashi 

Publication date: 25 November 2020

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

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

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)

Cites Work

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

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)