Improved guarantees for tree cut sparsifiers

DOI10.1007/978-3-662-44777-2_64MaRDI QIDQ2921461zbMATH OpenOpenAlexFDO

Authors Harald Räcke, Chintan D. Shah

Publication date 8 October 2014

Published in Algorithms - ESA 2014 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-662-44777-2_64

Mathematics Subject Classification ID

Trees (05C05) Flows in graphs (05C21) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Computing cut-based hierarchical decompositions in almost linear time
• Vertex sparsification in trees
• Vertex Sparsifiers: New Results from Old Techniques
• Vertex sparsifiers: new results from old techniques
• Extensions and limits to vertex sparsification

Cited in

(4)

• Mean isoperimetry with control on outliers: exact and approximation algorithms
• Computing cut-based hierarchical decompositions in almost linear time
• Maximum weight disjoint paths in outerplanar graphs via single-tree cut approximators
• Maximum weight disjoint paths in outerplanar graphs via single-tree cut approximators

This page was built for publication: Improved guarantees for tree cut sparsifiers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2921461)