Name
Abstract | ||
|---|---|---|
Let G be a graph and let A be its cutset-edge incidence matrix. We prove that the linear system 12Ax=1,x=0 is box totally dual integral (box-TDI) if and only ifG is a series-parallel graph; a by-product of this characterization is a structural description of a box-TDI system on matroids. Our results strengthen two previous theorems obtained respectively by Cornuejols, Fonlupt, and Naddef and by Mahjoub which assert that both polyhedra {x|12Ax=1,x=0} and {x|12Ax=1,1=x=0} are integral if G is series-parallel. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1016/j.dam.2008.05.001 | Discrete Applied Mathematics |
Keywords | Field | DocType |
structural description,cutset-edge incidence matrix,linear system,box-tdi system,previous theorem,series-parallel graph,polyhedron,cut,incidence matrix,graph cut,graph,traveling salesman problem,series parallel | Matroid,Discrete mathematics,Graph,Combinatorics,Linear system,Polyhedron,Travelling salesman problem,Incidence matrix,Mathematics | Journal |
Volume | Issue | ISSN |
157 | 1 | Discrete Applied Mathematics |
Citations | PageRank | References |
2 | 0.39 | 9 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Xujin Chen | 1 | 231 | 30.54 |
| Guoli Ding | 2 | 444 | 51.58 |
| Wenan Zang | 3 | 305 | 39.19 |