File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Packing circuits in matroids

TitlePacking circuits in matroids
Authors
Ding, GZang, W
KeywordsCircuit
Matroid
Polyhedron
Total dual integrality
Traveling salesman problem
Issue Date2009
PublisherSpringer Verlag. The Journal's web site is located at http://link.springer.de/link/service/journals/10107/
Citation
Mathematical Programming, 2009, v. 119 n. 1, p. 137-168 How to Cite?
DOI: http://dx.doi.org/10.1007/s10107-007-0205-6
AbstractThe purpose of this paper is to characterize all matroids M that satisfy the following minimax relation: for any nonnegative integral weight function w defined on E(M), Maximum { k: M has k circuits ,(repetition, allowed) such that each element e of M is used at most 2w(e) times by these circuits = Minimum { ∑x ∈ X w(x): X is a collection of elements (repetition allowed) of M such that every circuit in M meets X at least twice}. Our characterization contains a complete solution to a research problem on 2-edge-connected subgraph polyhedra posed by Cornuéjols, Fonlupt, and Naddef in 1985, which was independently solved by Vandenbussche and Nemhauser in Vandenbussche and Nemhauser (J. Comb. Optim. 9:357-379, 2005). © 2008 Springer-Verlag.
Persistent Identifierhttp://hdl.handle.net/10722/58957
ISSN
0025-5610
2023 Impact Factor: 2.2
2023 SCImago Journal Rankings: 1.982
ISI Accession Number ID
WOS:000263380900007
Funding AgencyGrant Number
NSAH98230-05-1-0081
NSFDMS-0556091
ITR-0326387
Research Grants Council of Hong Kong
Funding Information:

W. Zang's research partially supported by the Research Grants Council of Hong Kong.

References
References in Scopus

 

DC FieldValueLanguage
dc.contributor.authorDing, Gen_HK
dc.contributor.authorZang, Wen_HK
dc.date.accessioned2010-05-31T03:40:21Z-
dc.date.available2010-05-31T03:40:21Z-
dc.date.issued2009en_HK
dc.identifier.citationMathematical Programming, 2009, v. 119 n. 1, p. 137-168en_HK
dc.identifier.issn0025-5610en_HK
dc.identifier.urihttp://hdl.handle.net/10722/58957-
dc.description.abstractThe purpose of this paper is to characterize all matroids M that satisfy the following minimax relation: for any nonnegative integral weight function w defined on E(M), Maximum { k: M has k circuits ,(repetition, allowed) such that each element e of M is used at most 2w(e) times by these circuits = Minimum { ∑x ∈ X w(x): X is a collection of elements (repetition allowed) of M such that every circuit in M meets X at least twice}. Our characterization contains a complete solution to a research problem on 2-edge-connected subgraph polyhedra posed by Cornuéjols, Fonlupt, and Naddef in 1985, which was independently solved by Vandenbussche and Nemhauser in Vandenbussche and Nemhauser (J. Comb. Optim. 9:357-379, 2005). © 2008 Springer-Verlag.en_HK
dc.languageengen_HK
dc.publisherSpringer Verlag. The Journal's web site is located at http://link.springer.de/link/service/journals/10107/en_HK
dc.relation.ispartofMathematical Programmingen_HK
dc.rightsThis work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.-
dc.subjectCircuiten_HK
dc.subjectMatroiden_HK
dc.subjectPolyhedronen_HK
dc.subjectTotal dual integralityen_HK
dc.subjectTraveling salesman problemen_HK
dc.titlePacking circuits in matroidsen_HK
dc.typeArticleen_HK
dc.identifier.openurlhttp://library.hku.hk:4550/resserv?sid=HKU:IR&issn=0025-5610&volume=119&spage=137&epage=168&date=2009&atitle=Packing+Circuits+in+Matroidsen_HK
dc.identifier.emailZang, W:wzang@maths.hku.hken_HK
dc.identifier.authorityZang, W=rp00839en_HK
dc.description.naturepreprint-
dc.identifier.doi10.1007/s10107-007-0205-6en_HK
dc.identifier.scopuseid_2-s2.0-60449085504en_HK
dc.identifier.hkuros162702en_HK
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-60449085504&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume119en_HK
dc.identifier.issue1en_HK
dc.identifier.spage137en_HK
dc.identifier.epage168en_HK
dc.identifier.eissn1436-4646-
dc.identifier.isiWOS:000263380900007-
dc.publisher.placeGermanyen_HK
dc.identifier.scopusauthoridDing, G=7201791806en_HK
dc.identifier.scopusauthoridZang, W=7005740804en_HK
dc.identifier.issnl0025-5610-

Export via OAI-PMH Interface in XML Formats

OR

Export to Other Non-XML Formats