-
46浏览
-
0点赞
-
0收藏
-
0分享
-
0下载
-
0评论
-
引用
期刊论文
A Polyhedral Description of Kernels
Mathematics of Operations Research,2016,41(3): | 2016年04月05日 | https://doi.org/10.1287/moor.2015.0764
Let G be a digraph and let π(G) be the linear system consisting of nonnegativity, stability, and domination inequalities. We call G kernel ideal if π(H) defines an integral polytope for each induced subgraph H of G, and we call G kernel Mengerian if π(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.
学者未上传该成果的PDF文件,请等待学者更新
本学者其他成果
同领域成果