Realizing symmetric set functions as hypergraph cut capacity

DOI10.1016/J.DISC.2016.02.010MaRDI QIDQ284712zbMATH OpenOpenAlexFDO

Authors Yutaro Yamaguchi

Publication date 18 May 2016

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disc.2016.02.010

zbMATH Keywords

cut capacityhypergraphsubmodular functionsymmetric set function

Mathematics Subject Classification ID

Hypergraphs (05C65) Symmetric functions and generalizations (05E05) Deterministic network models in operations research (90B10) Programming involving graphs or networks (90C35)

Recommendations

• Realization of set functions as cut functions of graphs and hypergraphs
• On minimizing symmetric set functions
• Covering symmetric supermodular functions by graphs
• Covering symmetric supermodular functions by uniform hypergraphs
• Cones of alternating and cut submodular set functions

Cites work

• A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
• A faster strongly polynomial time algorithm for submodular function minimization
• Computing Edge-Connectivity in Multigraphs and Capacitated Graphs
• Cones of alternating and cut submodular set functions
• Geometric algorithms and combinatorial optimization
• scientific article; zbMATH DE number 3645097 (Why is no real title available?)
• Minimizing symmetric submodular functions
• On the foundations of combinatorial theory I. Theory of M�bius Functions
• Realization of set functions as cut functions of graphs and hypergraphs
• Submodular functions and electrical networks
• The ellipsoid method and its consequences in combinatorial optimization

Cited in

(3)

• Realization of set functions as cut functions of graphs and hypergraphs
• Minimum cuts and sparsification in hypergraphs
• Hypergraph Cuts with General Splitting Functions

This page was built for publication: Realizing symmetric set functions as hypergraph cut capacity

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