Improved guarantees for tree cut sparsifiers

Harald Räcke, Chintan Shah

Publikation: Beitrag in Buch/Bericht/KonferenzbandKonferenzbeitragBegutachtung

6 Zitate (Scopus)

Abstract

Harrelson, Hildrum and Rao [11] construct for a given graph a single tree that acts as a flow sparsifier, i.e., it can approximate multicommodity flows in G up to an O(log 2 nloglog n) factor. Many applications that use these trees do not actually require a flow sparsifier but would already work with just having a cut sparsifier. We show how to construct a cut sparsifier that is a single tree and has quality O(log 1.5 nloglog n). In addition we show a close connection of this problem to the Mincut Linear Arrangement Problem which shows that improving the guarantee to o(log 1.5 n) might be difficult.

OriginalspracheEnglisch
TitelAlgorithms, ESA 2014 - 22nd Annual European Symposium, Proceedings
Herausgeber (Verlag)Springer Verlag
Seiten774-785
Seitenumfang12
ISBN (Print)9783662447765
DOIs
PublikationsstatusVeröffentlicht - 2014
Veranstaltung22nd Annual European Symposium on Algorithms, ESA 2014 - Wroclaw, Polen
Dauer: 8 Sept. 201410 Sept. 2014

Publikationsreihe

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

Konferenz

Konferenz22nd Annual European Symposium on Algorithms, ESA 2014
Land/GebietPolen
OrtWroclaw
Zeitraum8/09/1410/09/14

Fingerprint

Untersuchen Sie die Forschungsthemen von „Improved guarantees for tree cut sparsifiers“. Zusammen bilden sie einen einzigartigen Fingerprint.

Dieses zitieren