Simple push-relabel algorithms for matroids and submodular flows

DOI10.1007/s13160-012-0076-yzbMath1254.90190OpenAlexW2149317019MaRDI QIDQ1926643

Zoltán Miklós, András Frank

Publication date: 28 December 2012

Published in: Japan Journal of Industrial and Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s13160-012-0076-y

zbMATH Keywords

combinatorial optimizationmatroid optimizationsubmodular flowspush-relabel algorithms

Mathematics Subject Classification ID

Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.) (52B40) Combinatorial optimization (90C27) Flows in graphs (05C21)

Related Items

Fair integral submodular flows, Popular critical matchings in the many-to-many setting, Tree-compositions and orientations

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finding feasible vectors of Edmonds-Giles polyhedra
• Generalized polymatroids and submodular flows
• New algorithms for the intersection problem of submodular systems
• A push-relabel framework for submodular function minimization and applications to parametric optimization
• A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
• Submodular functions and optimization.
• A Push/Relabel framework for submodular flows and its definement for 0-1 submodular flows
• A new approach to the maximum-flow problem
• Computing Maximal “Polymatroidal” Network Flows
• Flow Network Formulations of Polymatroid Optimization Problems
• Transversals and matroid partition
• Minimum partition of a matroid into independent subsets
• Matroids and the greedy algorithm