Vertex sparsification in trees

Gramoz Goranci, Harald Räcke

Publikation: Beitrag in Buch/Bericht/KonferenzbandKonferenzbeitragBegutachtung

7 Zitate (Scopus)

Abstract

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.

OriginalspracheEnglisch
TitelApproximation and Online Algorithms - 14th International Workshop, WAOA 2016, Revised Selected Papers
Redakteure/-innenMonaldo Mastrolilli, Klaus Jansen
Herausgeber (Verlag)Springer Verlag
Seiten103-115
Seitenumfang13
ISBN (Print)9783319517407
DOIs
PublikationsstatusVeröffentlicht - 2017
Veranstaltung14th International Workshop on Approximation and Online Algorithms, WAOA 2016 - Aarhus, Dänemark
Dauer: 25 Aug. 201626 Aug. 2016

Publikationsreihe

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Band10138 LNCS
ISSN (Print)0302-9743
ISSN (elektronisch)1611-3349

Konferenz

Konferenz14th International Workshop on Approximation and Online Algorithms, WAOA 2016
Land/GebietDänemark
OrtAarhus
Zeitraum25/08/1626/08/16

Fingerprint

Untersuchen Sie die Forschungsthemen von „Vertex sparsification in trees“. Zusammen bilden sie einen einzigartigen Fingerprint.

Dieses zitieren