{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,7]],"date-time":"2024-09-07T03:02:08Z","timestamp":1725678128011},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642299513"},{"type":"electronic","value":"9783642299520"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-29952-0_54","type":"book-chapter","created":{"date-parts":[[2012,5,3]],"date-time":"2012-05-03T06:14:09Z","timestamp":1336025649000},"page":"584-593","source":"Crossref","is-referenced-by-count":1,"title":["Submodular Minimization via Pathwidth"],"prefix":"10.1007","author":[{"given":"Hiroshi","family":"Nagamochi","sequence":"first","affiliation":[]}],"member":"297","reference":[{"issue":"1","key":"54_CR1","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1016\/0166-218X(89)90031-0","volume":"23","author":"S. Arnborg","year":"1989","unstructured":"Arnborg, S., Proskurowski, A.: Linear time algorithms for NP-hard problems restricted to partial k-trees. Discrete Applied Mathematics\u00a023(1), 11\u201324 (1989)","journal-title":"Discrete Applied Mathematics"},{"issue":"2","key":"54_CR2","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1007\/s00373-005-0627-y","volume":"22","author":"J. Bar\u00e1t","year":"2006","unstructured":"Bar\u00e1t, J.: Directed path-width and monotonicity in digraph searching. Graphs and Combinatorics\u00a022(2), 161\u2013172 (2006)","journal-title":"Graphs and Combinatorics"},{"unstructured":"Fleischer, L.K.: Recent progress in submodular function minimization. Optima, 1\u201311 (2000)","key":"54_CR3"},{"key":"54_CR4","volume-title":"Submodular Functions and Optimization","author":"S. Fujishige","year":"2005","unstructured":"Fujishige, S.: Submodular Functions and Optimization, 2nd edn. North-Holland, Amsterdam (2005)","edition":"2"},{"key":"54_CR5","doi-asserted-by":"publisher","first-page":"499","DOI":"10.1007\/BF02579273","volume":"1","author":"M. Gr\u00f6tschel","year":"1981","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., Schrijver, A.: The ellipsoid algorithm and its consequences in combinatorial optimization. Combinatorica\u00a01, 499\u2013513 (1981)","journal-title":"Combinatorica"},{"key":"54_CR6","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-97881-4","volume-title":"Geometric Algorithms and Combinatorial Optimization","author":"M. Gr\u00f6tschel","year":"1988","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., Schrijver, A.: Geometric Algorithms and Combinatorial Optimization. Springer, Heidelberg (1988)"},{"key":"54_CR7","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1007\/s10107-006-0084-2","volume":"112","author":"S. Iwata","year":"2008","unstructured":"Iwata, S.: Submodular function minimization. Math. Program.\u00a0112, 45\u201364 (2008)","journal-title":"Math. Program."},{"key":"54_CR8","doi-asserted-by":"publisher","first-page":"761","DOI":"10.1145\/502090.502096","volume":"48","author":"S. Iwata","year":"2001","unstructured":"Iwata, S., Fleischer, L., Fujishige, S.: A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions. J. ACM\u00a048, 761\u2013777 (2001)","journal-title":"J. ACM"},{"issue":"1","key":"54_CR9","doi-asserted-by":"publisher","first-page":"138","DOI":"10.1006\/jctb.2000.2031","volume":"82","author":"T. Johnson","year":"2001","unstructured":"Johnson, T., Robertson, N., Seymour, P.D., Thomas, R.: Directed tree-width. Journal of Combinatorial Theory Series B\u00a082(1), 138\u2013154 (2001)","journal-title":"Journal of Combinatorial Theory Series B"},{"key":"54_CR10","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1016\/0020-0190(92)90234-M","volume":"42","author":"N.G. Kinnersley","year":"1992","unstructured":"Kinnersley, N.G.: The vertex separation number of a graph equals its path-width. Information Processing Letters\u00a042, 345\u2013350 (1992)","journal-title":"Information Processing Letters"},{"key":"54_CR11","series-title":"Handbooks in Operations Research and Management Science","doi-asserted-by":"publisher","DOI":"10.1016\/S0927-0507(05)12007-6","volume-title":"Discrete Optimization","author":"S.T. McCormick","year":"2005","unstructured":"McCormick, S.T.: Submodular function minimization. In: Aardal, K., Nemhauser, G., Weismantel, R. (eds.) Discrete Optimization. Handbooks in Operations Research and Management Science, vol.\u00a012. Elsevier, Amsterdam (2005)"},{"key":"54_CR12","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\u00a056, 17\u201334 (2010)","journal-title":"Algorithmica"},{"key":"54_CR13","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. Proc. Lett.\u00a067, 239\u2013244 (1998)","journal-title":"Inf. Proc. Lett."},{"key":"54_CR14","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511721649","volume-title":"Algorithmic Aspects of Graph Connectivity","author":"H. Nagamochi","year":"2008","unstructured":"Nagamochi, H., Ibaraki, T.: Algorithmic Aspects of Graph Connectivity. Cambridge University Press, New York (2008)"},{"key":"54_CR15","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1007\/s10107-007-0189-2","volume":"118","author":"J.B. Orlin","year":"2009","unstructured":"Orlin, J.B.: A faster strongly polynomial time algorithm for submodular function minimization. Math. Program., Ser. A\u00a0118, 237\u2013251 (2009)","journal-title":"Math. Program., Ser. A"},{"key":"54_CR16","first-page":"3","volume":"82","author":"M. Queyranne","year":"1998","unstructured":"Queyranne, M.: Minimizing symmetric submodular functions. Math. Program.\u00a082, 3\u201312 (1998)","journal-title":"Math. Program."},{"issue":"1","key":"54_CR17","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/0095-8956(83)90079-5","volume":"35","author":"N. Robertson","year":"1983","unstructured":"Robertson, N., Seymour, P.: Graph minors. I. Excluding a forest. Journal of Combinatorial Theory, Series B\u00a035(1), 39\u201361 (1983)","journal-title":"Journal of Combinatorial Theory, Series B"},{"issue":"1","key":"54_CR18","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1016\/0095-8956(84)90013-3","volume":"36","author":"N. Robertson","year":"1984","unstructured":"Robertson, N., Seymour, P.: Graph minors III: Planar tree-width. J. Combin. Theory Ser. B\u00a036(1), 49\u201364 (1984)","journal-title":"J. Combin. Theory Ser. B"},{"issue":"2","key":"54_CR19","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1016\/j.jctb.2004.08.001","volume":"92","author":"N. Robertson","year":"2004","unstructured":"Robertson, N., Seymour, P.: Graph Minors. XX. Wagner\u2019s conjecture. J. Combin. Theory Ser. B\u00a092(2), 325\u2013335 (2004)","journal-title":"J. Combin. Theory Ser. B"},{"key":"54_CR20","doi-asserted-by":"publisher","first-page":"346","DOI":"10.1006\/jctb.2000.1989","volume":"80","author":"A. Schrijver","year":"2000","unstructured":"Schrijver, A.: A combinatorial algorithm minimizing submodular functions in strongly polynomial time. J. Combin. Theory Ser. B\u00a080, 346\u2013355 (2000)","journal-title":"J. Combin. Theory Ser. B"},{"key":"54_CR21","volume-title":"Combinatorial Optimization: Polyhedra and Efficiency","author":"A. Schrijver","year":"2003","unstructured":"Schrijver, A.: Combinatorial Optimization: Polyhedra and Efficiency. Springer, Berlin (2003)"},{"key":"54_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1007\/978-3-642-25870-1_30","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"H. Tamaki","year":"2011","unstructured":"Tamaki, H.: A Polynomial Time Algorithm for Bounded Directed Pathwidth. In: Kolman, P., Kratochv\u00edl, J. (eds.) WG 2011. LNCS, vol.\u00a06986, pp. 331\u2013342. Springer, Heidelberg (2011)"}],"container-title":["Lecture Notes in Computer Science","Theory and Applications of Models of Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-29952-0_54.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,4]],"date-time":"2021-05-04T11:23:06Z","timestamp":1620127386000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-29952-0_54"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642299513","9783642299520"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-29952-0_54","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}