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