TY - GEN
T1 - Vertex sparsification in trees
AU - Goranci, Gramoz
AU - Räcke, Harald
N1 - Publisher Copyright:
© Springer International Publishing AG 2017.
PY - 2017
Y1 - 2017
N2 - Given an unweighted tree T = (V,E) with terminals K ⊂ V, we show how to obtain a 2-quality vertex flow and cut sparsifier H with VH = K. We prove that our result is essentially tight by providing a 2− o(1) lower-bound on the quality of any cut sparsifier for stars. In addition we give improved results for quasi-bipartite graphs. First, we show how to obtain a 2-quality flow sparsifier with VH = K for such graphs. We then consider the other extreme and construct exact sparsifiers of size O(2k), when the input graph is unweighted.
AB - Given an unweighted tree T = (V,E) with terminals K ⊂ V, we show how to obtain a 2-quality vertex flow and cut sparsifier H with VH = K. We prove that our result is essentially tight by providing a 2− o(1) lower-bound on the quality of any cut sparsifier for stars. In addition we give improved results for quasi-bipartite graphs. First, we show how to obtain a 2-quality flow sparsifier with VH = K for such graphs. We then consider the other extreme and construct exact sparsifiers of size O(2k), when the input graph is unweighted.
KW - Graph sparsification
KW - Trees
KW - Vertex flow sparsifiers
UR - http://www.scopus.com/inward/record.url?scp=85010657837&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-51741-4_9
DO - 10.1007/978-3-319-51741-4_9
M3 - Conference contribution
AN - SCOPUS:85010657837
SN - 9783319517407
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 103
EP - 115
BT - Approximation and Online Algorithms - 14th International Workshop, WAOA 2016, Revised Selected Papers
A2 - Mastrolilli, Monaldo
A2 - Jansen, Klaus
PB - Springer Verlag
T2 - 14th International Workshop on Approximation and Online Algorithms, WAOA 2016
Y2 - 25 August 2016 through 26 August 2016
ER -