Large k-separated matchings of random regular graphs

Mihalis Beis, William Duckworth, Michele Zito

Research output: Chapter in Book/Report/Conference proceedingConference proceeding contributionpeer-review

1 Citation (Scopus)


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


ConferenceTwenty Eighth Australasian Computer Science Conference (ACSC 2005)
CityNewcastle, Australia

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