Shortest bibranchings and valuated matroid intersection
From MaRDI portal
Publication:1926655
DOI10.1007/s13160-012-0072-2zbMath1254.90199MaRDI QIDQ1926655
Publication date: 28 December 2012
Published in: Japan Journal of Industrial and Applied Mathematics (Search for Journal in Brave)
Full work available at URL: http://hdl.handle.net/2433/167968
90C35: Programming involving graphs or networks
52B40: Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.)
90C27: Combinatorial optimization
Related Items
Notes on Equitable Partitions into Matching Forests in Mixed Graphs and into $b$-branchings in Digraphs, The b‐bibranching problem: TDI system, packing, and discrete convexity, Relationship of two formulations for shortest bibranchings, Equitable partitions into matchings and coverings in mixed graphs
Cites Work
- Convexity and Steinitz's exchange property
- Valuated matroids: A new look at the greedy algorithm
- Efficient algorithms for finding minimum spanning trees in undirected and directed graphs
- Valuated matroids
- An efficient algorithm for minimum-weight bibranching
- A constructive proof for the induction of M-convex functions through networks
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Submodular functions and optimization.
- M-Convex Function on Generalized Polymatroid
- Optimal Matching Forests and Valuated Delta-Matroids
- Polynomial-Time Approximation Schemes for Maximizing Gross Substitutes Utility under Budget Constraints
- A weighted matroid intersection algorithm
- Min-max Relations for Directed Graphs
- Matroid intersection algorithms
- AN ALGORITHM FOR FINDING AN OPTIMAL "INDEPENDENT ASSIGNMENT"
- Discrete Convex Analysis
- Valuated Matroid Intersection I: Optimality Criteria
- Valuated Matroid Intersection II: Algorithms
- On some techniques useful for solution of transportation network problems
- Matrices and matroids for systems analysis
- Total dual integrality of matching forest constraints
