TR-2010-08

Degree bounded forest covering

Tamás Király, Lap Chi Lau

Published in:
Proceedings of 15th International Conference IPCO 2011, LNCS 6655 (2011), 315-323



Abstract

We prove that for an undirected graph with arboricity at most $k+\epsilon$, its edges can be decomposed into $k$ forests and a subgraph with maximum degree $\lceil \frac{k \epsilon +1}{1-\epsilon} \rceil$. The problem is solved by a linear programming based approach: we first prove that there exists a fractional solution to the problem, and then use a result on the degree bounded matroid problem by Király, Lau and Singh [5] to get an integral solution.


Bibtex entry:

@techreport{egres-10-08,
AUTHOR = {Kir{\'a}ly, Tam{\'a}s and Lau Chi, Lap},
TITLE = {Degree bounded forest covering},
NOTE= {{\tt www.cs.elte.hu/egres}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2010},
NUMBER = {TR-2010-08}
}


Last modification: 5.6.2018. Please email your comments to Tamás Király!