.png){kind=icon}
返回
Pathlength of outerplanar graphs
.png){kind=icon}
PRE
AI
DOI：10.1016/j.tcs.2026.115759.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
图G = (V, E)的路径分解是一系列V的子集序列，称为袋子，满足某些连通性性质。图G的路径分解的长度是G中属于同一袋子且距离最大的两个顶点之间的最大距离，G的路径长度（记为pl(G)）是其路径分解的最小长度。该参数因其对最小偏心最短路径问题、直线畸变问题等经典度量问题的算法应用而受到研究。然而，判断图G的路径长度是否不超过2是NP完全问题，且已知最佳近似算法的比率为2（除非P = NP，否则不存在c < 3/2的c近似算法）。在本工作中，我们专注于研究平面图简单子类的路径长度。我们首先设计了一个线性时间算法来计算树的路径长度。然后，我们证明具有n个顶点的循环图的路径长度等于⌊n/2⌋。我们的主要成果是为外平面图路径长度设计了一个(+1)-近似算法。该算法基于外平面图几乎所有最优（长度不超过pl(G) + 1）路径分解的刻画。
Keyword:
Path-decomposition
Outerplanar graph
Pathlength
期刊
IF:
1
论文数:
273
被引数:
1.0W
机构
引用论文
.png){kind=icon}
分享收藏分享收藏
查看更多内容