File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: The box-TDI system associated with 2-edge connected spanning subgraphs

TitleThe box-TDI system associated with 2-edge connected spanning subgraphs
Authors
Chen, XDing, GZang, W
KeywordsBox total dual integrality
Cut
Graph
Polyhedron
Traveling salesman problem
Issue Date2009
PublisherElsevier 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?
DOI: http://dx.doi.org/10.1016/j.dam.2008.05.001
AbstractLet 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 Identifierhttp://hdl.handle.net/10722/58970
ISSN
0166-218X
2021 Impact Factor: 1.254
2020 SCImago Journal Rankings: 0.700
ISI Accession Number ID
WOS:000261861700011
Funding AgencyGrant Number
NSAH98230-05-1-0081
DMS-0556091
ITR0326387
Research Grants Council of Hong Kong
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
References in Scopus

 

DC FieldValueLanguage
dc.contributor.authorChen, Xen_HK
dc.contributor.authorDing, Gen_HK
dc.contributor.authorZang, Wen_HK
dc.date.accessioned2010-05-31T03:40:34Z-
dc.date.available2010-05-31T03:40:34Z-
dc.date.issued2009en_HK
dc.identifier.citationDiscrete Applied Mathematics, 2009, v. 157 n. 1, p. 118-125en_HK
dc.identifier.issn0166-218Xen_HK
dc.identifier.urihttp://hdl.handle.net/10722/58970-
dc.description.abstractLet 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.languageengen_HK
dc.publisherElsevier BV. The Journal's web site is located at http://www.elsevier.com/locate/damen_HK
dc.relation.ispartofDiscrete Applied Mathematicsen_HK
dc.rightsDiscrete Applied Mathematics. Copyright © Elsevier BV.en_HK
dc.subjectBox total dual integralityen_HK
dc.subjectCuten_HK
dc.subjectGraphen_HK
dc.subjectPolyhedronen_HK
dc.subjectTraveling salesman problemen_HK
dc.titleThe box-TDI system associated with 2-edge connected spanning subgraphsen_HK
dc.typeArticleen_HK
dc.identifier.openurlhttp://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+Subgraphsen_HK
dc.identifier.emailZang, W:wzang@maths.hku.hken_HK
dc.identifier.authorityZang, W=rp00839en_HK
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.doi10.1016/j.dam.2008.05.001en_HK
dc.identifier.scopuseid_2-s2.0-56349148697en_HK
dc.identifier.hkuros162704en_HK
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-56349148697&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume157en_HK
dc.identifier.issue1en_HK
dc.identifier.spage118en_HK
dc.identifier.epage125en_HK
dc.identifier.isiWOS:000261861700011-
dc.publisher.placeNetherlandsen_HK
dc.identifier.scopusauthoridChen, X=8987182300en_HK
dc.identifier.scopusauthoridDing, G=7201791806en_HK
dc.identifier.scopusauthoridZang, W=7005740804en_HK
dc.identifier.issnl0166-218X-

Export via OAI-PMH Interface in XML Formats

OR

Export to Other Non-XML Formats