An analysis of the size of the minimum dominating sets in random recursive trees, using the Cockayne-Goodman-Hedetniemi algorithm

DOI10.1016/j.dam.2008.06.024zbMath1227.05205OpenAlexW2087753151MaRDI QIDQ1026103

Michele Zito, Colin Cooper

Publication date: 24 June 2009

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2008.06.024

zbMATH Keywords

algorithmsrandom treesdominating sets

Mathematics Subject Classification ID

Trees (05C05) Random graphs (graph-theoretic aspects) (05C80) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (2)

A note on the independence number, domination number and related parameters of random binary search trees and random recursive trees ⋮ On random trees obtained from permutation graphs

Cites Work

• A linear algorithm for the domination number of a tree
• Sparse hypercube 3-spanners
• Emergence of Scaling in Random Networks
• A threshold of ln n for approximating set cover
• `` Strong NP-Completeness Results
• On the domination number of a random graph
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: An analysis of the size of the minimum dominating sets in random recursive trees, using the Cockayne-Goodman-Hedetniemi algorithm