Decomposition of submodular functions

DOI10.1007/BF02579341zbMath0518.05059OpenAlexW2118220538MaRDI QIDQ1053717

William H. Cunningham

Publication date: 1983

Published in: Combinatorica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf02579341

zbMATH Keywords

decomposition algorithmssubmodular functionsunique decompositionhypergraph functionsnetwork functions

Mathematics Subject Classification ID

Hypergraphs (05C65) Circuits, networks (94C99) Combinatorial aspects of matroids and geometric lattices (05B35) Graph theory (05C99) Discrete mathematics in relation to computer science (68R99)

Related Items

On submodular function minimization, Minimum Cuts and Sparsification in Hypergraphs, On Submodular Search and Machine Scheduling, Tree-representation of set families and applications to combinatorial decompositions, The search value of a set, Decomposition of partial orders, Graph cuts with interacting edge weights: examples, approximations, and algorithms, Decomposition of 3-connected cubic graphs, Connectivity of submodular functions, Decomposition of k-ary relations, Set function optimization, Minimizing symmetric submodular functions, Unavoidable minors for connected 2-polymatroids, Some excluded-minor theorems for a class of polymatroids

Cites Work

• The ellipsoid method and its consequences in combinatorial optimization
• The Partial Order of a Polymatroid Extreme Point
• Multi-Terminal Network Flows
• A Combinatorial Decomposition Theory
• Decomposition of Directed Graphs
• Connectivity in Matroids
• Unnamed Item
• Unnamed Item
• Unnamed Item