Cleaning random d-regular graphs with brushes using a degree-greedy algorithm

Margaret Ellen Messinger, Paweł Prałat, Richard J. Nowakowski, Nicholas Wormald

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

10 Citations (Scopus)

Abstract

In the recently introduced model for cleaning a graph with brushes, we use a degree-greedy algorithm to clean a random d-regular graph on n vertices (with dn even). We then use a differential equations method to find the (asymptotic) number of brushes needed to clean a random d-regular graph using this algorithm. As well as the case for general d, interesting results for specific values of d are examined. We also state various open problems.

Original languageEnglish
Title of host publicationCombinatorial and Algorithmic Aspects of Networking - 4th Workshop, CAAN 2007, Revised Papers
Pages13-26
Number of pages14
Volume4852 LNCS
Publication statusPublished - 2007
Externally publishedYes
Event4th Workshop on Combinatorial and Algorithmic Aspects of Networking, CAAN 2007 - Halifax, Canada
Duration: 14 Aug 200714 Aug 2007

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4852 LNCS
ISSN (Print)03029743
ISSN (Electronic)16113349

Conference

Conference4th Workshop on Combinatorial and Algorithmic Aspects of Networking, CAAN 2007
CountryCanada
CityHalifax
Period14/08/0714/08/07

Keywords

  • Cleaning process
  • Degree-greedy algorithm
  • Differential equations method
  • Random d-regular graphs

Cite this