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

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

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 proceeding › Conference Paper › Research › peer-review

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 language	English
Title of host publication	Combinatorial and Algorithmic Aspects of Networking - 4th Workshop, CAAN 2007, Revised Papers
Pages	13-26
Number of pages	14
Volume	4852 LNCS
Publication status	Published - 2007
Externally published	Yes
Event	4th Workshop on Combinatorial and Algorithmic Aspects of Networking, CAAN 2007 - Halifax, Canada Duration: 14 Aug 2007 → 14 Aug 2007

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	4852 LNCS
ISSN (Print)	03029743
ISSN (Electronic)	16113349

Conference

Conference	4th Workshop on Combinatorial and Algorithmic Aspects of Networking, CAAN 2007
Country/Territory	Canada
City	Halifax
Period	14/08/07 → 14/08/07

Keywords

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

Cite this

Messinger, M. E., Prałat, P., Nowakowski, R. J., & Wormald, N. (2007). Cleaning random d-regular graphs with brushes using a degree-greedy algorithm. In Combinatorial and Algorithmic Aspects of Networking - 4th Workshop, CAAN 2007, Revised Papers (Vol. 4852 LNCS, pp. 13-26). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4852 LNCS).

Messinger, Margaret Ellen ; Prałat, Paweł ; Nowakowski, Richard J. et al. / Cleaning random d-regular graphs with brushes using a degree-greedy algorithm. Combinatorial and Algorithmic Aspects of Networking - 4th Workshop, CAAN 2007, Revised Papers. Vol. 4852 LNCS 2007. pp. 13-26 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{2cf1fc2bf446434ebe81730d45a04145,

title = "Cleaning random d-regular graphs with brushes using a degree-greedy algorithm",

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.",

keywords = "Cleaning process, Degree-greedy algorithm, Differential equations method, Random d-regular graphs",

author = "Messinger, {Margaret Ellen} and Pawe{\l} Pra{\l}at and Nowakowski, {Richard J.} and Nicholas Wormald",

year = "2007",

language = "English",

isbn = "3540772936",

volume = "4852 LNCS",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "13--26",

booktitle = "Combinatorial and Algorithmic Aspects of Networking - 4th Workshop, CAAN 2007, Revised Papers",

note = "4th Workshop on Combinatorial and Algorithmic Aspects of Networking, CAAN 2007 ; Conference date: 14-08-2007 Through 14-08-2007",

}

Messinger, ME, Prałat, P, Nowakowski, RJ & Wormald, N 2007, Cleaning random d-regular graphs with brushes using a degree-greedy algorithm. in Combinatorial and Algorithmic Aspects of Networking - 4th Workshop, CAAN 2007, Revised Papers. vol. 4852 LNCS, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 4852 LNCS, pp. 13-26, 4th Workshop on Combinatorial and Algorithmic Aspects of Networking, CAAN 2007, Halifax, Canada, 14/08/07.

Cleaning random d-regular graphs with brushes using a degree-greedy algorithm. / Messinger, Margaret Ellen; Prałat, Paweł; Nowakowski, Richard J. et al.
Combinatorial and Algorithmic Aspects of Networking - 4th Workshop, CAAN 2007, Revised Papers. Vol. 4852 LNCS 2007. p. 13-26 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4852 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-review

TY - GEN

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

AU - Messinger, Margaret Ellen

AU - Prałat, Paweł

AU - Nowakowski, Richard J.

AU - Wormald, Nicholas

PY - 2007

Y1 - 2007

N2 - 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.

AB - 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.

KW - Cleaning process

KW - Degree-greedy algorithm

KW - Differential equations method

KW - Random d-regular graphs

UR - http://www.scopus.com/inward/record.url?scp=38549131735&partnerID=8YFLogxK

M3 - Conference Paper

AN - SCOPUS:38549131735

SN - 3540772936

SN - 9783540772934

VL - 4852 LNCS

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 13

EP - 26

BT - Combinatorial and Algorithmic Aspects of Networking - 4th Workshop, CAAN 2007, Revised Papers

T2 - 4th Workshop on Combinatorial and Algorithmic Aspects of Networking, CAAN 2007

Y2 - 14 August 2007 through 14 August 2007

ER -

Messinger ME, Prałat P, Nowakowski RJ, Wormald N. Cleaning random d-regular graphs with brushes using a degree-greedy algorithm. In Combinatorial and Algorithmic Aspects of Networking - 4th Workshop, CAAN 2007, Revised Papers. Vol. 4852 LNCS. 2007. p. 13-26. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

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

Abstract

Publication series

Conference

Keywords

Other files and links

Cite this