重軽分解

組合せ数学と理論計算機科学において、重軽分解(重パス分解とも呼ばれる) は、ルート付きツリーをパスのセットに分解する手法です。重パス分解では、各非リーフノードは、子孫の数が最も多い子へのエッジである「重エッジ」を 1 つ選択します (同点の場合は任意に選択)。選択されたエッジが分解のパスを形成します。

パスへの分解

ツリーTのエッジが、各非リーフノードからその子ノードの 1 つへの 1 つの重いエッジを持つ、重いエッジと軽いエッジのセットに分割されている場合、重いエッジによって形成されるサブグラフはパスのセットで構成され、各非リーフ頂点は、その重いエッジを含む 1 つのパスにのみ属します。重いエッジのエンドポイントではないツリーのリーフノードは、長さが 0 のパスを形成すると見なすことができます。このように、各頂点は、パスの 1 つにのみ属します。各パスには、最上位の頂点であるヘッド頂点があります。

あるいは、重いエッジのパスには、パスの先頭から親までの軽いエッジを 1 つ含めて拡張することもできます。^[1]この分解のバリエーションでは、いくつかの頂点は複数のパスに属しますが、Tのすべてのエッジは1 つのパスに属します。

道の木

分解のパスは、それ自体が「パスツリー」、「重いパスツリー」、または「圧縮ツリー」と呼ばれるツリーに編成される場合があります。パスツリーの各ノードは、重いパス分解のパスに対応します。p が重いパス分解のパスである場合、パスツリー内のpの親は、pのヘッドの親を含むパスです。パスツリーのルートは、元のツリーのルートを含むパスです。または、パスツリーは、すべての重いエッジのエッジ収縮によって元のツリーから形成される場合もあります。

特定のツリーの「ライト」エッジは、ヘビーパス分解の一部として選択されなかったエッジです。ライトエッジが 2 つのツリーノードxとy を接続し、x がyの親である場合、x の子孫の数はyの 2 倍以上である必要があります。したがって、 n個のノードを持つツリーのルートからリーフへのパスには、最大で log ₂ n 個のライトエッジが存在できます。同様に、パスツリーの高さは最大で log ₂ n 個になります。

アプリケーション

ヘビーパス分解は、Sleator & Tarjan (1983) によってリンク/カットツリー構造の償却分析の一部として導入されました^{[2]。また、Harel & Tarjan (1984) によって}最小共通祖先データ構造の一部として導入されました^[3]。リンク/カットツリーデータ構造は、動的ツリーをパスに分割しますが、これは必ずしもヘビーパス分解ではありません。その分析では、ヘビーパス分解からの距離を測定するポテンシャル関数を使用します。また、パスツリーの高さが小さいため、各データ構造操作では、この関数の改善に充てることのできない少数のステップしか実行されません。^[2]最小共通祖先データ構造では、分解を使用して入力ツリーを対数深さの完全なバイナリツリーに埋め込み、各クエリを定数時間のビット単位の操作で解決できます。^[3]

重パス分解のその後の応用としては、レベル祖先問題の解決、^[4]、ツリー間の編集距離の計算、 ^[5]^[6]、グラフの描画と貪欲埋め込み、^[7]^[8]^[9]、特定のグラフのすべてのノード付近のパスの検索、^[10]、光ファイバー通信ネットワークの障害診断、^{[1] 、}文法ベースのコードのデコード、^[11]などがあります。

参考文献

^ ab Harvey, Nicholas JA; Pătraşcu, Mihai ; Wen, Yonggang; Yekhanin, Sergey; Chan, Vincent WS (2007)、「グラフの組み合わせグループテストによる全光ネットワークの非適応型障害診断」、第 26 回 IEEE 国際コンピュータ通信会議 (INFOCOM 2007)、pp. 697–705、doi :10.1109/INFCOM.2007.87、ISBN 978-1-4244-1047-7
^ ab Sleator, Daniel D. ; Tarjan, Robert Endre (1983)、「動的ツリーのデータ構造」、Journal of Computer and System Sciences、26 (3): 362–391、doi : 10.1016/0022-0000(83)90006-5、MR 0710253
^ ab Harel, Dov; Tarjan, Robert E. (1984)、「最も近い共通祖先を見つけるための高速アルゴリズム」、SIAM Journal on Computing、13 (2): 338–355、doi :10.1137/0213024
^ Dietz, Paul F. (1991)、「動的ツリーにおけるレベル祖先の検出」、アルゴリズムとデータ構造 (オタワ、オンタリオ州、1991)、コンピュータサイエンスの講義ノート、第519巻、ベルリン: Springer、pp. 32–40、doi :10.1007/BFb0028247、ISBN 3-540-54343-0、MR 1146687
^ Klein, Philip N. (1998)、「ルートなし順序付き木間の編集距離の計算」、アルゴリズム—ESA '98 (ヴェネツィア)、コンピュータサイエンスの講義ノート、vol. 1461、ベルリン: Springer、pp. 91–102、doi :10.1007/3-540-68530-8_8、ISBN 978-3-540-64848-2、MR 1683332、S2CID 9910968
^ Demaine, Erik D. ; Mozes, Shay; Rossman, Benjamin; Weimann, Oren (2010)、「ツリー編集距離の最適分解アルゴリズム」、ACM Transactions on Algorithms、6 (1): A2、doi :10.1007/978-3-540-73420-8_15、MR 2654906
^ Buchsbaum, Adam L.; Westbrook, Jeffery R. (2000)、「階層グラフビューの維持」、第 11 回 ACM-SIAM 離散アルゴリズムシンポジウムの議事録 (サンフランシスコ、カリフォルニア州、2000 年)、ニューヨーク: ACM、pp. 566–575、MR 1755515
^ Eppstein, David ; Goodrich, Michael T. (2011)、「双曲幾何学を用いた簡潔な貪欲幾何学ルーティング」、IEEE Transactions on Computers、60 (11): 1571–1580、doi :10.1109/TC.2010.257、MR 2830035、S2CID 40368995
^ Duncan, Christian A.; Eppstein, David ; Goodrich, Michael T .; Kobourov, Stephen G.; Nöllenburg, Martin (2013)、「完全な角度解像度と多項式面積によるツリーの描画」、Discrete and Computational Geometry、49 (2): 157–182、arXiv : 1009.0581、doi :10.1007/s00454-012-9472-y、MR 3017904、S2CID 254034095
^ アルストラップ、スティーブン;ラウリドセン、ピーター・W;サマーランド、ピア。 Thorup、Mikkel (1997)、「Finding cores of Limited length」、Algorithms and Data Structures、Lecture Notes in Computer Science Volume、vol. 1272、Springer、45–54 ページ、土井:10.1007/3-540-63307-3_47、ISBN 978-3-540-63307-5
^ Bille, Philip; Landau, Gad M.; Raman, Rajeev; Sadakane, Kunihiko; Satti, Srinivasa Rao; Weimann, Oren (2011)、「文法圧縮文字列へのランダムアクセス」、第 22 回 ACM-SIAM 離散アルゴリズムシンポジウムの議事録、フィラデルフィア、PA: SIAM、pp. 373–389、MR 2857133

