.png){kind=icon}
返回
EvenPath in directed single-crossing graphs
.png){kind=icon}
PRE
AI
DOI：10.1016/j.ipl.2025.106613.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
给定一个有向图G及其两个顶点s和t，EvenPath问题是指寻找从s到t的一条偶长度路径。对于一般有向图的EvenPath问题的判定版本，LaPaugh和Papadimitriou[1]已证明其为NP完全问题。因此，发现那些能使EvenPath问题得到高效求解的图类是有意义的。已知对于平面有向图和单交叉极小图(single-crossing-minor-free graphs)的EvenPath问题是可在多项式时间内求解的[2,3]。在我们的工作中，我们将能够使EvenPath问题在多项式时间内求解的图类扩展至单交叉图(single-crossing graphs)。我们的多项式时间算法本质上将有向单交叉图的EvenPath问题约简为平面有向图的若干个EvenPath问题和3-DisjointPaths问题的实例。
Keyword:
EvenPath
Reachability
Graph algorithms
期刊
I
IF:
0.6
论文数:
17
被引数:
3.4K
.png){kind=icon}
