A Polyhedral Description of Kernels
文献类型：期刊论文
| 作者 | Chen, Qin1; Chen, Xujin2 ; Zang, Wenan3
|
| 刊名 | MATHEMATICS OF OPERATIONS RESEARCH
 |
| 出版日期 | 2016-08-01 |
| 卷号 | 41期号:3页码:969-990 |
| 关键词 | digraph kernel polytope algorithm complexity |
| ISSN号 | 0364-765X |
| DOI | 10.1287/moor.2015.0764 |
| 英文摘要 | Let G be a digraph and let pi(G) be the linear system consisting of nonnegativity, stability, and domination inequalities. We call G kernel ideal if pi(H) defines an integral polytope for each induced subgraph H of G, and we call G kernel Mengerian if pi(H) is totally dual integral (TDI) for each induced subgraph H of G. In this paper we show that a digraph is kernel ideal iff it is kernel Mengerian iff it contains none of three forbidden structures; our characterization yields a polynomial-time algorithm for the minimum weighted kernel problem on kernel ideal digraphs. We also prove that it is NP-hard to find a kernel of minimum size even in a planar bipartite digraph with maximum degree at most three. |
| 资助项目 | National Natural Science Foundation of China[11222109] ; Chinese Academy of Sciences Program for Cross and Cooperative Team of Science and Technology Innovation ; Research Grants Council of Hong Kong |
| WOS研究方向 | Operations Research & Management Science ; Mathematics |
| 语种 | 英语 |
| WOS记录号 | WOS:000379496000014 |
| 出版者 | INFORMS |
| 源URL | [http://ir.amss.ac.cn/handle/2S8OKBNM/23140]  |
| 专题 | 应用数学研究所 |
| 通讯作者 | Chen, Qin |
| 作者单位 | 1.China Jiliang Univ, Dept Math, Hangzhou 310018, Zhejiang, Peoples R China 2.Chinese Acad Sci, Inst Appl Math, Beijing 100190, Peoples R China 3.Univ Hong Kong, Dept Math, Hong Kong, Hong Kong, Peoples R China |
| 推荐引用方式 GB/T 7714 | Chen, Qin,Chen, Xujin,Zang, Wenan. A Polyhedral Description of Kernels[J]. MATHEMATICS OF OPERATIONS RESEARCH,2016,41(3):969-990. |
| APA | Chen, Qin,Chen, Xujin,&Zang, Wenan.(2016).A Polyhedral Description of Kernels.MATHEMATICS OF OPERATIONS RESEARCH,41(3),969-990. |
| MLA | Chen, Qin,et al."A Polyhedral Description of Kernels".MATHEMATICS OF OPERATIONS RESEARCH 41.3(2016):969-990. |
入库方式： OAI收割
来源：数学与系统科学研究院
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。