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

DOI10.1007/978-3-540-77294-1_4zbMath1136.05320OpenAlexW2162824303MaRDI QIDQ5458503

Margaret-Ellen Messinger, Paweł Prałat, Richard J. Nowakowski, Nicholas C. 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 processdifferential equations methoddegree-greedy algorithmrandom d-regular graphs

Mathematics Subject Classification ID

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

Related Items

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

Cites Work

• Cleaning a network with brushes
• The asymptotic connectivity of labelled regular graphs
• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• Analysis of greedy algorithms on graphs with bounded degrees
• Random matchings which induce Hamilton cycles and Hamiltonian decompositions of random regular graphs
• Almost all cubic graphs are Hamiltonian
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item