Circuit and bond polytopes on series parallel graphs

作     者：Borne, Sylvie Fouilhoux, Pierre Grappe, Roland Lacroix, Mathieu Pesneau, Pierre 

作者机构：Univ Paris 13 Sorbonne Paris Cite LIPN CNRSUMR 7030 F-93430 Villetaneuse France Univ Paris 06 Sorbonne Univ Lab LIP6 UMR 7606 F-75005 Paris France Univ Bordeaux IMB UMR 5251 INRIA Bordeaux Sud Quest F-33405 Talence France 

出 版 物：《DISCRETE OPTIMIZATION》 (离散优化)

年 卷 期：2015年第17卷

页      面：55-68页

核心收录：

学科分类：1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 070102[理学-计算数学] 0701[理学-数学] 

主　　题：Circuit polytope Series-parallel graph Extended formulation Bond polytope 

摘      要：In this paper, we describe the circuit polytope on series-parallel graphs. We first show the existence of a compact extended formulation. Though not being explicit, its construction process helps us to inductively provide the description in the original space. As a consequence, using the link between bonds and circuits in planar graphs, we also describe the bond polytope on series-parallel graphs. (C) 2015 Elsevier B.V. All rights reserved.