Realizing symmetric set functions as hypergraph cut capacity

DOI10.1016/j.disc.2016.02.010zbMath1336.05145OpenAlexW2342735818MaRDI QIDQ284712

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

hypergraphsubmodular functioncut capacitysymmetric set function

Mathematics Subject Classification ID

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

Related Items (2)

Minimum Cuts and Sparsification in Hypergraphs ⋮ Hypergraph Cuts with General Splitting Functions

Cites Work

• A faster strongly polynomial time algorithm for submodular function minimization
• Cones of alternating and cut submodular set functions
• The ellipsoid method and its consequences in combinatorial optimization
• Geometric algorithms and combinatorial optimization
• Minimizing symmetric submodular functions
• Submodular functions and electrical networks
• Realization of set functions as cut functions of graphs and hypergraphs
• A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
• A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions
• Computing Edge-Connectivity in Multigraphs and Capacitated Graphs
• [https://portal.mardi4nfdi.de/wiki/Publication:5731810 On the foundations of combinatorial theory I. Theory of M�bius Functions]
• Unnamed Item

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