{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T06:52:47Z","timestamp":1725864767405},"publisher-location":"Cham","reference-count":16,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319455860"},{"type":"electronic","value":"9783319455877"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-319-45587-7_33","type":"book-chapter","created":{"date-parts":[[2016,9,9]],"date-time":"2016-09-09T00:01:21Z","timestamp":1473379281000},"page":"381-392","source":"Crossref","is-referenced-by-count":1,"title":["A Compact Representation for Minimizers of k-Submodular Functions (Extended Abstract)"],"prefix":"10.1007","author":[{"given":"Hiroshi","family":"Hirai","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Taihei","family":"Oki","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,9,10]]},"reference":[{"key":"33_CR1","unstructured":"Ando, K., Fujishige, S.: $$\\sqcup ,\\sqcap $$ -closed families and signed posets. Technical report, Forschungsinstitut f\u00fcr Diskrete Mathematik, Universit\u00e4t Bonn (1994)"},{"issue":"1","key":"33_CR2","doi-asserted-by":"crossref","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.: Geodesics in CAT(0) cubical complexes. Adv. Appl. Math. 48(1), 142\u2013163 (2012)","journal-title":"Adv. Appl. Math."},{"issue":"1\u20133","key":"33_CR3","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1016\/0012-365X(93)90140-O","volume":"111","author":"JP Barth\u00e9lemy","year":"1993","unstructured":"Barth\u00e9lemy, J.P., Constantin, J.: Median graphs, parallelism and posets. Discrete Math. 111(1\u20133), 49\u201363 (1993)","journal-title":"Discrete Math."},{"issue":"4","key":"33_CR4","doi-asserted-by":"crossref","first-page":"864","DOI":"10.1137\/S0097539792225297","volume":"23","author":"E Dahlhaus","year":"1994","unstructured":"Dahlhaus, E., Johnson, D.S., Papadimitriou, C.H., Seymour, P.D., Yannakakis, M.: The complexity of multiterminal cuts. SIAM J. Comput. 23(4), 864\u2013894 (1994)","journal-title":"SIAM J. Comput."},{"key":"33_CR5","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1007\/BF01240738","volume":"11","author":"T Feder","year":"1994","unstructured":"Feder, T.: Network flow and 2-satisfiability. Algorithmica 11, 291\u2013319 (1994)","journal-title":"Algorithmica"},{"key":"33_CR6","doi-asserted-by":"crossref","unstructured":"Gridchyn, I., Kolmogorov, V.: Potts model, parametric maxflow and $$k$$ -submodular functions. In: IEEE International Conference on Computer Vision (ICCV 2013), pp. 2320\u20132327 (2013)","DOI":"10.1109\/ICCV.2013.288"},{"key":"33_CR7","doi-asserted-by":"crossref","unstructured":"Hirai, H., Iwamasa, Y.: On $$k$$ -submodular relaxation. SIAM J. Discrete Math. (2016, to appear)","DOI":"10.1137\/15M101926X"},{"key":"33_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"451","DOI":"10.1007\/978-3-642-32147-4_40","volume-title":"Combinatorial Optimization","author":"A Huber","year":"2012","unstructured":"Huber, A., Kolmogorov, V.: Towards minimizing k-submodular functions. In: Mahjoub, A.R., Markakis, V., Milis, I., Paschos, V.T. (eds.) ISCO 2012. LNCS, vol. 7422, pp. 451\u2013462. Springer, Heidelberg (2012)"},{"key":"33_CR9","doi-asserted-by":"crossref","unstructured":"Iwata, Y., Wahlstr\u00f6m, M., Yoshida, Y.: Half-integrality, LP-branching and FPT algorithms. SIAM J. Comput. (2016, to appear)","DOI":"10.1137\/140962838"},{"key":"33_CR10","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1016\/S0020-0190(00)00023-5","volume":"74","author":"DJ Kavvadias","year":"2000","unstructured":"Kavvadias, D.J., Sideri, M., Stavropoulos, E.C.: Generating all maximal models of a Boolean expression. Inf. Process. Lett. 74, 157\u2013162 (2000)","journal-title":"Inf. Process. Lett."},{"key":"33_CR11","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1137\/130945648","volume":"44","author":"V Kolmogorov","year":"2015","unstructured":"Kolmogorov, V., Thapper, J., \u017divn\u00fd, S.: The power of linear programming for general-valued CSPs. SIAM J. Comput. 44, 1\u201336 (2015)","journal-title":"SIAM J. Comput."},{"key":"33_CR12","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-03994-2","volume-title":"Analysis, Matrices and Matroids for Systems","author":"K Murota","year":"2010","unstructured":"Murota, K.: Analysis, Matrices and Matroids for Systems. Springer, Berlin (2010)"},{"key":"33_CR13","doi-asserted-by":"crossref","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.: Petri nets, event structures and domains, part I. Theoret. Comput. Sci. 13, 85\u2013108 (1981)","journal-title":"Theoret. Comput. Sci."},{"key":"33_CR14","doi-asserted-by":"crossref","unstructured":"Orlin, J.B.: Max flows in $${\\rm O}(nm)$$ time, or better. In: Proceedings of the 45th Annual ACM Symposium on Theory of Computing (STOC 2013), pp. 765\u2013774 (2013)","DOI":"10.1145\/2488608.2488705"},{"key":"33_CR15","series-title":"Mathematical Programming Studies","doi-asserted-by":"crossref","first-page":"8","DOI":"10.1007\/BFb0120902","volume-title":"Combinatorial Optimization II","author":"JC Picard","year":"1980","unstructured":"Picard, J.C., Queyranne, M.: On the structure of all minimum cuts in a network and applications. In: Rayward-Smith, V.J. (ed.) Combinatorial Optimization II. Mathematical Programming Studies, vol. 13, pp. 8\u201316. Springer, Berlin (1980)"},{"issue":"5","key":"33_CR16","doi-asserted-by":"crossref","first-page":"801","DOI":"10.1090\/S0002-9939-1954-0064749-7","volume":"5","author":"M Sholander","year":"1954","unstructured":"Sholander, M.: Medians and betweenness. Proc. Am. Math. Soc. 5(5), 801\u2013807 (1954)","journal-title":"Proc. Am. Math. Soc."}],"container-title":["Lecture Notes in Computer Science","Combinatorial Optimization"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-45587-7_33","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2017,6,24]],"date-time":"2017-06-24T18:18:26Z","timestamp":1498328306000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-45587-7_33"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783319455860","9783319455877"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-45587-7_33","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]}}}