Random procedures for dominating sets in graphs

MaRDI QIDQ986706zbMATH OpenFDO

Authors Sarah Artmann, Frank Göring, Jochen Harant, Dieter Rautenbach, Ingo Schiermeyer

Publication date 12 August 2010

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://eudml.org/doc/228104, http://www.emis.de/journals/EJC/Volume_17/Abstracts/v17i1r102.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

dominationindependenceprobabilistic method

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Review text

Summary: We present and analyze some random procedures for the construction of small dominating sets in graphs. Several upper bounds for the domination number of a graph are derived from these procedures.

Recommendations

• Random procedures for dominating sets in bipartite graphs
• scientific article; zbMATH DE number 2230938
• On the domination number of a random graph
• Randomized greedy algorithms for finding smallk-dominating sets of regular graphs
• Dominating sets of random 2-in 2-out directed graphs

Cited in

(13)

• Dominating sets of random 2-in 2-out directed graphs
• A randomized algorithm for determining dominating sets in graphs of maximum degree five
• Randomized algorithms and upper bounds for multiple domination in graphs and networks
• New probabilistic upper bounds on the domination number of a graph
• Sieve methods in random graph theory
• Random iteration algorithm for graph-directed sets
• Random procedures for dominating sets in bipartite graphs
• A note on domination parameters in random graphs
• Best and worst case permutations for random online domination of the path
• Algorithms and Models for the Web-Graph
• Lower Bounds and Algorithms for Dominating Sets in Web Graphs
• Near-optimal dominating sets in dense random graphs in polynomial expected time
• New probabilistic upper bounds on the domination number of a graph. II

This page was built for publication: Random procedures for dominating sets in graphs

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