Dominating sets of random 2-in 2-out directed graphs

MaRDI QIDQ1010736zbMATH OpenFDO

Authors Stephen Howe

Publication date 7 April 2009

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

Full work available at URL https://eudml.org/doc/117223, http://www.emis.de/journals/EJC/Volume_15/Abstracts/v15i1r29.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

2-in 2-out digraphs2-in 2-out directed graphsdeprioritised algorithmsmall dominating sets

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Recommendations

• Random procedures for dominating sets in graphs
• Randomized greedy algorithms for finding smallk-dominating sets of regular graphs
• Lower Bounds and Algorithms for Dominating Sets in Web Graphs
• Algorithms and Models for the Web-Graph
• On the Independent Domination Number of Random Regular Graphs

Cited in

(10)

• Directed dominating set problem studied by cavity method: warning propagation and population dynamics
• Near-optimal dominating sets in dense random graphs in polynomial expected time
• Random procedures for dominating sets in graphs
• The 2-tuple dominating independent number of a random graph
• Dominating sets in directed graphs
• Algorithms and Models for the Web-Graph
• The directed dominating set problem: generalized leaf removal and belief propagation
• Statistical mechanics of the directed 2-distance minimal dominating set problem
• Lower Bounds and Algorithms for Dominating Sets in Web Graphs
• Random procedures for dominating sets in bipartite graphs

This page was built for publication: Dominating sets of random 2-in 2-out directed graphs

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