{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:20:00Z","timestamp":1740122400193,"version":"3.37.3"},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2017,6,3]],"date-time":"2017-06-03T00:00:00Z","timestamp":1496448000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2017,6,3]],"date-time":"2017-06-03T00:00:00Z","timestamp":1496448000000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["25280004","26330023"],"award-info":[{"award-number":["25280004","26330023"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["26280004"],"award-info":[{"award-number":["26280004"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2018,10]]},"DOI":"10.1007\/s10878-017-0142-0","type":"journal-article","created":{"date-parts":[[2017,6,3]],"date-time":"2017-06-03T13:16:05Z","timestamp":1496495765000},"page":"709-741","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["A compact representation for minimizers of k-submodular functions"],"prefix":"10.1007","volume":"36","author":[{"given":"Hiroshi","family":"Hirai","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6862-9484","authenticated-orcid":false,"given":"Taihei","family":"Oki","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,6,3]]},"reference":[{"key":"142_CR1","unstructured":"Ando K, Fujishige S (1994) $$\\sqcup ,\\sqcap $$-closed families and signed posets. Technical report, Forschungsinstitut f\u00fcr Diskrete Mathematik, Universit\u00e4t Bonn"},{"key":"142_CR2","doi-asserted-by":"publisher","first-page":"142","DOI":"10.1016\/j.aam.2011.06.004","volume":"48","author":"F Ardila","year":"2012","unstructured":"Ardila F, Owen M, Sullivant S (2012) Geodesics in CAT(0) cubical complexes. Adv Appl Math 48:142\u2013163","journal-title":"Adv Appl Math"},{"key":"142_CR3","unstructured":"Babenko MA, Karzanov AV (2012) On weighted multicommodity flows in directed networks. \n                    arXiv:1212.0224v1"},{"issue":"1\u20133","key":"142_CR4","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1016\/0012-365X(93)90140-O","volume":"111","author":"J-P Barth\u00e9lemy","year":"1993","unstructured":"Barth\u00e9lemy J-P, Constantin J (1993) Median graphs, parallelism and posets. Discret Math 111(1\u20133):49\u201363","journal-title":"Discret Math"},{"key":"142_CR5","doi-asserted-by":"publisher","first-page":"626","DOI":"10.1137\/S0895480193242591","volume":"10","author":"A Bouchet","year":"1997","unstructured":"Bouchet A (1997) Multimatroids I. Coverings by independent sets. SIAM J Discret Math 10:626\u2013646","journal-title":"SIAM J Discret Math"},{"key":"142_CR6","doi-asserted-by":"publisher","first-page":"715","DOI":"10.1137\/110837760","volume":"41","author":"V Chepoi","year":"2012","unstructured":"Chepoi V (2012) Nice labeling problem for event structures: a counterexample. SIAM J Comput 41:715\u2013727","journal-title":"SIAM J Comput"},{"key":"142_CR7","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1007\/BF01240738","volume":"11","author":"T Feder","year":"1994","unstructured":"Feder T (1994) Network flow and 2-satisfiability. Algorithmica 11:291\u2013319","journal-title":"Algorithmica"},{"key":"142_CR8","unstructured":"Fujishige S (1995) Submodular functions and combinatorial optimization (in Japanese). In: Proceedings of the 7th research association of mathematical programming symposium (RAMP 1995), pp 13\u201328"},{"key":"142_CR9","doi-asserted-by":"crossref","unstructured":"Gridchyn I, Kolmogorov V (2013) Potts model, parametric maxflow and $$k$$-submodular functions. In: Proceedings of the IEEE international conference on computer vision (ICCV 2013), pp 2320\u20132327","DOI":"10.1109\/ICCV.2013.288"},{"issue":"2","key":"142_CR10","first-page":"149","volume":"53","author":"H Hirai","year":"2010","unstructured":"Hirai H (2010) A note on multiflow locking theorem. J Op Res Soc Jpn 53(2):149\u2013156","journal-title":"J Op Res Soc Jpn"},{"key":"142_CR11","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.disopt.2015.07.001","volume":"18","author":"H Hirai","year":"2015","unstructured":"Hirai H (2015) L-extendable functions and a proximity scaling algorithm for minimum cost multiflow problem. Discret Optim 18:1\u201337","journal-title":"Discret Optim"},{"key":"142_CR12","doi-asserted-by":"publisher","first-page":"1726","DOI":"10.1137\/15M101926X","volume":"30","author":"H Hirai","year":"2016","unstructured":"Hirai H, Iwamasa Y (2016) On $$k$$-submodular relaxation. SIAM J Discret Math 30:1726\u20131736","journal-title":"SIAM J Discret Math"},{"key":"142_CR13","doi-asserted-by":"crossref","unstructured":"Hirai H, Oki T (2016) A compact representation for minimizers of $$k$$-submodular functions (extended abstract). In: Proceedings of the 4th international symposium on combinatorial optimization (ISCO 2016), volume 9849 of lecture notes in computer science, Springer, Cham, pp 381\u2013392","DOI":"10.1007\/978-3-319-45587-7_33"},{"key":"142_CR14","doi-asserted-by":"crossref","unstructured":"Huber A, Kolmogorov V (2012) Towards minimizing $$k$$-submodular functions. In: Proceedings of the 2nd international symposium on combinatorial optimization (ISCO 2012), Volume 7422 of lecture notes in computer science, Springer, Heidelberg, pp 451\u2013462","DOI":"10.1007\/978-3-642-32147-4_40"},{"key":"142_CR15","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1007\/PL00009811","volume":"18","author":"T Ibaraki","year":"1998","unstructured":"Ibaraki T, Karzanov AV, Nagamochi H (1998) A fast algorithm for finding a maximum free multiflow in an inner eulerian network and some generalizations. Combinatorica 18:61\u201383","journal-title":"Combinatorica"},{"key":"142_CR16","doi-asserted-by":"publisher","unstructured":"Iwamasa Y (2017) On a general framework for network representability in discrete optimization. J Comb Optim. doi:\n                    10.1007\/s10878-017-0136-y","DOI":"10.1007\/s10878-017-0136-y"},{"key":"142_CR17","doi-asserted-by":"crossref","unstructured":"Iwata S, Tanigawa S, Yoshida Y (2016a) Improved approximation algorithms for $$k$$-submodular function maximization. In: Proceedings of the 27th annual ACM-SIAM symposium on discrete algorithms (SODA 2016), pp 404\u2013413","DOI":"10.1137\/1.9781611974331.ch30"},{"key":"142_CR18","doi-asserted-by":"crossref","unstructured":"Iwata Y, Wahlstr\u00f6m M, Yoshida Y (2016b) Half-integrality, LP-branching and FPT algorithms. SIAM J Comput 45:1377\u20131411","DOI":"10.1137\/140962838"},{"key":"142_CR19","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1016\/S0020-0190(00)00023-5","volume":"74","author":"DJ Kavvadias","year":"2000","unstructured":"Kavvadias DJ, Sideri M, Stavropoulos EC (2000) Generating all maximal models of a Boolean expression. Inf Process Lett 74:157\u2013162","journal-title":"Inf Process Lett"},{"key":"142_CR20","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/130945648","volume":"44","author":"V Kolmogorov","year":"2015","unstructured":"Kolmogorov V, Thapper J, \u017divn\u00fd S (2015) The power of linear programming for general-valued CSPs. SIAM J Comput 44:1\u201336","journal-title":"SIAM J Comput"},{"key":"142_CR21","doi-asserted-by":"crossref","unstructured":"Kovtun I (2003) Partial optimal labeling search for a NP-hard subclass of (max,+) problems. In: Proceedings of the 25th German association for pattern recognition (DAGM 2003), volume 2781 of lecture notes in computer science, Springer, Heidelberg, pp 402\u2013409","DOI":"10.1007\/978-3-540-45243-0_52"},{"key":"142_CR22","volume-title":"Matrices and matroids for systems analysis","author":"K Murota","year":"2000","unstructured":"Murota K (2000) Matrices and matroids for systems analysis. Springer, Berlin"},{"key":"142_CR23","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1016\/0304-3975(81)90112-2","volume":"13","author":"M Nielsen","year":"1981","unstructured":"Nielsen M, Plotkin G, Winskel G (1981) Petri nets, event structures and domains, part I. Theor Comput Sci 13:85\u2013108","journal-title":"Theor Comput Sci"},{"key":"142_CR24","unstructured":"Orlin JB (2013) Max flows in $$\\text{O}(nm)$$ time, or better. In: Proceedings of the 45th annual ACM Symposium on theory of computing (STOC 2013), pp 765\u2013774"},{"key":"142_CR25","doi-asserted-by":"publisher","unstructured":"Picard J-C, Queyranne M (1980) On the structure of all minimum cuts in a network and applications. In: Rayward-Smith VJ (ed) Combinatorial optimization II, volume 13 of mathematical programming studies. Springer, Berlin, pp 8\u201316. doi:\n                    10.1007\/BFb0120902","DOI":"10.1007\/BFb0120902"},{"key":"142_CR26","doi-asserted-by":"publisher","first-page":"324","DOI":"10.1016\/0097-3165(93)90052-A","volume":"62","author":"V Reiner","year":"1993","unstructured":"Reiner V (1993) Signed posets. J Comb Theory Ser A 62:324\u2013360","journal-title":"J Comb Theory Ser A"},{"key":"142_CR27","doi-asserted-by":"crossref","unstructured":"Scharstein D, Szeliski R (2003) High-accuracy stereo depth maps using structured light. In: Proceedings of the 2003 IEEE computer society conference on computer vision and pattern recognition (CVPR 2003), pp 195\u2013202","DOI":"10.1109\/CVPR.2003.1211354"},{"key":"142_CR28","doi-asserted-by":"crossref","unstructured":"Scharstein D, Szeliski R, Zabih R (2001) A taxonomy and evaluation of dense two-frame stereo correspondence algorithms. In: Proceedings of the IEEE workshop on stereo and multi-baseline vision (SMBV 2001), pp 131\u2013140","DOI":"10.1109\/SMBV.2001.988771"},{"issue":"5","key":"142_CR29","doi-asserted-by":"publisher","first-page":"801","DOI":"10.1090\/S0002-9939-1954-0064749-7","volume":"5","author":"M Sholander","year":"1954","unstructured":"Sholander M (1954) Medians and betweenness. Proc Am Math Soc 5(5):801\u2013807","journal-title":"Proc Am Math Soc"},{"key":"142_CR30","unstructured":"Squire MB (1995) Enumerating the ideals of a poset. Technical report, North Carolina State University"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-017-0142-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-017-0142-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-017-0142-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,17]],"date-time":"2020-05-17T12:48:24Z","timestamp":1589719704000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-017-0142-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,6,3]]},"references-count":30,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2018,10]]}},"alternative-id":["142"],"URL":"https:\/\/doi.org\/10.1007\/s10878-017-0142-0","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"type":"print","value":"1382-6905"},{"type":"electronic","value":"1573-2886"}],"subject":[],"published":{"date-parts":[[2017,6,3]]},"assertion":[{"value":"3 June 2017","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}