木のリスト辺彩色の遷移可能性
スポンサーリンク
概要
- 論文の詳細を見る
本論文では,同じグラフのリスト辺彩色が2つ与えられたとき,一方の彩色から他方の彩色へ段階的に遷移させたい.ただし,1回に変更(再彩色)できるのは1本の辺の色のみであり,遷移の途中で得られる彩色は全てリスト辺彩色でなければならない.従来,木に対し,任意のリスト辺彩色が互いに遷移できるための十分条件が知られていた.本論文では,木に対し,従来の十分条件を改良した新しい十分条件を与える.我々の十分条件は,ある意味で最良である.証明は構成的であり,与えられたリスト辺彩色を実際に遷移させる多項式時間アルゴリズムが得られる.木の点数をnとすると,アルゴリズムはO(n^2)回の再彩色を行う遷移を見つける.我々の十分条件を満たす長さnの道でΩ(n^2)回の再彩色を必要とする問題例があるため,この再彩色回数の上界はタイトである.
- 2011-03-02
著者
関連論文
- 1-D-4 経路長を短くする一方通行決定(離散・組合せ最適化(2))
- バランスのよいグラフ分割を用いた平面グラフの小面積格子描画法
- リスト辺彩色の再構成問題
- 木の均一分割問題
- 3連結平面グラフの細分の格子凸描画
- 需要点と供給点があるグラフの分割問題の近似可能性
- 直並列グラフの折れ曲がり最小の直交描画
- グラフの距離辺彩色アルゴリズム
- 需要点と供給点のあるグラフの分割
- 再構成問題の計算複雑さ
- 需要と供給の木の分割
- Efficient Algorithms for Edge-Coloring Partial k-Trees
- 部分k-木で辺素な道をみつけるアルゴリズム
- 部分k木を全彩色する多項式時間アルゴリズム
- 木の最小コスト辺彩色のマッチングへの帰着
- A-026 グラフ分割を用いた格子描画法(モデル・アルゴリズム・プログラミング,一般論文)
- グラフの距離辺彩色アルゴリズム
- Reconfiguration of list edge-colorings in a tree (コンピュテーション)
- 需要点と供給点のある木のコスト最小分割
- 部分k木で辺素な道を見つけるアルゴリズム
- 木を辺ランク付けする効率のよいアルゴリズム
- 部分k木を[g,f]-辺彩色する多項式時間アルゴリズム
- 部分k-木に対する[g,f]-辺彩色アルゴリズム
- 部分κ木を辺彩色する並列アルゴリズム
- 部分$k$木を全彩色する線形時間アルゴリズム (新しいパラダイムとしてのアルゴリズム工学)
- DS-1-4 剰余関数を計算するしきい値回路のエネルギー複雑度とファンイン(DS-1.COMP学生シンポジウム,シンポジウムセッション)
- 部分集合和遷移問題の多項式時間近似スキーム
- LA-11 直並列グラフをリスト辺彩色するアルゴリズム(A. アルゴリズム・基礎)
- 直並列グラフをリスト辺彩色するアルゴリズム
- 部分k-木のl-点彩色多項式時間アルゴリズム
- 木の最小コスト辺彩色のマッチングへの帰着
- 需要点と供給点のある木のコスト最小分割
- 木のリスト辺彩色の遷移可能性
- A-37 直並列グラフのリスト全彩色(グラフアルゴリズム(1),A.アルゴリズム・基礎)
- 剰余関数を計算するエネルギー複雑度の小さいしきい値回路
- 退化的グラフの全彩色
- 部分k-木の全彩色を求める線形時間アルゴリズム
- 部分k-木の全彩色を求める多項式時間アルゴリズム
- 部分κ-木の一般化点ランキング
- 木の一般化辺ランキング
- 木の分割問題を解くアルゴリズム
- 直並列グラフの重み付き彩色の効率のよいアルゴリズム
- 部分k木で独立全域木を見つけるアルゴリズム
- 部分κ木に対する辺素な道問題のNP-完全性
- 部分k-木をf-辺彩色するアルゴリズム
- グラフの辺彩色及びƒ-辺彩色アルゴリズム
- 部分集合和遷移問題の多項式時間近似スキーム
- 木,カクタスにおける点被覆の遷移可能性 (コンピュテーション)
- 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学生シンポジウム,シンポジウムセッション)
- Reconfiguration of List L(2,1)-Labelings in a Graph (コンピュテーション)
- 基単調図形に分割可能な最大重み領域を得る基線の配置問題
- グラフ上の拡散競争ゲームの計算複雑さ
- 論理回路の出力パターン数え上げ
- グラフの帯域幅連続多重彩色を求めるアルゴリズム
- 単位正方形上の一意被覆問題に対する近似アルゴリズム
- 関数$P^n_D$を計算するしきい値回路 (理論計算機科学の新展開)
- Energy-Efficient Threshold Circuits Detecting Global Pattern in 1-Dimensional Arrays (New Trends in Theoretical Computer Science)
- トロミノ詰込問題の計算複雑さについて
- グラフのリストL(2,1)ラベリングの遷移可能性(一般)
- 論理回路の出力パターン数え上げ(一般)
- 次数指定した最大正則誘導部分グラフ探索問題(一般)