KMS Of Academy of mathematics and systems sciences, CAS
| A Polyhedral Description of Kernels | |
Chen, Qin1; Chen, Xujin2 ; Zang, Wenan3
| |
| 2016-08-01 | |
| Source Publication | MATHEMATICS OF OPERATIONS RESEARCH
 |
| ISSN | 0364-765X |
| Volume | 41Issue:3Pages:969-990 |
| Abstract | 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. |
| Keyword | digraph kernel polytope algorithm complexity |
| DOI | 10.1287/moor.2015.0764 |
| Language | 英语 |
| Funding Project | 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 Research Area | Operations Research & Management Science ; Mathematics |
| WOS Subject | Operations Research & Management Science ; Mathematics, Applied |
| WOS ID | WOS:000379496000014 |
| Publisher | INFORMS |
| Citation statistics | |
| Document Type | 期刊论文 |
| Identifier | http://ir.amss.ac.cn/handle/2S8OKBNM/23141 |
| Collection | 应用数学研究所 |
| Corresponding Author | Chen, Qin |
| Affiliation | 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 |
| Recommended Citation 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. |
| Files in This Item: | There are no files associated with this item. | |||||
Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.
Edit Comment