Simple linear flow decomposition algorithms on trees, circles, and augmented trees

DOI10.1002/net.21470zbMath1269.90136OpenAlexW2041402531MaRDI QIDQ5326771

Balachandran Vaidyanathan

Publication date: 6 August 2013

Published in: Networks (Search for Journal in Brave)

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

zbMATH Keywords

treescirclescomplexity analysisflow decompositionnetwork flow algorithmsaugmented trees

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Applications of graph theory (05C90) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (2)

Faster strongly polynomial algorithms for the unbalanced transportation problem and assignment problem with monge costs ⋮ Fast algorithms for convex cost flow problems on circles, lines, and trees

Cites Work

• Unnamed Item
• An algorithm for computing the restriction s|caffold assignment problem in computational biology
• Dynamic trees as search trees via Euler tours, applied to the network simplex algorithm
• A data structure for dynamic trees
• Fast algorithms for convex cost flow problems on circles, lines, and trees
• Fast Algorithms for Specially Structured Minimum Cost Flow Problems with Applications
• A new approach to the maximum-flow problem
• Improved Time Bounds for the Maximum Flow Problem
• Efficient Minimum Cost Matching and Transportation Using the Quadrangle Inequality

This page was built for publication: Simple linear flow decomposition algorithms on trees, circles, and augmented trees