木の最小コスト点彩色の列挙と一意性について
スポンサーリンク
概要
- 論文の詳細を見る
本稿では,木に対する最小コスト点彩色が一意でない場合,それらを重複無く全て列挙するアルゴリズムを提案する.一般グラフの最小コスト点彩色問題はNP困難であるが,1997年,Kroon et. al.は木に対する線形時間アルゴリズムを提案した.しかし,最小コスト点彩色が一意で無い場合,それらを列挙するアルゴリズムはまだ提案されていない.そこで我々は初めて列挙アルゴリズムを提案する.本稿では,与えられた木Tに対し,最小コスト点彩色を1つ当たりO(nd2)時間で列挙するアルゴリズムを提案する.ただし,nはTの頂点数,dはTの最大次数である.また,木の最小コスト点彩色に対して任意の十分大きな色数が与えられた時,その色を全て使用する木の特徴付けを行う.
- 2013-02-22
著者
関連論文
- A polynomial-time perfect sampler for the Q-Ising with local fields (アルゴリズムと計算機科学の数理的基盤とその応用--RIMS研究集会報告集)
- 頂点独立なノイズ付きQ-イジング模型のための多項式時間パーフェクトサンプラー
- あみだくじの高速列挙
- Enumeration of Perfect Sequences of Chordal Graph (Acceleration and Visualization of Computation for Enumeration Problems)
- 2-E-17 Enumeration of Perfect Sequences of Chordal Graph
- コーダルグラフの完全列の列挙
- 組合せ構造の列挙とサンプリング(代数、形式言語、計算システム理論とその応用)
- Approximation algorithm for generating B^m × J contingency tables
- 冒険とOR(21世紀を最適化する女性たち)
- 分割表の列挙とグレブナー基底 (最適化の数理とアルゴリズム)
- 分割表の列挙とランダム生成 (グレブナ-基底の理論的有効性と実践的有効性)
- Integer Programming and Grobner Bases (Algebraic Combinatorics on Convex Polytopes)
- A SURVEY OF ALGORITHMS FOR CALCULATING POWER INDICES OF WEIGHTED MAJORITY GAMES
- 2部グラフの辺彩色を列挙するアルゴリズムの計算時間の解析
- 木の最小コスト点彩色の列挙と一意性について