リスト辺彩色の再構成問題
スポンサーリンク
概要
- 論文の詳細を見る
本論文では,同じグラフのリスト辺彩色が2つ与えられたとき,一方の彩色から他方の彩色へ段階的に変形可能かどうか判定する問題を扱う.ただし,1回に変更できるのは1本の辺の色のみであり,変形の途中で得られる彩色は全てリスト辺彩色でなければならない.まず,本論文では,各辺のリストが6色から選ばれている最大次数3の平面的グラフに対してさえ,この問題はPSPACE完全であることを示す.次に,問題を木に限定することで,任意のリスト辺彩色が互いに変形可能であるための十分条件を与える.具体的には,木の各辺に与えられたリストの色数がその辺のどちらの端点の次数より真に大きいとき,木の任意のリスト辺彩色は任意の他のリスト辺彩色に変形可能であることを示す.この十分条件は,ある意味で最良である.我々の証明は,O(n^2)ステップで与えられたリスト辺彩色を実際に変形する多項式時間アルゴリズムを与える.ここで,nは木の点数である.また,十分条件を満たす道でΩ(n^2)ステップの変形を必要とする問題例を与えることで,上記のバウンドがタイトであることを示す.
- 2009-06-22
著者
-
伊藤 健洋
東北大学大学院情報科学研究科
-
KAMINSKI Marcin
Department of Computer Science, Universite Libre de Bruxelles
-
DEMAINE Erik
MIT Computer Science and Artificial Intelligence Laboratory
-
Kaminski Marcin
Department Of Computer Science Universite Libre De Bruxelles
-
伊藤 健洋
東北大学情報科学研究科
関連論文
- 1-D-4 経路長を短くする一方通行決定(離散・組合せ最適化(2))
- リスト辺彩色の再構成問題
- 木の均一分割問題
- 需要点と供給点があるグラフの分割問題の近似可能性
- グラフの距離辺彩色アルゴリズム
- 需要点と供給点のあるグラフの分割
- 再構成問題の計算複雑さ
- 需要と供給の木の分割
- 木の最小コスト辺彩色のマッチングへの帰着
- A-025 Finding Reconfigurations between List Edge-Colorings of a Graph
- グラフの距離辺彩色アルゴリズム
- Reconfiguration of list edge-colorings in a tree (コンピュテーション)
- 需要点と供給点のある木のコスト最小分割
- Modification of physicochemical properties of actin filaments suppresses cell fragmentation in the execution phase of staurosporine-induced apoptotic processes
- 部分集合和遷移問題の多項式時間近似スキーム
- 木の最小コスト辺彩色のマッチングへの帰着
- 需要点と供給点のある木のコスト最小分割
- 木のリスト辺彩色の遷移可能性
- 部分集合和遷移問題の多項式時間近似スキーム
- 木,カクタスにおける点被覆の遷移可能性 (コンピュテーション)
- On the base-line location problem for the maximum weight region decomposable into base-monotone shapes (New Trends in Algorithms and Theory of Computation)
- 木,カクタスにおける点被覆の遷移可能性
- DS-1-9 グラフのL(2,1)ラベリングの遷移可能性(DS-1.COMP学生シンポジウム,シンポジウムセッション)
- 基単調図形に分割可能な最大重み領域を得る基線の配置問題
- グラフ上の拡散競争ゲームの計算複雑さ
- 単位正方形上の一意被覆問題に対する近似アルゴリズム
- Finding a Hamiltonian Path in a Cube with Specified Turns is Hard
- トロミノ詰込問題の計算複雑さについて
- グラフのリストL(2,1)ラベリングの遷移可能性(一般)
- Computational Complexity of Piano-Hinged Dissections
- 次数指定した最大正則誘導部分グラフ探索問題(一般)