台形グラフの彩色問題を解く並列アルゴリズム
スポンサーリンク
概要
- 論文の詳細を見る
グラフGの節点に対し,隣接するどの2節点も異なる色となるように着色することをGの彩色という. 彩色問題とは,与えられたグラフを最小の数の色で彩色することである.一般のグラフにおいて,彩色問題はNP困難であるということは良く知られている.しかし,いくつかの制限されたクラスに属するグラフに対しては,多項式時間逐次アルゴリズムが存在する.本論文では,台形グラフの彩色問題をCREW PRAM上でO(n^3/log n)個のプロセッサを用いてO(log^2 n)時間で解く並列アルゴリズムを示す.ただし, nはグラフGの節点数を表す.
- 社団法人電子情報通信学会の論文
- 1996-12-06
著者
関連論文
- 冗長度削減による関連新聞記事の要約
- グラフの構造的特徴と効率の良い並列アルゴリズムについて (新しいパラダイムとしてのアルゴリズム工学)
- 外平面グラフ上の最大流を求める並列アルゴリズム
- 外平面グラフ上の最大流量を求める並列アルゴリズム(組合せ最適化(3))
- 外平面グラフ上の最大流量を求める並列アルゴリズム
- 2-C-10 A Polynomial Time Algorithm for Obtaining a Minimum Edge Ranking on Two-connected Outerplanar Graphs
- 置換グラフ上における最小節点ランキング全域木問題を解くアルゴリズム (計算機科学基礎理論の新展開)
- 最小節点ランキング全域木問題の計算複雑性について
- 置換グラフ上における最小節点ランキング全域木問題を解くアルゴリズム
- 置換グラフ上における最小節点ランキング全域木問題を解くアルゴリズム
- An algorithm for solving the edge-disjoint path problem on tournament graphs
- in-トーナメントグラフ上のハミルトン閉路を求める並列アルゴリズム(グラフ理論(3))
- 台形グラフの点彩色問題を解く並列アルゴリズム(グラフ・ネットワーク(3))
- 台形グラフの彩色問題を解く並列アルゴリズム
- 2連結グラフ上の与えられた節点を中心とする全域木を求める並列アルゴリズム
- 外平面グラフ上のst-最短経路を求める並列アルゴリズム
- 外平面グラフの最長路問題を解く並列アルゴリズム
- A Simple Near Optimal Parallel Algorithm for Recognizing Outerplanar Graphs
- 外平面グラフ上のs-t最長路を求める並列アルゴリズム(組合せ最適化(3))
- 外平面グラフ上のst-最短経路を求める並列アルゴリズム(グラフ・ネットワーク(3))
- 平面オイラーグラフ上での辺素な路問題を解く並列アルゴリズム
- 確率文脈自由文法が持つ解析木の生成数抑制能力に関する検証
- 平面オイラーグラフの辺素な路問題を解く並列アルゴリズム(理論計算機科学とその周辺)
- 平面オイラーグラフの辺素な路問題を解く並列アルゴリズム(組合せ・グラフ・ネットワーク)
- 1-C-6 置換グラフ上における最小2-組支配集合を求める多項式時間アルゴリズム(最適化・アルゴリズム(2))