A note on minimizing submodular functions

DOI10.1016/S0020-0190(98)00114-8zbMath1339.90285OpenAlexW1975172458MaRDI QIDQ293366

Hiroshi Nagamochi, Toshihide Ibaraki

Publication date: 9 June 2016

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: http://www.sciencedirect.com/science/article/pii/S0020019098001148?np=y

zbMATH Keywords

algorithmscomputational complexitycombinatorial problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27)

Related Items

Some Results about the Contractions and the Pendant Pairs of a Submodular System, Minimum degree orderings, A note on the minimization of symmetric and general submodular functions, Minimizing a monotone concave function with laminar covering constraints, Graph connectivity and its augmentation: Applications of MA orderings, Submodular function minimization, Posimodular function optimization, Polyhedral structure of submodular and posi-modular systems

Cites Work

• Unnamed Item
• Unnamed Item
• Canonical decompositions of symmetric submodular systems
• Ancestor tree for arbitrary multi-terminal cut functions
• Submodular functions and optimization
• Geometric algorithms and combinatorial optimization
• A new approach to the maximum-flow problem
• Multi-Terminal Network Flows
• Augmenting Graphs to Meet Edge-Connectivity Requirements
• Computing Edge-Connectivity in Multigraphs and Capacitated Graphs
• On sparse subgraphs preserving connectivity properties
• A Fast Algorithm for Optimally Increasing the Edge Connectivity