Submodular functions in graph theory

DOI10.1016/0012-365X(93)90158-PzbMATH Open0788.05078MaRDI QIDQ686469FDOQ686469

Authors: András Frank 

Publication date: 4 January 1994

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

Recommendations

• scientific article; zbMATH DE number 446490
• Variations for Lovász’ Submodular Ideas
• Graphic submodular function minimization: a graphic approach and applications
• Structures of subpartitions related to a submodular function minimization
• Connectivity of submodular functions

zbMATH Keywords

digraphsubmodular functions

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Structural characterization of families of graphs (05C75) Graph theory (05C99)

Cites Work

• On the Problem of Decomposing a Graph into n Connected Factors
• Title not available (Why is that?)
• On Representatives of Subsets
• Title not available (Why is that?)
• Title not available (Why is that?)
• Generalized polymatroids and submodular flows
• On two minimax theorems in graph
• Augmenting Graphs to Meet Edge-Connectivity Requirements
• Konstruktion aller n-fach kantenzusammenhaengenden Digraphen
• Ecken vom Innen- und Außengrad \(n\) in minimal \(n\)-fach kantenzusammenhängenden Digraphen
• Title not available (Why is that?)

Cited In (13)

• Submodular function minimization
• Bimonotone linear inequalities and sublattices of \(\mathbb R^n\)
• Variations for Lovász’ Submodular Ideas
• Highly connected hypergraphs containing no two edge-disjoint spanning connected subhypergraphs
• Sublattices of product spaces: Hulls, representations and counting
• On the \(L_{\infty}\)-norm of extreme points for crossing supermodular directed network LPs
• Ideal, non-extended formulations for disjunctive constraints admitting a network representation
• Approximating the smallest \(k\)-edge connected spanning subgraph by LP-rounding
• On the monotonicity of games generated by symmetric submodular functions.
• Structures of subpartitions related to a submodular function minimization
• On vertices of outdegree \(k\) in minimally \(k\)-arc-connected digraphs
• Connectivity of submodular functions
• On the complexity of submodular function minimisation on diamonds

This page was built for publication: Submodular functions in graph theory

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