Large k-separated matchings of random regular graphs

Mihalis Beis, William Duckworth, Michele Zito

Research output: Chapter in Book/Report/Conference proceedingConference proceeding contribution

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 languageEnglish
Title of host publicationProceedings of the Twenty Eighth Australasian Computer Science Conference (ACSC 2005)
EditorsVladimir Estivill-Castro
Place of PublicationSydney, Australia
PublisherAustralian Computer Society
Pages175-181
Number of pages7
ISBN (Print)1920682201
Publication statusPublished - 2005
EventTwenty Eighth Australasian Computer Science Conference (ACSC 2005) - Newcastle, Australia
Duration: 31 Jan 20052 Mar 2005

Conference

ConferenceTwenty Eighth Australasian Computer Science Conference (ACSC 2005)
CityNewcastle, Australia
Period31/01/052/03/05

Fingerprint Dive into the research topics of 'Large <i>k</i>-separated matchings of random regular graphs'. Together they form a unique fingerprint.

Cite this