近似最小限の帯域のバイナリの木

Question

最低帯域幅の問題が見つ順序のグラフのノードの整数線を最小限に抑える最大の距離の他の隣接するノード。

この決定の問題は、NP完全でもバイナリー。 複雑な結果のための帯域幅の最小化を目的としたGarey,Graham、ジョンソン、Knuth、サイアムJ.Appl.Math., Vol.34,No.3,1978年.

何が最も良く知られているの効率的なapproximability結果を算出す最小限の帯域のバイナリの木がありますか？その中から最適なも知られる条件と硬度の近似りませんか？

Answer 1

Blacheしていました。al、近似Intractabilityの帯域の問題1997年 確認ありません PTA の問題がない限り$ ext{P}= ext{NP}$のもの(バイナリ)。 Unger W,の複雑性を近似した年数帯域の問題1998年 る定数$k\in\mathbb{N}$が多項式時間近似アルゴリズム近似因子の$k$.なので、残念ながらありません PTA も 出荷時 の問題です。

しかしながら、一部の種類のグラフは、問題を解決することができまたは近似多項式時間で最近の調査では、 プチJ.,追補の調査レイアウトの問題、2011年.の調査は、表3、4、8.この調査も素敵なリストを参照したい場合は掘深めます。これはより最新版の調査による ディアスet al., 調査のグラフレイアウトの問題、2002年.

場合にご関心をお持ちになられた方は正確なアルゴリズムとしても多いかと思い、現在最速の一つで与えられます Cygan M.とPilipczuk、もっと早く正確な帯域幅、2012年.このアルゴリズムに$O(4.83^n)$る。