次数増加禁止点を持つグラフの指定点3辺連結化問題に対する線形時間アルゴリズム
スポンサーリンク
概要
- 論文の詳細を見る
次数増加禁止点を持つグラフの指定点集合にタイするk辺連結化問題kECA(G, S, D)は次のように定義される:"正整数k, 無向多重グラフG=(V, E), 指定点集合S⊊V, 次数増加可能点集合D⊊Vが与えられたときに, Dの2点を結ぶ辺の集合E′で, (V, E∪E′)においてSのどの2点間にもk本以上の辺素な道が存在するような最小本数の辺集合E′を求めよ."V-Dの点をGの次数増加禁止点と呼ぶ.本稿では, 3ECA(G, S, D)に対して, 解の存在性判定と解を求めることがO(|V|+|E|)時間で実行できることを示す.
- 社団法人電子情報通信学会の論文
- 2000-07-18
著者
-
間島 利也
広島国際大学工学部
-
渡邉 敏正
広島大学工学部第二類回路・システム工学講座
-
間島 利也
広島国際大学 社会環境科学部 情報通信学科
-
間島 利也
広島市立大学情報科学部情報工学科
-
渡邉 敏正
広島大学工学部第二類(電気系)
-
渡邉 敏正
広島大学工学部
関連論文
- 点次数の増加上限制約を持つ2点連結グラフに対する線形時間3点連結化アルゴリズム
- 枝重み付きカクタスに対する発火系列問題の解法
- サイクリックカクタスに対する発火系列問題の解法について
- 次数制約付きのグラフに対する指定点3辺連結化問題の解法
- 次数制約付きのグラフに対する指定点3辺連結化問題の解法
- 次数制約付きのグラフに対する指定点k辺連結化について
- 次数増加禁止点を持つグラフの指定点3辺連結化問題に対する線形時間アルゴリズム
- 次数増加禁止点を持つグラフの指定点3点連結化問題に対する線形時間アルゴリズム
- 次数増加禁止点を持つグラフの指定点集合に対する2, 3点連結化問題の解法
- 次数増加禁止点を持つグラフに対する点連結度増加問題
- 次数増加禁止点を持つグラフに対する点連結度増加問題
- グラフの指定点集合に対する3点連結化問題の解法
- グラフの指定点3点連結化問題に対する解法
- グラフの局所辺連結度増加問題に対する近似解法
- グラフのk辺連結化問題に対する新しい近似解法
- ペトリネットの最小初期マーキング問題に対する発見的解法
- ペトリネット発火系列問題に対する発見的アルゴリズムFSDTとMAX SAT解法への応用
- ペトリネット発火系列問題に対する発見的アルゴリズムFSDTとMAX SAT解法への応用
- 指定ノード集合を含むサポートを持つペトリネットインバリアントの算出アルゴリズムFMSN
- 指定ノード集合を含むサポートを持つペトリネットインバリアントの算出アルゴリズムFMSN
- 次数制約付きのグラフに対する指定点2点連結化問題の解法
- λ-辺連結グラフにおける指定点集合の(λ+1)-辺連結化のための2-近似アルゴリズムFSA+1
- グラフの最小コスト3-点連結化問題に対する近似アルゴリズム
- ペトリネット発火系列問題の概説
- ペトリネット発火系列問題の概説
- ペトリネットのサイフォン・トラップサポート集合に基づくインバリアント算出法
- CST2000-9 ペトリネットの最小初期マーキング問題に対する発見的アルゴリズムFMDB
- サイクリックカクタスに対する発火系列問題の解法について
- TD-1-11 平面全域部分グラフ抽出法とその応用
- 1カウンタ言語を受理するRTAの構成法
- SA-6-1 ペトリネットにおけるサイフォンの抽出法とその応用
- SA-7-2 データから見たCST研究会 : これまでとこれから
- SA-6-8 通信ネットワーク3辺連結化のための分散アルゴリズム
- コンカレント工学研究会の活動を振り返って : 歴代委員長からのメッセージ(一般,コンカレントシステム及び一般)
- 時間付きペトリネットによるスケジューリングのための発見的アルゴリズムSDS
- 時間付きペトリネットによるスケジューリングのための発見的アルゴリズムSDS
- A-12-9 Fourier-Motzin法によるペトリネットインバリアントの効率的算法
- CST2000-12 Fourier-Motzkin法によるペトリネットインバリアント計算の効率化
- A-12-6 ペトリネットの発火系列問題の発見的解法について
- CST2000-8 ペトリネット発火系列問題とその関連問題に対する発見的アルゴリズム
- ペトリネットにおけるトークン数下限制約を持つ発火系列問題
- 付加辺の多重度に上限を持つ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)
- プリント基板設計における非平面接続要求の部品下領域を利用した配線手法
- プリント基板設計における非平面接続要求の部品下領域を利用した配線手法
- プリント基板設計における非平面接続要求の部品下領域を利用した配線手法
- ペトリネットの発火系列問題に対する新しい発見的解法FSD
- ペトリネットの指定プレース集合を含むサイフォン抽出法
- ペトリネットの発火系列問題に対する新しいヒューリスティックアルゴリズム
- ペトリネットの発火系列問題に対する新しいヒューリスティックアルゴリズム