Simple push-relabel algorithms for matroids and submodular flows

DOI10.1007/s13160-012-0076-yzbMath1254.90190MaRDI 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 optimization; matroid optimization; submodular flows; push-relabel algorithms

Mathematics Subject Classification ID

52B40: Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.)

90C27: Combinatorial optimization

05C21: Flows in graphs

Related Items

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