Randomised algorithms for finding small weakly-connected dominating sets of regular graphs

DOI10.1007/3-540-44849-7_15MaRDI QIDQ4437499zbMATH OpenFDO

Authors W. Duckworth, Bernard Mans

Publication date 2 December 2003

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/2653/26530083.htm

zbMATH Keywords

dominating setsrandom regular graphsweakly-connected

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Randomized algorithms (68W20)

Recommendations

• Connected domination of regular graphs
• On the connected domination number of random regular graphs
• Small k-dominating sets of regular graphs
• Minimum connected dominating sets of random cubic graphs
• A new kind of domination in regular graphs

Cited in

(6)

• Connected domination of regular graphs
• A randomized algorithm for determining dominating sets in graphs of maximum degree five
• Analysis of a greedy heuristic for finding small dominating sets in graphs
• Learning automata-based algorithms for finding minimum weakly connected dominating set in stochastic graphs
• On the connected domination number of random regular graphs
• Bounds relating the weakly connected domination number to the total domination number and the matching number

This page was built for publication: Randomised algorithms for finding small weakly-connected dominating sets of regular graphs

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