帯域幅連続多重彩色の近似アルゴリズム(一般)
スポンサーリンク
概要
- 論文の詳細を見る
グラフGの各点ηには正整数の重みb(v)が,各辺(v,w)には非負整数の重みb(v,w)が与えられているとする.このとき,Gの帯域幅連続多重彩色(以下か彩色と呼ぶ)では,Gの各点vに連続したb(v)個の正整数を色として割り当て,Gのどの辺(v,w)に対しても,端点vに割り当てられた各整数が端点wに割り当てられたどの整数よりもb(v,w)+1以上離れるようにしたい.Gの点に割り当てられる最大の整数(色)はそのb-彩色のスパンと呼ばれる.与えられたグラフのか彩色でスパンが最小なものを求める問題が,b-彩色問題である.本文ではひ彩色問題に対して,高速な4つの近似アルゴリズムを与える.
- 一般社団法人電子情報通信学会の論文
- 2013-08-27
著者
関連論文
- ブール剰余関数を計算するしきい値論理回路のサイズとエネルギー複雑度のトレードオフ
- 木の均一分割問題
- 3連結平面グラフの細分の格子凸描画
- 多値2入力論理関数のAND-EXOR論理式の最小化(理論,回路,ネットワークプロセッサ,通信のための信号処理,無線LAN/PAN,一般)
- 需要点と供給点があるグラフの分割問題の近似可能性
- 内部三角化平面グラフの開矩形勢力描画
- 平面グラフの矩形外周格子凸描画
- 現在のWebにおけるHITSについて
- 平面グラフの外頂点数最小の凸描画
- 木の最小コスト辺彩色のマッチングへの帰着
- 多値2入力論理関数のAND-EXOR論理式の最小化(理論,回路,ネットワークプロセッサ,通信のための信号処理,無線LAN/PAN,一般)
- 多値2入力論理関数のAND-EXOR論理式の最小化(理論,回路,ネットワークプロセッサ,通信のための信号処理,無線LAN/PAN,一般)
- 対称関数を計算するユネイト回路のサイズとエネルギーのトレードオフ
- ブール剰余関数を計算するしきい値論理回路のサイズとエネルギー複雑度のトレードオフ
- A-026 グラフ分割を用いた格子描画法(モデル・アルゴリズム・プログラミング,一般論文)
- 木の最小コスト辺彩色のマッチングへの帰着
- 需要点と供給点のある木のコスト最小分割
- 内部3連結グラフの格子凸描画
- 鍵共有グラフを用いた絶対に安全なメッセージ送信
- 需要点,供給点,辺容量を持つ木の分割アルゴリズム
- 内部3連結グラフの格子凸描画(情報・システム基礎,学生論文)
- グラフの帯域幅連続多重彩色を求めるアルゴリズム
- グラフの帯域幅連続多重彩色を求めるアルゴリズム
- 帯域幅連続多重彩色の近似アルゴリズム(一般)