付加辺の多重度に上限を持つk辺連結化問題に対する発見的解法EAM
スポンサーリンク
概要
- 論文の詳細を見る
辺対の多重度に上限のあるk辺連結化問題は次のように定義される:"グラフG = (V, E)と関数f : V × V → Z^+(非負整数)が与えられたとき,G^1 = (V, E∪E^1)がk辺連結であり,且つ任意の頂点対u, vに対し,u, v間に付加される辺数がf (u, v)を越えないような付加辺集合E^1の中で,辺数が最小となるものを見つけよ".この問題はNP-完全であることが既に知られている.本稿では,この問題に対する新しい発見的解法EAMを提案し,実験により既存の発見的解法と比較して,その性能の良さを示す.
- 社団法人電子情報通信学会の論文
- 1999-12-10
著者
関連論文
- 枝重み付きカクタスに対する発火系列問題の解法
- サイクリックカクタスに対する発火系列問題の解法について
- 次数増加禁止点を持つグラフの指定点3辺連結化問題に対する線形時間アルゴリズム
- 次数増加禁止点を持つグラフの指定点3点連結化問題に対する線形時間アルゴリズム
- 次数増加禁止点を持つグラフに対する点連結度増加問題
- グラフの指定点集合に対する3点連結化問題の解法
- ペトリネットの最小初期マーキング問題に対する発見的解法
- ペトリネット発火系列問題に対する発見的アルゴリズムFSDTとMAX SAT解法への応用
- ペトリネット発火系列問題に対する発見的アルゴリズムFSDTとMAX SAT解法への応用
- 指定ノード集合を含むサポートを持つペトリネットインバリアントの算出アルゴリズムFMSN
- 指定ノード集合を含むサポートを持つペトリネットインバリアントの算出アルゴリズムFMSN
- ペトリネット発火系列問題の概説
- ペトリネット発火系列問題の概説
- ペトリネットのサイフォン・トラップサポート集合に基づくインバリアント算出法
- CONTEC : 辺交差の制御機能を有するグラフ描画システム
- CST2000-9 ペトリネットの最小初期マーキング問題に対する発見的アルゴリズムFMDB
- サイクリックカクタスに対する発火系列問題の解法について
- TD-1-11 平面全域部分グラフ抽出法とその応用
- SA-6-1 ペトリネットにおけるサイフォンの抽出法とその応用
- SA-6-8 通信ネットワーク3辺連結化のための分散アルゴリズム
- コンカレント工学研究会の活動を振り返って : 歴代委員長からのメッセージ(一般,コンカレントシステム及び一般)
- 時間付きペトリネットによるスケジューリングのための発見的アルゴリズムSDS
- 時間付きペトリネットによるスケジューリングのための発見的アルゴリズムSDS
- A-12-9 Fourier-Motzin法によるペトリネットインバリアントの効率的算法
- CST2000-12 Fourier-Motzkin法によるペトリネットインバリアント計算の効率化
- A-12-6 ペトリネットの発火系列問題の発見的解法について
- CST2000-8 ペトリネット発火系列問題とその関連問題に対する発見的アルゴリズム
- ペトリネットにおけるトークン数下限制約を持つ発火系列問題
- 付加辺の多重度に上限を持つk辺連結化問題に対する発見的解法EAM
- 付加辺の多重度に上限を持つk辺連結化問題に対する発見的解法EAM
- 最大独立点問題解法に基づくTerminal-Vertex Graphにおける全域平面部分グラフ抽出
- D-1-4 通信ネットワークの2辺連結化問題に対する分散アルゴリズムRDBCA
- 非交差道を用いたプリント基板配線領域の見積り手法
- 層割当てのためのネット集合分割に基づく制約付きビア数最小化手法PNLA
- 層割当てのためのネット集合分割に基づく制約付きビア数最小化手法PNLA
- 層割当てのためのネット集合分割に基づく制約付きビア数最小化手法PNLA
- 通信ネットワークの3辺連結化分散アルゴリズム3DECA
- 部分論理回路の縮約に基づくFPGAテクノロジーマッピング法
- Efficient Augmentation to Construct $(\sigma + 1)$-Edge-Connected Simple Graphs (Algorithm Engineering as a New Paradigm)
- グラフの多重辺付加を許さない4辺連結化問題
- グラフの多重辺付加を許さない辺連結化問題
- グラフの多重辺付加を許さない4辺連結化問題
- プリント基板設計における非平面接続要求の部品下領域を利用した配線手法
- プリント基板設計における非平面接続要求の部品下領域を利用した配線手法
- プリント基板設計における非平面接続要求の部品下領域を利用した配線手法
- ペトリネットの発火系列問題に対する新しい発見的解法FSD
- ペトリネットの指定プレース集合を含むサイフォン抽出法
- ペトリネットの発火系列問題に対する新しいヒューリスティックアルゴリズム
- ペトリネットの発火系列問題に対する新しいヒューリスティックアルゴリズム