A Compact Representation for Minimizers of k-Submodular Functions (Extended Abstract)

DOI10.1007/978-3-319-45587-7_33zbMath1455.90134OpenAlexW2512284356MaRDI QIDQ2835693

Hiroshi Hirai, Taihei Oki

Publication date: 30 November 2016

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-45587-7_33

zbMATH Keywords

\(k\)-submodular functionBirkhoff representation theoremPotts energy functionposet with inconsistent pairs

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Proceedings, conferences, collections, etc. pertaining to operations research and mathematical programming (90-06) Algebraic aspects of posets (06A11) Semilattices (06A12) Computational methods for problems pertaining to ordered structures (06-08)

Related Items (1)

A compact representation for minimizers of \(k\)-submodular functions

Cites Work

• Generating all maximal models of a Boolean expression
• Geodesics in CAT(0) cubical complexes
• Median graphs, parallelism and posets
• Petri nets, event structures and domains. I
• Network flow and 2-satisfiability
• Half-integrality, LP-branching, and FPT Algorithms
• On $k$-Submodular Relaxation
• Towards Minimizing k-Submodular Functions
• On the structure of all minimum cuts in a network and applications
• The Complexity of Multiterminal Cuts
• The Power of Linear Programming for General-Valued CSPs
• Max flows in O(nm) time, or better
• Medians and Betweenness
• Matrices and matroids for systems analysis

This page was built for publication: A Compact Representation for Minimizers of k-Submodular Functions (Extended Abstract)