Pathwidth -- 来自 Wolfram MathWorld

路径宽度

图的路径宽度，也称为区间厚度、顶点分离数和节点搜索数，比路径分解中最大集合的大小小 1。

如下表总结，路径宽度的障碍集（由三角形图和轮辐图组成，如上图所示）和（由 110 个图组成）在 Kinnersley 和 Langston (1992) 中描述，他们利用了门矩阵布局参数与路径宽度参数问题相同这一事实（Fellows 和 Langston 1989，Kinnersley 和 Langston 1992）。

路径宽度界限	障碍
	三角形图和轮辐图
	110 个禁用次图

上面展示了 110 个禁用次图的集合 (Kinnersley 和 Langston 1992)。它们在 Wolfram 语言中实现为GraphData["PathwidthForbidden"].

另请参阅

图带宽, 轮辐图, 树宽度

使用 Wolfram|Alpha 探索

更多尝试

参考文献

Chlebiková, J. "The Structure of Obstructions to Treewidth and Pathwidth." Disc. Appl. Math. 120, 61-71, 2002.Fellows, M. R. and Langston, M. A. "On Search, Decision and the Efficiency of Polynomial-Time Algorithms." In Proceedings of the 21st ACM Symposium on the Theory of Computing, pp. 501-512, 1989.Kinnersley, N. G. and Langston, M. A. "Obstruction Set Isolation for the Gate Matrix Layout Problem." Disc. Appl. Math. 54, 169-213, 1992.

请按如下方式引用

Weisstein, Eric W. "路径宽度。" 来自 MathWorld--Wolfram Web 资源。 https://mathworld.net.cn/Pathwidth.html