Polyhedral structure of submodular and posi-modular systems

DOI10.1016/S0166-218X(00)00246-8zbMath0969.90018OpenAlexW2057575931MaRDI QIDQ1841887

Hiroshi Nagamochi, Toshihide Ibaraki

Publication date: 18 February 2001

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0166-218x(00)00246-8

zbMATH Keywords

networkpolyhedraminimum cutsubmodular functioncoreposi-modular functionedge-connectivity augmentation

Mathematics Subject Classification ID

Deterministic network models in operations research (90B10) Connectivity (05C40)

Related Items

Minimum cost source location problem with local 3-vertex-connectivity requirements, Graph connectivity and its augmentation: Applications of MA orderings, Posimodular function optimization

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on minimizing submodular functions
• Generalized polymatroids and submodular flows
• Submodular functions and optimization
• Geometric algorithms and combinatorial optimization
• Deterministic \(\tilde O(nm)\) time edge-splitting in undirected graphs
• A laminarity property of the polyhedron described by a weakly posi-modular set function
• Cores of convex games
• An Algorithm for the Equipollent Resource Allocation Problem
• A Primal-Dual Algorithm for Submodular Flows
• A new approach to the maximum-flow problem
• The minimum augmentation of any graph to aK-edge-connected graph
• Augmenting Graphs to Meet Edge-Connectivity Requirements
• Computing Edge-Connectivity in Multigraphs and Capacitated Graphs