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 |