{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T13:28:19Z","timestamp":1740144499410,"version":"3.37.3"},"reference-count":18,"publisher":"EDP Sciences","issue":"3","license":[{"start":{"date-parts":[[2018,10,22]],"date-time":"2018-10-22T00:00:00Z","timestamp":1540166400000},"content-version":"vor","delay-in-days":113,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"FMJH Program Gaspard Monge in optimization and operation research"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["RAIRO-Oper. Res."],"accepted":{"date-parts":[[2018,5,2]]},"published-print":{"date-parts":[[2018,7]]},"abstract":"<jats:p>The <jats:italic>st<\/jats:italic>-bond polytope of a graph is the convex hull of the incidence vectors of its <jats:italic>st<\/jats:italic>-bonds, where an <jats:italic>st<\/jats:italic>-bond is a minimal <jats:italic>st<\/jats:italic>-cut. In this paper, we provide a linear description of the <jats:italic>st<\/jats:italic>-bond polytope on series-parallel graphs. We also show that the <jats:italic>st<\/jats:italic>-bond polytope is the intersection of the <jats:italic>st<\/jats:italic>-cut dominant and the bond polytope.<\/jats:p>","DOI":"10.1051\/ro\/2018035","type":"journal-article","created":{"date-parts":[[2018,5,8]],"date-time":"2018-05-08T08:11:07Z","timestamp":1525767067000},"page":"923-934","source":"Crossref","is-referenced-by-count":0,"title":["The <i>st<\/i>-bond polytope on series-parallel graphs"],"prefix":"10.1051","volume":"52","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7093-2175","authenticated-orcid":false,"given":"Roland","family":"Grappe","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8385-3890","authenticated-orcid":false,"given":"Mathieu","family":"Lacroix","sequence":"additional","affiliation":[]}],"member":"250","published-online":{"date-parts":[[2018,10,22]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","first-page":"466","DOI":"10.1137\/0606047","volume":"6","author":"Balas","year":"1985","journal-title":"SIAM J. Algebr. Discrete Methods"},{"key":"R2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/S0166-218X(98)00096-1","volume":"89","author":"Balas","year":"1998","journal-title":"Discrete Appl. Math."},{"key":"R3","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1007\/BF02592023","volume":"36","author":"Barahona","year":"1986","journal-title":"Math. Program."},{"key":"R4","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1016\/j.dam.2017.04.022","volume":"240","author":"Barbato","year":"2018","journal-title":"Discrete Appl. Math."},{"key":"R5","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1016\/j.disopt.2015.04.001","volume":"17","author":"Borne","year":"2015","journal-title":"Discrete Optim."},{"key":"R6","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1016\/S0167-5060(08)70877-X","volume":"8","author":"Calvillo","year":"1980","journal-title":"Ann. Discrete Math."},{"key":"R7","unstructured":"Chakrabarti A., \nFleischer L. and \nWeibel C., When the cut condition is enough: a complete characterization for multiflow problems in series-parallel networks, in \nProc. of the 44th Symposium on Theory of Computing STOC\u201912 \n(2012) 19\u201326."},{"key":"R8","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1016\/0022-247X(65)90125-3","volume":"10","author":"Duffin","year":"1965","journal-title":"J. Math. Anal. Appl."},{"key":"R9","unstructured":"Edmonds J., Submodular functions, matroids and certain polyhedra, in \nCombinatorial Structures and their Applications. \n(1970) 69\u201387."},{"key":"R10","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1016\/0890-5401(92)90041-D","volume":"98","author":"Eppstein","year":"1992","journal-title":"Inf. Comput."},{"key":"R11","doi-asserted-by":"crossref","first-page":"399","DOI":"10.4153\/CJM-1956-045-5","volume":"8","author":"Ford","year":"1956","journal-title":"Can. J. Math."},{"key":"R12","unstructured":"Fourier J.B.J., \nSolution d\u2019une question particuliere du calcul des in\u00e9galit\u00e9s. \nNouveau Bulletin des Sciences par la Soci\u00e9t\u00e9 philomatique de Paris \n(1826) 99\u2013100."},{"key":"R13","unstructured":"Garey M.R. and \nJohnson D.S., \nComputers and Intractability: A Guide to the Theory of NP-Completeness. \nFreeman, \nSan Francisco \n(1979)."},{"key":"R14","doi-asserted-by":"crossref","first-page":"704","DOI":"10.1137\/0205049","volume":"5","author":"Garey","year":"1976","journal-title":"SIAM J. Comput."},{"key":"R15","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1137\/0204019","volume":"4","author":"Hadlock","year":"1975","journal-title":"SIAM J. Comput."},{"key":"R16","doi-asserted-by":"crossref","first-page":"271","DOI":"10.4064\/fm-15-1-271-283","volume":"15","author":"Kuratowski","year":"1930","journal-title":"Fundam. Math."},{"key":"R17","unstructured":"Schrijver A., \nCombinatorial Optimization. \nSpringer-Verlag, \nBerlin, Heidelberg \n(2003)."},{"key":"R18","doi-asserted-by":"crossref","first-page":"441","DOI":"10.1007\/s10107-010-0373-7","volume":"124","author":"Skutella","year":"2010","journal-title":"Math. Program."}],"container-title":["RAIRO - Operations Research"],"original-title":[],"link":[{"URL":"https:\/\/www.rairo-ro.org\/10.1051\/ro\/2018035\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,8,28]],"date-time":"2020-08-28T18:58:16Z","timestamp":1598641096000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.rairo-ro.org\/10.1051\/ro\/2018035"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,7]]},"references-count":18,"journal-issue":{"issue":"3"},"alternative-id":["ro160245"],"URL":"https:\/\/doi.org\/10.1051\/ro\/2018035","relation":{},"ISSN":["0399-0559","1290-3868"],"issn-type":[{"type":"print","value":"0399-0559"},{"type":"electronic","value":"1290-3868"}],"subject":[],"published":{"date-parts":[[2018,7]]}}}