Large k-separated matchings of random regular graphs

Mihalis Beis; William Duckworth; Michele Zito

Large k-separated matchings of 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

1 Citation (Scopus)

Abstract

A k-separated matching in a graph is a set of edges at distance at least ? 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	Proceedings of the Twenty Eighth Australasian Computer Science Conference (ACSC 2005)
Editors	Vladimir Estivill-Castro
Place of Publication	Sydney, Australia
Publisher	Australian Computer Society
Pages	175-181
Number of pages	7
ISBN (Print)	1920682201
Publication status	Published - 2005
Event	Twenty Eighth Australasian Computer Science Conference (ACSC 2005) - Newcastle, Australia Duration: 31 Jan 2005 → 2 Mar 2005

Conference

Conference	Twenty Eighth Australasian Computer Science Conference (ACSC 2005)
City	Newcastle, Australia
Period	31/01/05 → 2/03/05

Cite this

@inproceedings{e3b701ff4e2b407a8ec6fd2adcdb623f,

title = "Large k-separated matchings of random regular graphs",

abstract = "A k-separated matching in a graph is a set of edges at distance at least ? 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 = "2005",

language = "English",

isbn = "1920682201",

pages = "175--181",

editor = "Vladimir Estivill-Castro",

booktitle = "Proceedings of the Twenty Eighth Australasian Computer Science Conference (ACSC 2005)",

publisher = "Australian Computer Society",

address = "Australia",

note = "Twenty Eighth Australasian Computer Science Conference (ACSC 2005) ; Conference date: 31-01-2005 Through 02-03-2005",

}

Large k-separated matchings of random regular graphs. / Beis, Mihalis; Duckworth, William; Zito, Michele.
Proceedings of the Twenty Eighth Australasian Computer Science Conference (ACSC 2005). ed. / Vladimir Estivill-Castro. Sydney, Australia: Australian Computer Society, 2005. p. 175-181.

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

TY - GEN

T1 - Large k-separated matchings of random regular graphs

AU - Beis, Mihalis

AU - Duckworth, William

AU - Zito, Michele

PY - 2005

Y1 - 2005

N2 - A k-separated matching in a graph is a set of edges at distance at least ? 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 ? 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.

UR - https://www.scopus.com/pages/publications/33750700934

M3 - Conference proceeding contribution

SN - 1920682201

SP - 175

EP - 181

BT - Proceedings of the Twenty Eighth Australasian Computer Science Conference (ACSC 2005)

A2 - Estivill-Castro, Vladimir

PB - Australian Computer Society

CY - Sydney, Australia

T2 - Twenty Eighth Australasian Computer Science Conference (ACSC 2005)

Y2 - 31 January 2005 through 2 March 2005

ER -

Large k-separated matchings of random regular graphs

Abstract

Conference

Other files and links

Fingerprint

Cite this