{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:41:49Z","timestamp":1740109309357,"version":"3.37.3"},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2022,1,29]],"date-time":"2022-01-29T00:00:00Z","timestamp":1643414400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,1,29]],"date-time":"2022-01-29T00:00:00Z","timestamp":1643414400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001840","name":"Icelandic Centre for Research","doi-asserted-by":"publisher","award":["152679-05"],"award-info":[{"award-number":["152679-05"]}],"id":[{"id":"10.13039\/501100001840","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001840","name":"Icelandic Centre for Research","doi-asserted-by":"crossref","award":["174484-05"],"award-info":[{"award-number":["174484-05"]}],"id":[{"id":"10.13039\/501100001840","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001700","name":"Ministry of Education, Culture, Sports, Science and Technology","doi-asserted-by":"publisher","award":["JP24106002"],"award-info":[{"award-number":["JP24106002"]}],"id":[{"id":"10.13039\/501100001700","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["JP25280004","JP26280001"],"award-info":[{"award-number":["JP25280004","JP26280001"]}],"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":["JP16K00001"],"award-info":[{"award-number":["JP16K00001"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001695","name":"Japan Science and Technology Corporation","doi-asserted-by":"crossref","award":["JPMJCR1402"],"award-info":[{"award-number":["JPMJCR1402"]}],"id":[{"id":"10.13039\/501100001695","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2022,4]]},"DOI":"10.1007\/s00453-021-00910-y","type":"journal-article","created":{"date-parts":[[2022,1,29]],"date-time":"2022-01-29T20:02:25Z","timestamp":1643486545000},"page":"1107-1131","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Posimodular Function Optimization"],"prefix":"10.1007","volume":"84","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5774-8437","authenticated-orcid":false,"given":"Magn\u00fas M.","family":"Halld\u00f3rsson","sequence":"first","affiliation":[]},{"given":"Toshimasa","family":"Ishii","sequence":"additional","affiliation":[]},{"given":"Kazuhisa","family":"Makino","sequence":"additional","affiliation":[]},{"given":"Kenjiro","family":"Takazawa","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,1,29]]},"reference":[{"key":"910_CR1","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1006\/jagm.2001.1203","volume":"42","author":"K Arata","year":"2002","unstructured":"Arata, K., Iwata, S., Makino, K., Fujishige, S.: Locating sources to meet flow demands in undirected networks. J. Algorithms 42, 54\u201368 (2002)","journal-title":"J. Algorithms"},{"key":"910_CR2","doi-asserted-by":"crossref","unstructured":"Chekuri, C., Ene, A.: Approximation algorithms for submodular multiway partition. In: IEEE 52nd Annual Symposium on Foundations of Computer Science, pp. 807\u2013816 (2011)","DOI":"10.1109\/FOCS.2011.34"},{"key":"910_CR3","unstructured":"Egres open problem list: http:\/\/lemon.cs.elte.hu\/egres\/open\/Maximizing_a_skew-supermodular_function"},{"key":"910_CR4","doi-asserted-by":"publisher","first-page":"1133","DOI":"10.1137\/090779346","volume":"40","author":"U Feige","year":"2011","unstructured":"Feige, U., Mirrokni, V.S., Vondr\u00e1k, J.: Maximizing non-monotone submodular functions. SIAM J. Comput. 40, 1133\u20131153 (2011)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"910_CR5","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1137\/0405003","volume":"5","author":"A Frank","year":"1992","unstructured":"Frank, A.: Augmenting graphs to meet edge-connectivity requirements. SIAM J. Discrete Math. 5(1), 25\u201353 (1992)","journal-title":"SIAM J. Discrete Math."},{"issue":"1\u20132","key":"910_CR6","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1016\/S0166-218X(99)00198-5","volume":"100","author":"S Fujishige","year":"2000","unstructured":"Fujishige, S.: A laminarity property of the polyhedron described by a weakly posi-modular set function. Discrete Appl. Math. 100(1\u20132), 123\u2013126 (2000)","journal-title":"Discrete Appl. Math."},{"key":"910_CR7","doi-asserted-by":"crossref","unstructured":"Halld\u00f3rsson, M.M., Ishii, T., Makino, K., Takazawa, K.: Posimodular function optimization. In: Proceedings of 15th International Symposium on Algorithms and Data Structures (WADS), pp. 437\u2013448. Springer (2017)","DOI":"10.1007\/978-3-319-62127-2_37"},{"issue":"1","key":"910_CR8","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1142\/S1793830910000474","volume":"2","author":"T Ishii","year":"2010","unstructured":"Ishii, T., Makino, K.: Posi-modular systems with modulotone requirements under permutation constraints. Discrete Math. Algorithms Appl. 2(1), 61\u201376 (2010)","journal-title":"Discrete Math. Algorithms Appl."},{"key":"910_CR9","doi-asserted-by":"publisher","first-page":"427","DOI":"10.1080\/1055-6780309510593","volume":"18","author":"H Ito","year":"2003","unstructured":"Ito, H., Makino, K., Arata, K., Honami, S., Itatsu, Y., Fujishige, S.: Source location problem with flow requirements in directed networks. Optim. Methods Softw. 18, 427\u2013435 (2003)","journal-title":"Optim. Methods Softw."},{"issue":"3","key":"910_CR10","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1002\/net.3230030306","volume":"3","author":"EL Lawler","year":"1973","unstructured":"Lawler, E.L.: Cutsets and partitions of hypergraphs. Networks 3(3), 275\u2013285 (1973)","journal-title":"Networks"},{"key":"910_CR11","doi-asserted-by":"crossref","unstructured":"Lee, Y.T., Sidford, A., Wong, S.C.: A faster cutting plane method and its implications for combinatorial and convex optimization. In: IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS), pp. 1049\u20131065. IEEE Computer Society (2015)","DOI":"10.1109\/FOCS.2015.68"},{"key":"910_CR12","doi-asserted-by":"publisher","first-page":"278","DOI":"10.1016\/j.ic.2012.10.016","volume":"222","author":"D Lokshtanov","year":"2013","unstructured":"Lokshtanov, D., Marx, D.: Clustering with local restrictions. Inf. Comput. 222, 278\u2013292 (2013)","journal-title":"Inf. Comput."},{"issue":"4","key":"910_CR13","first-page":"199","volume":"47","author":"H Nagamochi","year":"2004","unstructured":"Nagamochi, H.: Graph algorithms for network connectivity problems. J. Oper. Res. Soc. Japan 47(4), 199\u2013223 (2004)","journal-title":"J. Oper. Res. Soc. Japan"},{"issue":"1","key":"910_CR14","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1007\/s00453-008-9239-2","volume":"56","author":"H Nagamochi","year":"2010","unstructured":"Nagamochi, H.: Minimum degree orderings. Algorithmica 56(1), 17\u201334 (2010)","journal-title":"Algorithmica"},{"issue":"5","key":"910_CR15","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1016\/S0020-0190(98)00114-8","volume":"67","author":"H Nagamochi","year":"1998","unstructured":"Nagamochi, H., Ibaraki, T.: A note on minimizing submodular functions. Inf. Process. Lett. 67(5), 239\u2013244 (1998)","journal-title":"Inf. Process. Lett."},{"issue":"1\u20133","key":"910_CR16","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1016\/S0166-218X(00)00246-8","volume":"107","author":"H Nagamochi","year":"2000","unstructured":"Nagamochi, H., Ibaraki, T.: Polyhedral structure of submodular and posi-modular systems. Discrete Appl. Math. 107(1\u20133), 165\u2013189 (2000)","journal-title":"Discrete Appl. Math."},{"issue":"2","key":"910_CR17","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1023\/A:1011409332456","volume":"5","author":"H Nagamochi","year":"2001","unstructured":"Nagamochi, H., Shiraki, T., Ibaraki, T.: Augmenting a submodular and posi-modular set function by a multigraph. J. Combin. Optim. 5(2), 175\u2013212 (2001)","journal-title":"J. Combin. Optim."},{"key":"910_CR18","doi-asserted-by":"publisher","first-page":"858","DOI":"10.1137\/060663970","volume":"23","author":"M Sakashita","year":"2009","unstructured":"Sakashita, M., Makino, K., Nagamochi, H., Fujishige, S.: Minimum transversals in posi-modular systems. SIAM J. Discrete Math. 23, 858\u2013871 (2009)","journal-title":"SIAM J. Discrete Math."},{"key":"910_CR19","doi-asserted-by":"crossref","unstructured":"Svitkina, Z., Tardos, \u00c9.: Min\u2013max multiway cut. In: Approximation, Randomization, and Combinatorial Optimization, pp. 207\u2013218 (2004)","DOI":"10.1007\/978-3-540-27821-4_19"},{"key":"910_CR20","first-page":"863","volume":"J81\u2013A","author":"H Tamura","year":"1998","unstructured":"Tamura, H., Sugawara, H., Sengoku, M., Shinoda, S.: Plural cover problem on undirected flow networks. IEICE Trans. J81\u2013A, 863\u2013869 (1998). ((in Japanese))","journal-title":"IEICE Trans."},{"key":"910_CR21","doi-asserted-by":"crossref","unstructured":"van\u00a0den Heuvel, J., Johnson, M.: The external network problem with edge- or arc-connectivity requirements. In: Combinatorial and Algorithmic Aspects of Networking, Lecture Notes in Computer Science, vol. 3405, pp. 114\u2013126. Springer (2004)","DOI":"10.1007\/11527954_11"},{"key":"910_CR22","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1016\/0022-0000(87)90038-9","volume":"35","author":"T Watanabe","year":"1987","unstructured":"Watanabe, T., Nakamura, A.: Edge-connectivity augmentation problems. J. Comput. Syst. Sci. 35, 96\u2013144 (1987)","journal-title":"J. Comput. Syst. Sci."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00910-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-021-00910-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00910-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,3,16]],"date-time":"2022-03-16T15:09:44Z","timestamp":1647443384000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-021-00910-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,1,29]]},"references-count":22,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2022,4]]}},"alternative-id":["910"],"URL":"https:\/\/doi.org\/10.1007\/s00453-021-00910-y","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2022,1,29]]},"assertion":[{"value":"17 April 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 November 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 January 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}