An efficient scaling algorithm for the minimum weight bibranching problem

DOI10.1007/S00453-009-9377-1MaRDI QIDQ652532zbMATH OpenOpenAlexFDO

Authors Maxim 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

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

Recommendations

• An Efficient Scaling Algorithm for the Minimum Weight Bibranching Problem
• An efficient algorithm for minimum-weight bibranching
• Relationship of two formulations for shortest bibranchings
• The \(b\)-branching problem in digraphs
• scientific article; zbMATH DE number 7378329

Cites work

• scientific article; zbMATH DE number 437545 (Why is no real title available?)
• scientific article; zbMATH DE number 3936534 (Why is no real title available?)
• A data structure for dynamic trees
• An Efficient Scaling Algorithm for the Minimum Weight Bibranching Problem
• An efficient algorithm for minimum-weight bibranching
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Efficient algorithms for finding minimum spanning trees in undirected and directed graphs
• Faster Scaling Algorithms for Network Problems
• Faster scaling algorithms for general graph matching problems
• How to make a digraph strongly connected
• Introduction to algorithms
• Min-max Relations for Directed Graphs
• Optimum branchings

Cited in

(4)

• Equitable partitions into matchings and coverings in mixed graphs
• Relationship of two formulations for shortest bibranchings
• An Efficient Scaling Algorithm for the Minimum Weight Bibranching Problem
• The b‐bibranching problem: TDI system, packing, and discrete convexity

This page was built for publication: An efficient scaling algorithm for the minimum weight bibranching problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q652532)