A Note on the NP-Completeness of Vertex Elimination on Directed Graphs
A Note on the NP-Completeness of Vertex Elimination on Directed Graphs
复制标题
关于有向图顶点消除的NP完备性的一个注解
DOI：
--
复制
发表时间：
1980
期刊：
影响因子：
--
通讯作者：
J. Gilbert
中科院分区：
文献类型：
--
作者：
J. Gilbert
对Rose和Tarjan的证明进行了更正[SIAM J.Appl.数学，1978]确定有向图的最小填充消除顺序是NP-完全的。
A correction is made to Rose and Tarjan’s proof [SIAM J. Appl. Math., 1978] that determining a minimum fill-in elimination ordering for a directed graph is NP-complete.