A note on minimizing submodular functions

DOI10.1016/S0020-0190(98)00114-8MaRDI QIDQ293366zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• Minimizing symmetric submodular functions
• A faster strongly polynomial time algorithm for submodular function minimization
• scientific article; zbMATH DE number 910864
• scientific article; zbMATH DE number 876702
• Algorithms for symmetric submodular function minimization under hereditary constraints and generalizations

Cites work

• scientific article; zbMATH DE number 446490 (Why is no real title available?)
• scientific article; zbMATH DE number 910864 (Why is no real title available?)
• A Fast Algorithm for Optimally Increasing the Edge Connectivity
• A new approach to the maximum-flow problem
• Ancestor tree for arbitrary multi-terminal cut functions
• Augmenting Graphs to Meet Edge-Connectivity Requirements
• Canonical decompositions of symmetric submodular systems
• Computing Edge-Connectivity in Multigraphs and Capacitated Graphs
• Geometric algorithms and combinatorial optimization
• Multi-Terminal Network Flows
• On sparse subgraphs preserving connectivity properties
• Submodular functions and optimization

Cited in

(18)

• Submodular function minimization
• On minimizing symmetric set functions
• Minimum degree orderings
• A note on submodular function minimization by Chubanov's LP algorithm
• A note on Schrijver's submodular function minimization algorithm.
• scientific article; zbMATH DE number 910864 (Why is no real title available?)
• Polyhedral structure of submodular and posi-modular systems
• Finding submodularity hidden in symmetric difference
• Algorithms for symmetric submodular function minimization under hereditary constraints and generalizations
• Some results about the contractions and the pendant pairs of a submodular system
• A Compact Representation for Minimizers of k-Submodular Functions (Extended Abstract)
• Graph connectivity and its augmentation: Applications of MA orderings
• Posimodular function optimization
• scientific article; zbMATH DE number 5319970 (Why is no real title available?)
• On the complexity of submodular function minimisation on diamonds
• Minimizing submodular functions over families of sets
• Minimizing a monotone concave function with laminar covering constraints
• A note on the minimization of symmetric and general submodular functions

This page was built for publication: A note on minimizing submodular functions

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