Finding feasible vectors of Edmonds-Giles polyhedra

DOI10.1016/0095-8956(84)90029-7zbMath0544.05016OpenAlexW2000317174WikidataQ56987202 ScholiaQ56987202MaRDI QIDQ796541

András Frank

Publication date: 1984

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

Full work available at URL: https://doi.org/10.1016/0095-8956(84)90029-7

zbMATH Keywords

intersecting familiessubmodular functionsEdmonds-Giles polyhedroninteger valued modular function

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35) Graph theory (05C99) Algorithms in computer science (68W99)

Related Items

A Mazur-Orlicz type theorem for submodular set functions, A fast cost scaling algorithm for submodular flow, An out-of-kilter method for submodular flows, A capacity scaling algorithm for convex cost submodular flows, Optimum partitioning into intersections of ring families, Sandwich theorems for set functions, Generalized polymatroids and submodular flows, Optimization over the polyhedron determined by a submodular function on a co-intersecting family, Directed submodularity, ditroids and directed submodular flows, An application of submodular flows, Gradient methods of maximization of convex functions on discrete structures, Simple push-relabel algorithms for matroids and submodular flows, Improved bound for the Carathéodory rank of the bases of a matroid, A dual algorithm for submodular flow problems, A cost-scaling algorithm for \(0-1\) submodular flows, A capacity scaling algorithm for M-convex submodular flow, Duality for balanced submodular flows, Integral infeasibility and testing total dual integrality, A cost-scaling algorithm for minimum-cost node-capacitated multiflow problem, A combinatorial algorithm minimizing submodular functions in strongly polynomial time.

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Testing membership in matroid polyhedra
• On total dual integrality
• How to make a digraph strongly connected
• Total dual integrality and b-matchings
• The ellipsoid method and its consequences in combinatorial optimization
• Matroid Intersection
• A Primal-Dual Algorithm for Submodular Flows
• Minimum cost flow with set-constraints
• A weighted matroid intersection algorithm
• Minimization of Some Nonlinear Functions over Polymatroidal Network Flows
• Computing Maximal “Polymatroidal” Network Flows
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
• ALGORITHMS FOR SOLVING THE INDEPENDENT-FLOW PROBLEMS
• A Minimax Theorem for Directed Graphs
• An Algorithm for Submodular Functions on Graphs