An efficient algorithm for minimum-weight bibranching

DOI10.1006/jctb.1998.1817zbMath0916.05065OpenAlexW1981881379MaRDI QIDQ1272485

Rudi A. Pendavingh, J. C. M. Keijsper

Publication date: 19 July 1999

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/jctb.1998.1817

zbMATH Keywords

directed path\(r\)-branchingbibranchingbipartite edge covers

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20)

Related Items (7)

Efficient many-to-Many point matching in one dimension ⋮ Shortest bibranchings and valuated matroid intersection ⋮ The b‐bibranching problem: TDI system, packing, and discrete convexity ⋮ An efficient scaling algorithm for the minimum weight bibranching problem ⋮ Equitable partitions into matchings and coverings in mixed graphs ⋮ Relationship of two formulations for shortest bibranchings ⋮ On packing connectors

Cites Work

• Efficient algorithms for finding minimum spanning trees in undirected and directed graphs
• Optimum matching forests I: Special weights
• Optimum matching forests II: General weights
• Optimum matching forests III: Facets of matching forest polyhedra
• Min-max Relations for Directed Graphs
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
• Fibonacci heaps and their uses in improved network optimization algorithms
• Optimum branchings
• On some techniques useful for solution of transportation network problems
• Unnamed Item
• Unnamed Item

This page was built for publication: An efficient algorithm for minimum-weight bibranching