Packing edges in random regular graphs

Mihalis Beis; William Duckworth; Michele Zito

doi:10.1007/3-540-45687-2_9

Packing edges in random regular graphs

Mihalis Beis, William Duckworth, Michele Zito

School of Computing

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

5 Citations (Scopus)

Abstract

A k-separated matching in a graph is a set of edges at distance at least k from one another (hence, for instance, a 1-separated matching is just a matching in the classical sense). We consider the problem of approximating the solution to the maximum k-separated matching problem in random r-regular graphs for each fixed integer k and each fixed r ≥ 3. We prove both constructive lower bounds and combinatorial upper bounds on the size of the optimal solutions.

Original language	English
Title of host publication	Mathematical Foundations of Computer Science 2002, 27th International Symposium, MFCS 2002 Warsaw, Poland, August 26-30, 2002 Proceedings
Editors	Krzysztof Diks, Wojciech Rytter
Place of Publication	Heidelberg, Germany
Publisher	Springer, Springer Nature
Pages	118-130
Number of pages	13
ISBN (Print)	3540440402
DOIs	https://doi.org/10.1007/3-540-45687-2_9
Publication status	Published - 2002
Event	The 27th International Symposium on Mathematical Foundations of Computer Science - Warsaw, Poland Duration: 26 Aug 2002 → 30 Aug 2002

Conference

Conference	The 27th International Symposium on Mathematical Foundations of Computer Science
City	Warsaw, Poland
Period	26/08/02 → 30/08/02

Access to Document

10.1007/3-540-45687-2_9

Cite this

@inproceedings{8dc16f38952f41baa0a92301078952b0,

title = "Packing edges in random regular graphs",

abstract = "A k-separated matching in a graph is a set of edges at distance at least k from one another (hence, for instance, a 1-separated matching is just a matching in the classical sense). We consider the problem of approximating the solution to the maximum k-separated matching problem in random r-regular graphs for each fixed integer k and each fixed r ≥ 3. We prove both constructive lower bounds and combinatorial upper bounds on the size of the optimal solutions.",

author = "Mihalis Beis and William Duckworth and Michele Zito",

year = "2002",

doi = "10.1007/3-540-45687-2_9",

language = "English",

isbn = "3540440402",

pages = "118--130",

editor = "Krzysztof Diks and Wojciech Rytter",

booktitle = "Mathematical Foundations of Computer Science 2002, 27th International Symposium, MFCS 2002 Warsaw, Poland, August 26-30, 2002 Proceedings",

publisher = "Springer, Springer Nature",

address = "United States",

note = "The 27th International Symposium on Mathematical Foundations of Computer Science ; Conference date: 26-08-2002 Through 30-08-2002",

}

Beis, M, Duckworth, W & Zito, M 2002, Packing edges in random regular graphs. in K Diks & W Rytter (eds), Mathematical Foundations of Computer Science 2002, 27th International Symposium, MFCS 2002 Warsaw, Poland, August 26-30, 2002 Proceedings. Springer, Springer Nature, Heidelberg, Germany, pp. 118-130, The 27th International Symposium on Mathematical Foundations of Computer Science, Warsaw, Poland, 26/08/02. https://doi.org/10.1007/3-540-45687-2_9

Packing edges in random regular graphs. / Beis, Mihalis; Duckworth, William; Zito, Michele.
Mathematical Foundations of Computer Science 2002, 27th International Symposium, MFCS 2002 Warsaw, Poland, August 26-30, 2002 Proceedings. ed. / Krzysztof Diks; Wojciech Rytter. Heidelberg, Germany: Springer, Springer Nature, 2002. p. 118-130.

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

TY - GEN

T1 - Packing edges in random regular graphs

AU - Beis, Mihalis

AU - Duckworth, William

AU - Zito, Michele

PY - 2002

Y1 - 2002

N2 - A k-separated matching in a graph is a set of edges at distance at least k from one another (hence, for instance, a 1-separated matching is just a matching in the classical sense). We consider the problem of approximating the solution to the maximum k-separated matching problem in random r-regular graphs for each fixed integer k and each fixed r ≥ 3. We prove both constructive lower bounds and combinatorial upper bounds on the size of the optimal solutions.

AB - A k-separated matching in a graph is a set of edges at distance at least k from one another (hence, for instance, a 1-separated matching is just a matching in the classical sense). We consider the problem of approximating the solution to the maximum k-separated matching problem in random r-regular graphs for each fixed integer k and each fixed r ≥ 3. We prove both constructive lower bounds and combinatorial upper bounds on the size of the optimal solutions.

U2 - 10.1007/3-540-45687-2_9

DO - 10.1007/3-540-45687-2_9

M3 - Conference proceeding contribution

SN - 3540440402

SP - 118

EP - 130

BT - Mathematical Foundations of Computer Science 2002, 27th International Symposium, MFCS 2002 Warsaw, Poland, August 26-30, 2002 Proceedings

A2 - Diks, Krzysztof

A2 - Rytter, Wojciech

PB - Springer, Springer Nature

CY - Heidelberg, Germany

T2 - The 27th International Symposium on Mathematical Foundations of Computer Science

Y2 - 26 August 2002 through 30 August 2002

ER -

Packing edges in random regular graphs

Abstract

Conference

Access to Document

Fingerprint

Cite this