Cleaning Random d-Regular Graphs with Brushes Using a Degree-Greedy Algorithm

DOI10.1007/978-3-540-77294-1_4MaRDI QIDQ5458503zbMATH OpenOpenAlexFDO

Authors Margaret-Ellen Messinger, Paweł Prałat, R. J. Nowakowski, Nicholas Wormald

Publication date 15 April 2008

Published in Combinatorial and Algorithmic Aspects of Networking (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-77294-1_4

zbMATH Keywords

cleaning processdegree-greedy algorithmdifferential equations methodrandom d-regular graphs

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Applications of graph theory (05C90)

Recommendations

• Cleaning regular graphs with brushes
• Brush your trees!
• Cleaning random \(d\)-regular graphs with brooms
• Cleaning random graphs with brushes
• Cleaning a network with brushes

Cites work

• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• Almost all cubic graphs are Hamiltonian
• Analysis of greedy algorithms on graphs with bounded degrees
• Cleaning a network with brushes
• scientific article; zbMATH DE number 3708282 (Why is no real title available?)
• scientific article; zbMATH DE number 1342092 (Why is no real title available?)
• scientific article; zbMATH DE number 747040 (Why is no real title available?)
• scientific article; zbMATH DE number 1405894 (Why is no real title available?)
• Random matchings which induce Hamilton cycles and Hamiltonian decompositions of random regular graphs
• The asymptotic connectivity of labelled regular graphs

Cited in

(10)

• \textsc{polish} -- Let us play the cleaning game
• Brushing without capacity restrictions
• Cleaning random graphs with brushes
• Cleaning regular graphs with brushes
• The Robot Cleans Up
• Cleaning with brooms
• Cleaning random \(d\)-regular graphs with brooms
• The robot cleans up
• Parallel cleaning of a network with brushes
• Clean the graph before you draw it!

This page was built for publication: Cleaning Random d-Regular Graphs with Brushes Using a Degree-Greedy Algorithm

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