An efficient scaling algorithm for the minimum weight bibranching problem

DOI10.1007/S00453-009-9377-1zbMATH Open1275.68157OpenAlexW2068452881MaRDI QIDQ652532FDOQ652532

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

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

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)

Cites Work

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

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)