一千萬個為什麽

搜索

二叉樹上最小帶寬的近似值

最小帶寬問題是在整數行上找到一個圖節點的排序,以最小化任何兩個相鄰節點之間的最大距離。

即使對於二叉樹,決策問題也是NP完全的。 帶寬最小化的復雜性結果。 Garey,Graham,Johnson和Knuth,SIAM J. Appl。 Math。,Vol。 1978年第3期,第3期,第3頁)。

計算二叉樹上最小帶寬的最有效的近似性結果是什麽?什麽是近似結果最有名的條件硬度?

最佳答案

Blache et. al, On Approximation Intractability of the Bandwidth Problem, 1997 confirms there is no PTAS for the problem unless $\text{P} = \text{NP}$, even for (binary) trees. Unger W, The Complexity of the Approximation of the Bandwidth Problem, 1998 show that for any constant $k \in \mathbb{N}$ there is no polynomial time approximation algorithm with an approximation factor of $k$. So, unfortunately there's no PTAS nor APX for the problem.

但是,對於某些類型的圖,問題可以用多項式時間來解決或近似。對於最近的調查,請參閱 Petit J.,Addenda到布局問題調查,2011“。在調查中,請參閱表3,表4和表8.如果您想更深入地了解某個方向,此調查還提供了一個很好的參考列表。這是舊版調查的更新版本,由 Diaz et al。 ,圖形布局問題調查,2002年。

如果您對精確算法感興趣,我認為目前最快的算法是

Cygan M.和Pilipczuk M 。,甚至更快的精確帶寬,2012 。該算法以$ O(4.83 ^ n)$ time運行。

轉載註明原文: 二叉樹上最小帶寬的近似值