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

被引：0

作者：

Messinger, Margaret-Ellen ^{[1
]}

Pralat, Pawel ^{[1
]}

Nowakowski, Richard J. ^{[1
]}

Wormald, Nicholas ^{[2
]}

机构：

[1] Dalhousie Univ, Dept Math & Stat, Halifax, NS, Canada

[2] Univ Waterloo, Dept Combinator & Optimizat, Waterloo, ON N2L 3G1, Canada

来源：

COMBINATORIAL AND ALGORITHMIC ASPECTS OF NETWORKING | 2007年 / 4852卷

基金：

加拿大自然科学与工程研究理事会;

关键词：

cleaning process; random d-regular graphs; degree-greedy algorithm; differential equations method;

D O I：

暂无

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

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.

引用

页码：13 / +

页数：2

共 12 条

[1] [Anonymous], 1992, P S RANDOM GRAPHS PO
[2] Bollobas B., 1980, European Journal of Combinatorics, V1, P311
[3] Bollobas Bela, 1981, LONDON MATH SOC LECT, V52, P80
[4] Random matchings which induce Hamilton cycles and Hamiltonian decompositions of random regular graphs
Kim, JH
Wormald, NC
[J]. JOURNAL OF COMBINATORIAL THEORY SERIES B, 2001, 81 (01) : 20 - 44
[5] MCKEIL S, 2007, THESIS DALHOUSIE U
[6] MESSINGER ME, IN PRESS THEORETICAL
[7] Monagan MB, 2005, MAPLE 10 PROGRAMMING
[8] ALMOST ALL CUBIC GRAPHS ARE HAMILTONIAN
ROBINSON, RW
WORMALD, NC
[J]. RANDOM STRUCTURES & ALGORITHMS, 1992, 3 (02) : 117 - 125
[9] Wormald N C, 1999, LECT APPROXIMATION R, P73
[10] Analysis of greedy algorithms on graphs with bounded degrees
Wormald, NC
[J]. DISCRETE MATHEMATICS, 2003, 273 (1-3) : 235 - 260

← 1 2 →