Vertex Sparsification in Trees

DOI10.1007/978-3-319-51741-4_9zbMath1486.05041arXiv1612.03017OpenAlexW2567279537MaRDI QIDQ2971161

Gramoz Goranci, Harald Räcke

Publication date: 4 April 2017

Published in: Approximation and Online Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1612.03017

zbMATH Keywords

treesgraph sparsificationvertex flow sparsifiers

Mathematics Subject Classification ID

Trees (05C05) Flows in graphs (05C21)

Related Items (5)

Reachability Preservers: New Extremal Bounds and Approximation Algorithms ⋮ Unnamed Item ⋮ Refined Vertex Sparsifiers of Planar Graphs ⋮ Improved Guarantees for Vertex Sparsification in Planar Graphs ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Characterizing multiterminal flow networks and computing flows in networks of small treewidth
• On mimicking networks representing minimum terminal cuts
• Metric extension operators, vertex sparsifiers and Lipschitz extendability
• Preserving Terminal Distances Using Minors
• Extensions and limits to vertex sparsification
• Spectral Sparsification of Graphs
• Hardness of robust network design
• Graph Minors for Preserving Terminal Distances Approximately - Lower and Upper Bounds
• Approximation Algorithms for Multicommodity-Type Problems with Guarantees Independent of the Graph Size
• On vertex sparsifiers with Steiner nodes
• Cutting Corners Cheaply, or How to Remove Steiner Points

This page was built for publication: Vertex Sparsification in Trees