Capacity-preserving subgraphs of directed flow networks

DOI10.1007/978-3-031-34347-6_14arXiv2303.17274OpenAlexW4379117816MaRDI QIDQ6182901

Max Ilsen, Markus Chimani

Publication date: 22 December 2023

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

series-parallel graphsmaximum flowinapproximabilityminimum equivalent digraph

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Discrete mathematics in relation to computer science (68Rxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A factor 2 approximation algorithm for the generalized Steiner network problem
• A linear time \(\frac{5}{3}\)-approximation for the minimum strongly-connected spanning subgraph problem
• On sparse spanners of weighted graphs
• Directed Steiner problems with connectivity constraints
• Graph spanners: a tutorial review
• Topology of series-parallel networks
• An efficiently solvable case of the minimum weight equivalent subgraph problem
• The Recognition of Series Parallel Digraphs
• Approximating the Minimum Equivalent Digraph
• Reducibility among Combinatorial Problems
• Approximation Algorithms for Multicommodity-Type Problems with Guarantees Independent of the Graph Size
• Computationally Related Problems
• Analytical approach to parallel repetition
• Design of Survivable Networks: A survey
• The Transitive Reduction of a Directed Graph
• Telecommunications network design: Technology impacts and future directions

This page was built for publication: Capacity-preserving subgraphs of directed flow networks