Network flow spanners

DOI10.1002/NET.20357MaRDI QIDQ3057178zbMATH OpenOpenAlexFDO

Authors Feodor F. Dragan, Chenyu Yan

Publication date 24 November 2010

Published in Networks (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/net.20357

zbMATH Keywords

approximation algorithmsmaximum flow preservationnetwork designNP-completenessspannersspanning trees

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Communication networks in operations research (90B18)

Recommendations

• Network Flow Spanners
• Note: Small integral flows need only sparse networks
• Directed spanners via flow-based linear programs
• On the hardness of approximating spanners
• Designing multi-commodity flow trees

Cites work

• (1 + εΒ) -spanner constructions for general graphs
• A Better Approximation Ratio for the Minimum Sizek-Edge-Connected Spanning Subgraph Problem
• A factor 2 approximation algorithm for the generalized Steiner network problem
• A linear-time algorithm for finding a sparse \(k\)-connected spanning subgraph of a \(k\)-connected graph
• A primal-dual approximation algorithm for generalized Steiner network problems
• Additive graph spanners
• An efficient approximation algorithm for the survivable network design problem
• Approximating minimum MAX-stretch spanning trees on unweighted graphs
• Approximating Minimum-Size k-Connected Spanning Subgraphs via Matching
• Approximating the smallest k-edge connected spanning subgraph by LP-rounding
• Approximation Algorithms for Several Graph Augmentation Problems
• Biconnectivity approximations and graph carvings
• Distributed Computing: A Locality-Sensitive Approach
• scientific article; zbMATH DE number 1003253 (Why is no real title available?)
• scientific article; zbMATH DE number 434498 (Why is no real title available?)
• scientific article; zbMATH DE number 1375574 (Why is no real title available?)
• scientific article; zbMATH DE number 2011848 (Why is no real title available?)
• scientific article; zbMATH DE number 2038725 (Why is no real title available?)
• scientific article; zbMATH DE number 1445376 (Why is no real title available?)
• Multi-Terminal Network Flows
• On network design problems: fixed cost flows and the covering Steiner problem
• On sparse spanners of weighted graphs
• Reconstructing the shape of a tree from observed dissimilarity data
• Restrictions of minimum spanner problems
• There are planar graphs almost as good as the complete graph
• Tree Spanners
• Tree spanners in planar graphs
• Tree spanners on chordal graphs: complexity and algorithms

Cited in

(3)

• Source-wise round-trip spanners
• Network Flow Spanners
• Note: Small integral flows need only sparse networks

This page was built for publication: Network flow spanners

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