主題
Search

路徑寬度

圖 G 的路徑寬度，也稱為區間厚度、頂點分離數和節點搜尋數，比路徑分解 G 中最大集合的大小小 1。

PathwidthForbiddenMinors

如下表總結，路徑寬度 <=1 的障礙集（由 三角形圖 C_3 和 輪輻圖 S(3,2) 組成，如上圖所示）和 <=2 （由 110 個圖組成）在 Kinnersley 和 Langston (1992) 中描述，他們利用了門矩陣佈局引數 k 與路徑寬度引數 k-1 問題相同這一事實（Fellows 和 Langston 1989，Kinnersley 和 Langston 1992）。

路徑寬度界限障礙
<=1三角形圖 C_3 和 輪輻圖 S(3,2)
<=2110 個 停用次圖
Pathwidth2FirbiddenMinors

上面展示了 110 個 停用次圖 的集合 (Kinnersley 和 Langston 1992)。 它們在 Wolfram 語言 中實現為GraphData["PathwidthForbidden"].

另請參閱

圖頻寬, 輪輻圖, 樹寬度

使用 探索

參考文獻

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. "路徑寬度。" 來自 Web 資源。 https://mathworld.tw/Pathwidth.html

主題分類