Packing edges in random regular graphs

Mihalis Beis, William Duckworth, Michele Zito

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

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 languageEnglish
Title of host publicationMathematical Foundations of Computer Science 2002, 27th International Symposium, MFCS 2002 Warsaw, Poland, August 26-30, 2002 Proceedings
EditorsKrzysztof Diks, Wojciech Rytter
Place of PublicationHeidelberg, Germany
PublisherSpringer, Springer Nature
Pages118-130
Number of pages13
ISBN (Print)3540440402
DOIs
Publication statusPublished - 2002
EventThe 27th International Symposium on Mathematical Foundations of Computer Science - Warsaw, Poland
Duration: 26 Aug 200230 Aug 2002

Conference

ConferenceThe 27th International Symposium on Mathematical Foundations of Computer Science
CityWarsaw, Poland
Period26/08/0230/08/02

Fingerprint Dive into the research topics of 'Packing edges in random regular graphs'. Together they form a unique fingerprint.

Cite this