咨询与建议

看过本文的还看了

相关文献

该作者的其他文献

文献详情 >On the complexity of the Euler... 收藏

On the complexity of the Eulerian closed walk with precedence path constraints problem

与领先路径限制问题在关上的 Eulerian 的复杂性上走

作     者:Kerivin, H. L. M. Lacroix, M. Mahjoub, A. R. 

作者机构:Univ Blaise Pascal Clermont Ferrand II CNRS UMR 6158 LIMOS F-63177 Aubiere France Clemson Univ Dept Math Sci Clemson SC 29634 USA 

出 版 物:《THEORETICAL COMPUTER SCIENCE》 (理论计算机科学)

年 卷 期:2012年第439卷

页      面:16-29页

核心收录:

学科分类:08[工学] 0812[工学-计算机科学与技术(可授工学、理学学位)] 

主  题:Eulerian closed walk Precedence path constraints NP-completeness Polynomial-time algorithm 

摘      要:The Eulerian closed walk problem in a digraph is a well-known polynomial-time solvable problem. In this paper, we show that if we impose the feasible solutions to fulfill some precedence constraints specified by paths of the digraph, then the problem becomes NP-complete. We also present a polynomial-time algorithm to solve this variant of the Eulerian closed walk problem when the set of paths does not contain some forbidden structure. This allows us to give necessary and sufficient conditions for the existence of feasible solutions in this polynomial-time solvable case. (C) 2012 Published by Elsevier B.V.

读者评论 与其他读者分享你的观点

用户名:未登录
我的评分