论文标题
最小偏心率最短的路径问题相对于结构参数
Minimum Eccentricity Shortest Path Problem with Respect to Structural Parameters
论文作者
论文摘要
最小偏心率最短的路径问题包括在给定的无向图中找到最短的偏心率的最短路径。相对于所需的偏心率，该问题已知NP完整和w [2] - hard。我们介绍了通过模块宽度，群集图，树宽与所需偏心率的组合和最大叶子数的组合和最大叶子数来参数参数的问题。
The Minimum Eccentricity Shortest Path Problem consists in finding a shortest path with minimum eccentricity in a given undirected graph. The problem is known to be NP-complete and W[2]-hard with respect to the desired eccentricity. We present fpt-algorithms for the problem parameterized by the modular width, distance to cluster graph, the combination of treewidth with the desired eccentricity, and maximum leaf number.
