Network flow spanners

DOI10.1002/net.20357zbMath1202.90054MaRDI QIDQ3057178

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

NP-completeness; network design; approximation algorithms; spanners; spanning trees; maximum flow preservation

Mathematics Subject Classification ID

90B18: Communication networks in operations research

05C85: Graph algorithms (graph-theoretic aspects)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Reconstructing the shape of a tree from observed dissimilarity data
• 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
• On sparse spanners of weighted graphs
• An efficient approximation algorithm for the survivable network design problem
• Restrictions of minimum spanner problems
• There are planar graphs almost as good as the complete graph
• Tree spanners on chordal graphs: complexity and algorithms
• On network design problems: fixed cost flows and the covering steiner problem
• Multi-Terminal Network Flows
• Approximation Algorithms for Several Graph Augmentation Problems
• A Better Approximation Ratio for the Minimum Sizek-Edge-Connected Spanning Subgraph Problem
• Biconnectivity approximations and graph carvings
• Approximating Minimum-Size k-Connected Spanning Subgraphs via Matching
• Distributed Computing: A Locality-Sensitive Approach
• Tree Spanners
• (1 + εΒ) -spanner constructions for general graphs
• A primal-dual approximation algorithm for generalized Steiner network problems
• Additive graph spanners
• Tree spanners in planar graphs