版权所有:内蒙古大学图书馆 技术提供:维普资讯• 智图
内蒙古自治区呼和浩特市赛罕区大学西街235号 邮编: 010021
作者机构: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.