Network flow spanners
From MaRDI portal
Publication:3057178
DOI10.1002/net.20357zbMath1202.90054MaRDI QIDQ3057178
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
NP-completeness; network design; approximation algorithms; spanners; spanning trees; maximum flow preservation
90B18: Communication networks in operations research
05C85: Graph algorithms (graph-theoretic aspects)
Cites Work
- 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
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
