Simple push-relabel algorithms for matroids and submodular flows

DOI10.1007/S13160-012-0076-YMaRDI QIDQ1926643zbMATH OpenOpenAlexFDO

Authors András Frank, Zoltán Miklós

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

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

Recommendations

• Improved algorithms for submodular function minimization and submodular flow
• A push-relabel framework for submodular function minimization and applications to parametric optimization
• A fast cost scaling algorithm for submodular flow
• A Primal-Dual Algorithm for Submodular Flows
• A Push/Relabel framework for submodular flows and its definement for 0-1 submodular flows

Cites work

• scientific article; zbMATH DE number 446490 (Why is no real title available?)
• scientific article; zbMATH DE number 3580570 (Why is no real title available?)
• A Push/Relabel framework for submodular flows and its definement for 0-1 submodular flows
• A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
• A new approach to the maximum-flow problem
• A push-relabel framework for submodular function minimization and applications to parametric optimization
• Computing Maximal “Polymatroidal” Network Flows
• Connections in combinatorial optimization
• Finding feasible vectors of Edmonds-Giles polyhedra
• Flow Network Formulations of Polymatroid Optimization Problems
• Generalized polymatroids and submodular flows
• Matroids and the greedy algorithm
• Minimum partition of a matroid into independent subsets
• New algorithms for the intersection problem of submodular systems
• Submodular functions and optimization.
• Transversals and matroid partition

Cited in

(6)

• Single Commodity-Flow Algorithms for Lifts of Graphic and Co-graphic Matroids
• A Push/Relabel framework for submodular flows and its definement for 0-1 submodular flows
• Popular critical matchings in the many-to-many setting
• Fair integral submodular flows
• Degree Bounded Matroids and Submodular Flows
• Tree-compositions and orientations

This page was built for publication: Simple push-relabel algorithms for matroids and submodular flows

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1926643)