A Unified Approach to Box-Mengerian Hypergraphs

doi:10.1287/moor.1100.0458

CSpace > 应用数学研究所

	A Unified Approach to Box-Mengerian Hypergraphs
	Chen, Xujin1 ; Chen, Zhibin 2; Zang, Wenan 2
	2010-08-01
发表期刊	MATHEMATICS OF OPERATIONS RESEARCH
ISSN	0364-765X
卷号	35 期号:3 页码:655-668
摘要	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.
关键词	hypergraph matroid box-total dual integrality packing covering
DOI	10.1287/moor.1100.0458
语种	英语
资助项目	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类目	Operations Research & Management Science ; Mathematics, Applied
WOS记录号	WOS:000281719400008
出版者	INFORMS
引用统计
文献类型	期刊论文
条目标识符	http://ir.amss.ac.cn/handle/2S8OKBNM/9908
专题	应用数学研究所
通讯作者	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.