[hpwyk07-1] Harvey, Nicholas JA; Pătraşcu, Mihai ; Wen, Yonggang; Yekhanin, Sergey; Chan, Vincent WS (2007)、「グラフの組み合わせグループテストによる全光ネットワークの非適応型障害診断」、第 26 回 IEEE 国際コンピュータ通信会議 (INFOCOM 2007)、pp. 697–705、doi :10.1109/INFCOM.2007.87、ISBN 978-1-4244-1047-7

[st83-2] Sleator, Daniel D. ; Tarjan, Robert Endre (1983)、「動的ツリーのデータ構造」、Journal of Computer and System Sciences、26 (3): 362–391、doi : 10.1016/0022-0000(83)90006-5、MR 0710253

[ht84-3] Harel, Dov; Tarjan, Robert E. (1984)、「最も近い共通祖先を見つけるための高速アルゴリズム」、SIAM Journal on Computing、13 (2): 338–355、doi :10.1137/0213024

[d91-4] Dietz, Paul F. (1991)、「動的ツリーにおけるレベル祖先の検出」、アルゴリズムとデータ構造 (オタワ、オンタリオ州、1991)、コンピュータサイエンスの講義ノート、第519巻、ベルリン: Springer、pp. 32–40、doi :10.1007/BFb0028247、ISBN 3-540-54343-0、MR 1146687

[k98-5] Klein, Philip N. (1998)、「ルートなし順序付き木間の編集距離の計算」、アルゴリズム—ESA '98 (ヴェネツィア)、コンピュータサイエンスの講義ノート、vol. 1461、ベルリン: Springer、pp. 91–102、doi :10.1007/3-540-68530-8_8、ISBN 978-3-540-64848-2、MR 1683332、S2CID 9910968

[dmrw10-6] Demaine, Erik D. ; Mozes, Shay; Rossman, Benjamin; Weimann, Oren (2010)、「ツリー編集距離の最適分解アルゴリズム」、ACM Transactions on Algorithms、6 (1): A2、doi :10.1007/978-3-540-73420-8_15、MR 2654906

[bw00-7] Buchsbaum, Adam L.; Westbrook, Jeffery R. (2000)、「階層グラフビューの維持」、第 11 回 ACM-SIAM 離散アルゴリズムシンポジウムの議事録 (サンフランシスコ、カリフォルニア州、2000 年)、ニューヨーク: ACM、pp. 566–575、MR 1755515

[eg11-8] Eppstein, David ; Goodrich, Michael T. (2011)、「双曲幾何学を用いた簡潔な貪欲幾何学ルーティング」、IEEE Transactions on Computers、60 (11): 1571–1580、doi :10.1109/TC.2010.257、MR 2830035、S2CID 40368995

[degkn13-9] Duncan, Christian A.; Eppstein, David ; Goodrich, Michael T .; Kobourov, Stephen G.; Nöllenburg, Martin (2013)、「完全な角度解像度と多項式面積によるツリーの描画」、Discrete and Computational Geometry、49 (2): 157–182、arXiv : 1009.0581、doi :10.1007/s00454-012-9472-y、MR 3017904、S2CID 254034095

[alst97-10] アルストラップ、スティーブン;ラウリドセン、ピーター・W;サマーランド、ピア。 Thorup、Mikkel (1997)、「Finding cores of Limited length」、Algorithms and Data Structures、Lecture Notes in Computer Science Volume、vol. 1272、Springer、45–54 ページ、土井:10.1007/3-540-63307-3_47、ISBN 978-3-540-63307-5

[blrssw11-11] Bille, Philip; Landau, Gad M.; Raman, Rajeev; Sadakane, Kunihiko; Satti, Srinivasa Rao; Weimann, Oren (2011)、「文法圧縮文字列へのランダムアクセス」、第 22 回 ACM-SIAM 離散アルゴリズムシンポジウムの議事録、フィラデルフィア、PA: SIAM、pp. 373–389、MR 2857133