k-辺連結性を保存する疎なグラフを求める効率の良いNCアルゴリズム
スポンサーリンク
概要
- 論文の詳細を見る
多重グラフGのk-辺連結性を保持する疎な全域部分多重グラフを、CRCW(ARBITRARY)PRAM上でO(k(n+m'))個のプロセッサを使用し、O((logkn)(logk)^2(logn)^2))時間で計算するNCアルゴリズムを与える。ここで、nはGの頂点数、m'はGを単純化して得られるグラフの辺の数を表す。
- 社団法人電子情報通信学会の論文
- 1998-06-23
著者
関連論文
- MAX-2-SATに対する分枝限定法
- 矩形パッキング問題に対する厳密解法
- MAX-2-SATに対する分枝限定法
- グラフの極大成分を用いた生物ネットワークの解析(遺伝子発現・ネットワーク)
- 根付き三角化平面的グラフの列挙
- ビーコン配置問題と対偶問題に対する効率的近似アルゴリズム
- 最小費用枝架設問題に対する近似解法
- P2Pシステムのための深さ最小木の構築について
- P2Pシステムのための深さ最小木の構築について(マルチメディア(システム/通信/ネットワーク),放送通信連携サービスとその品質,一般)
- P2Pシステムのための深さ最小木の構築について(マルチメディア(システム/通信/ネットワーク),放送通信連携サービスとその品質,一般)
- P2Pシステムのための深さ最小木の構築について(マルチメディア(システム/通信/ネットワーク),放送通信連携サービスとその品質,一般)
- 容量付木状経路問題に対する近似解法
- 反復構成特徴に基づいた分類器の実データへの拡張
- 特徴ベクトルに基づく木状の化学分子の列挙アルゴリズム(セッション5)
- 特徴ベクトルに基づく木状の化学分子の列挙アルゴリズム(セッション5)
- 光バースト交換網における専用波長を用いた全域木形成による衝突回避法
- ビーコン配置問題と対偶問題に対する効率的近似アルゴリズム
- パス構造グラフにおける納期違反コスト最小化選択的配達スケジューリング(機械要素,潤滑,工作,生産管理など)
- 食品の袋詰め最適化問題に対する動的計画法(機械要素,潤滑,工作,生産管理など)
- 時間依存最短路問題に対するA^*アルゴリズム
- 組合せの効率的な生成法 (計算機科学とアルゴリズムの数理的基礎とその応用)
- de Bruijn及びKautzダイグラフのページナンバー
- k-辺連結性を保存する疎なグラフを求める効率の良いNCアルゴリズム
- 反復ラインダイグラフの深さの浅い独立全域木
- 平面無向グラフで2番目に短い経路を求めるアルゴリズム
- サイクル上の忌避型施設配置ゲームにおける,3-候補地もしくは4-候補地の戦略耐性メカニズム (最適化の基礎理論と応用)