An efficient scaling algorithm for the minimum weight bibranching problem

DOI10.1007/s00453-009-9377-1zbMath1275.68157OpenAlexW2068452881MaRDI QIDQ652532

Maxim A. Babenko

Publication date: 14 December 2011

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-009-9377-1

zbMATH Keywords

branchingprimal-dual algorithmbipartite edge coverblocking augmentationweight scaling

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

The b‐bibranching problem: TDI system, packing, and discrete convexity ⋮ Equitable partitions into matchings and coverings in mixed graphs ⋮ Relationship of two formulations for shortest bibranchings

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Efficient algorithms for finding minimum spanning trees in undirected and directed graphs
• How to make a digraph strongly connected
• An efficient algorithm for minimum-weight bibranching
• A data structure for dynamic trees
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• An Efficient Scaling Algorithm for the Minimum Weight Bibranching Problem
• Min-max Relations for Directed Graphs
• Faster scaling algorithms for general graph matching problems
• Faster Scaling Algorithms for Network Problems
• Optimum branchings