File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: A unified approach to box-mengerian hypergraphs

TitleA unified approach to box-mengerian hypergraphs
Authors
Chen, XChen, ZZang, W
KeywordsBox-total dual integrality
Covering
Hypergraph
Matroid
Packing
Issue Date2010
PublisherINFORMS. The Journal's web site is located at http://mor.pubs.informs.org
Citation
Mathematics Of Operations Research, 2010, v. 35 n. 3, p. 655-668 How to Cite?
DOI: http://dx.doi.org/10.1287/moor.1100.0458
AbstractA hypergraph is called box-Mengerian if the linear system Ax ≥ 1, x ≥ 0 is box-totally dual integral (box-TDI), where A is the edge-vertex incidence matrix of the hypergraph. Because it is NP-hard in general to recognize box-Mengerian hypergraphs, a basic theme in combinatorial optimization is to identify such objects associated with various problems. In this paper, we show that the so-called equitably subpartitionable (ESP) property, first introduced by Ding and Zang (Ding, G., W. Zang. 2002. Packing cycles in graphs. J. Combin. Theory Ser. B 86 381-407) in their characterization of all graphs with the min-max relation on packing and covering cycles, turns out to be even sufficient for box-Mengerian hypergraphs. We also establish several new classes of box-Mengerian hypergraphs based on ESP property. This approach is of transparent combinatorial nature and is hence fairly easy to work with. Copyright © 2010 INFORMS.
Persistent Identifierhttp://hdl.handle.net/10722/124810
ISSN
0364-765X
2023 Impact Factor: 1.4
2023 SCImago Journal Rankings: 1.215
ISI Accession Number ID
WOS:000281719400008
Funding AgencyGrant Number
National Science Foundation of China10771209
Chinese Academy of Scienceskjcx-yw-s7
Research Grants Council of Hong Kong
National Science Foundation of China
Basic Research of the University of Hong Kong
Funding Information:

The authors are indebted to Professor Guoli Ding for stimulating discussions. Xujin Chen is supported in part by the National Science Foundation of China under Grant 10771209 and the Chinese Academy of Sciences under Grant kjcx-yw-s7. Wenan Zang is supported in part by the Research Grants Council of Hong Kong, the Overseas and Hong Kong Macau Young Scholars Collaborative Research Fund of the National Science Foundation of China, and Seed Funding for Basic Research of the University of Hong Kong.

References
References in Scopus

 

DC FieldValueLanguage
dc.contributor.authorChen, Xen_HK
dc.contributor.authorChen, Zen_HK
dc.contributor.authorZang, Wen_HK
dc.date.accessioned2010-10-31T10:55:26Z-
dc.date.available2010-10-31T10:55:26Z-
dc.date.issued2010en_HK
dc.identifier.citationMathematics Of Operations Research, 2010, v. 35 n. 3, p. 655-668en_HK
dc.identifier.issn0364-765Xen_HK
dc.identifier.urihttp://hdl.handle.net/10722/124810-
dc.description.abstractA hypergraph is called box-Mengerian if the linear system Ax ≥ 1, x ≥ 0 is box-totally dual integral (box-TDI), where A is the edge-vertex incidence matrix of the hypergraph. Because it is NP-hard in general to recognize box-Mengerian hypergraphs, a basic theme in combinatorial optimization is to identify such objects associated with various problems. In this paper, we show that the so-called equitably subpartitionable (ESP) property, first introduced by Ding and Zang (Ding, G., W. Zang. 2002. Packing cycles in graphs. J. Combin. Theory Ser. B 86 381-407) in their characterization of all graphs with the min-max relation on packing and covering cycles, turns out to be even sufficient for box-Mengerian hypergraphs. We also establish several new classes of box-Mengerian hypergraphs based on ESP property. This approach is of transparent combinatorial nature and is hence fairly easy to work with. Copyright © 2010 INFORMS.en_HK
dc.languageengen_HK
dc.publisherINFORMS. The Journal's web site is located at http://mor.pubs.informs.orgen_HK
dc.relation.ispartofMathematics of Operations Researchen_HK
dc.subjectBox-total dual integralityen_HK
dc.subjectCoveringen_HK
dc.subjectHypergraphen_HK
dc.subjectMatroiden_HK
dc.subjectPackingen_HK
dc.titleA unified approach to box-mengerian hypergraphsen_HK
dc.typeArticleen_HK
dc.identifier.openurlhttp://library.hku.hk:4550/resserv?sid=HKU:IR&issn=0364-765X&volume=35&issue=3&spage=655&epage=668&date=2010&atitle=A+unified+approach+to+box-mengerian+hypergraphsen_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.1287/moor.1100.0458en_HK
dc.identifier.scopuseid_2-s2.0-77956638891en_HK
dc.identifier.hkuros174828en_HK
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-77956638891&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume35en_HK
dc.identifier.issue3en_HK
dc.identifier.spage655en_HK
dc.identifier.epage668en_HK
dc.identifier.eissn1526-5471-
dc.identifier.isiWOS:000281719400008-
dc.publisher.placeUnited Statesen_HK
dc.identifier.scopusauthoridChen, X=8987182300en_HK
dc.identifier.scopusauthoridChen, Z=36476991200en_HK
dc.identifier.scopusauthoridZang, W=7005740804en_HK
dc.identifier.issnl0364-765X-

Export via OAI-PMH Interface in XML Formats

OR

Export to Other Non-XML Formats