File Download
There are no files associated with this item.
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1016/j.dam.2008.05.001
- Scopus: eid_2-s2.0-56349148697
- WOS: WOS:000261861700011
- Find via
Supplementary
- Citations:
- Appears in Collections:
Article: The box-TDI system associated with 2-edge connected spanning subgraphs
Title | The box-TDI system associated with 2-edge connected spanning subgraphs | ||||||
---|---|---|---|---|---|---|---|
Authors | |||||||
Keywords | Box total dual integrality Cut Graph Polyhedron Traveling salesman problem | ||||||
Issue Date | 2009 | ||||||
Publisher | Elsevier BV. The Journal's web site is located at http://www.elsevier.com/locate/dam | ||||||
Citation | Discrete Applied Mathematics, 2009, v. 157 n. 1, p. 118-125 How to Cite? | ||||||
Abstract | Let G be a graph and let A be its cutset-edge incidence matrix. We prove that the linear system frac(1, 2) A x ≥ 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 Cornuéjols, Fonlupt, and Naddef and by Mahjoub which assert that both polyhedra {x {divides} frac(1, 2) A x ≥ 1, x ≥ 0} and {x {divides} frac(1, 2) A x ≥ 1, 1 ≥ x ≥ 0} are integral if G is series-parallel. © 2008 Elsevier B.V. All rights reserved. | ||||||
Persistent Identifier | http://hdl.handle.net/10722/58970 | ||||||
ISSN | 2015 Impact Factor: 0.722 2015 SCImago Journal Rankings: 0.880 | ||||||
ISI Accession Number ID |
Funding Information: The second author was supported in part by NSA grant H98230-05-1-0081 and NSF grants DMS-0556091 and ITR0326387. The third author was supported in part by the Research Grants Council of Hong Kong. | ||||||
References |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Chen, X | en_HK |
dc.contributor.author | Ding, G | en_HK |
dc.contributor.author | Zang, W | en_HK |
dc.date.accessioned | 2010-05-31T03:40:34Z | - |
dc.date.available | 2010-05-31T03:40:34Z | - |
dc.date.issued | 2009 | en_HK |
dc.identifier.citation | Discrete Applied Mathematics, 2009, v. 157 n. 1, p. 118-125 | en_HK |
dc.identifier.issn | 0166-218X | en_HK |
dc.identifier.uri | http://hdl.handle.net/10722/58970 | - |
dc.description.abstract | Let G be a graph and let A be its cutset-edge incidence matrix. We prove that the linear system frac(1, 2) A x ≥ 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 Cornuéjols, Fonlupt, and Naddef and by Mahjoub which assert that both polyhedra {x {divides} frac(1, 2) A x ≥ 1, x ≥ 0} and {x {divides} frac(1, 2) A x ≥ 1, 1 ≥ x ≥ 0} are integral if G is series-parallel. © 2008 Elsevier B.V. All rights reserved. | en_HK |
dc.language | eng | en_HK |
dc.publisher | Elsevier BV. The Journal's web site is located at http://www.elsevier.com/locate/dam | en_HK |
dc.relation.ispartof | Discrete Applied Mathematics | en_HK |
dc.rights | Discrete Applied Mathematics. Copyright © Elsevier BV. | en_HK |
dc.subject | Box total dual integrality | en_HK |
dc.subject | Cut | en_HK |
dc.subject | Graph | en_HK |
dc.subject | Polyhedron | en_HK |
dc.subject | Traveling salesman problem | en_HK |
dc.title | The box-TDI system associated with 2-edge connected spanning subgraphs | en_HK |
dc.type | Article | en_HK |
dc.identifier.openurl | http://library.hku.hk:4550/resserv?sid=HKU:IR&issn=0166-218X&volume=157&spage=118&epage=125&date=2009&atitle=The+Box-TDI+System+Associated+with+2-Edge+Connected+Spanning+Subgraphs | en_HK |
dc.identifier.email | Zang, W:wzang@maths.hku.hk | en_HK |
dc.identifier.authority | Zang, W=rp00839 | en_HK |
dc.description.nature | link_to_subscribed_fulltext | - |
dc.identifier.doi | 10.1016/j.dam.2008.05.001 | en_HK |
dc.identifier.scopus | eid_2-s2.0-56349148697 | en_HK |
dc.identifier.hkuros | 162704 | en_HK |
dc.relation.references | http://www.scopus.com/mlt/select.url?eid=2-s2.0-56349148697&selection=ref&src=s&origin=recordpage | en_HK |
dc.identifier.volume | 157 | en_HK |
dc.identifier.issue | 1 | en_HK |
dc.identifier.spage | 118 | en_HK |
dc.identifier.epage | 125 | en_HK |
dc.identifier.isi | WOS:000261861700011 | - |
dc.publisher.place | Netherlands | en_HK |
dc.identifier.scopusauthorid | Chen, X=8987182300 | en_HK |
dc.identifier.scopusauthorid | Ding, G=7201791806 | en_HK |
dc.identifier.scopusauthorid | Zang, W=7005740804 | en_HK |