A Unified Approach to Box-Mengerian Hypergraphs
文献类型：期刊论文
| 作者 | Chen, Xujin1 ; Chen, Zhibin2; Zang, Wenan2
|
| 刊名 | MATHEMATICS OF OPERATIONS RESEARCH
 |
| 出版日期 | 2010-08-01 |
| 卷号 | 35期号:3页码:655-668 |
| 关键词 | hypergraph matroid box-total dual integrality packing covering |
| ISSN号 | 0364-765X |
| DOI | 10.1287/moor.1100.0458 |
| 英文摘要 | A 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. |
| 资助项目 | National Science Foundation of China[10771209] ; Chinese Academy of Sciences[kjcx-yw-s7] ; Research Grants Council of Hong Kong ; National Science Foundation of China ; Basic Research of the University of Hong Kong |
| WOS研究方向 | Operations Research & Management Science ; Mathematics |
| 语种 | 英语 |
| WOS记录号 | WOS:000281719400008 |
| 出版者 | INFORMS |
| 源URL | [http://ir.amss.ac.cn/handle/2S8OKBNM/9907]  |
| 专题 | 应用数学研究所 |
| 通讯作者 | Chen, Xujin |
| 作者单位 | 1.Chinese Acad Sci, Inst Appl Math, Beijing 100190, Peoples R China 2.Univ Hong Kong, Dept Math, Hong Kong, Hong Kong, Peoples R China |
| 推荐引用方式 GB/T 7714 | Chen, Xujin,Chen, Zhibin,Zang, Wenan. A Unified Approach to Box-Mengerian Hypergraphs[J]. MATHEMATICS OF OPERATIONS RESEARCH,2010,35(3):655-668. |
| APA | Chen, Xujin,Chen, Zhibin,&Zang, Wenan.(2010).A Unified Approach to Box-Mengerian Hypergraphs.MATHEMATICS OF OPERATIONS RESEARCH,35(3),655-668. |
| MLA | Chen, Xujin,et al."A Unified Approach to Box-Mengerian Hypergraphs".MATHEMATICS OF OPERATIONS RESEARCH 35.3(2010):655-668. |
入库方式： OAI收割
来源：数学与系统科学研究院
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。