グラフの付加辺多重度に上限を持つk-辺連結化問題
スポンサーリンク
概要
- 論文の詳細を見る
各頂点間の付加辺数に上限を持つk-辺連結化問題を次のように定義する:"無向グラフG=(V, E)と関数f:V×V→Z^+^(非負整数)が与えられたとき, G′=(V, E∪E′)がk-辺連結であり, 且つ任意の2頂点u, vの間に付加された辺の本数がf(u, v)を越えないような辺集合E′の中で辺数が最小である辺集合を求めよ."本稿では, まずこの問題がNP-完全であることを示す.次に発見的解法を提案し, その能力を実験的に検証する.
- 1998-04-24
著者
関連論文
- 端子頂点グラフの全域平面部分グラフ抽出法に対する切断対とネット描画変更に基づく高精度化
- グラフの最大誘導木を抽出する発見的解法の点除去に基づく性能強化
- グラフの最大誘導木抽出法の計算機実験による性能評価(デモ展示・ポスター講演,ネットワークプロセッサ,通信のための信号処理,無線LAN/PAN,一般)
- グラフの付加辺多重度に上限を持つk-辺連結化問題
- 3-連結グラフに対する点被覆及び連結点被覆問題について
- プリント基板レイアウト設計における非平面接続数の極小化手法
- 与えられた制約を満たす矩形双対グラフ描画手法
- 障害物を持つ格子スタイナー木問題に対する高速・高精度近似解法(ネットワークプロセッサ, 通信のための信号処理, 符号理論, 一般)
- 障害物を持つ格子スタイナー木問題に対する高速・高精度近似解法(ネットワークプロセッサ, 通信のための信号処理, 符号理論, 一般)
- 障害物を持つ格子スタイナー木問題に対する高速・高精度近似解法(ネットワークプロセッサ, 通信のための信号処理, 符号理論, 一般)
- 障害物を持つ格子スタイナー木問題に対する高速・高精度近似解法
- 障害物を持つ格子スタイナー木問題に対する高速・高精度近似解法
- 障害物を持つ格子スタイナー木問題に対する高速・高精度近似解法
- 障害物を有する格子スタイナー木問題に対する発見的アルゴリズムAGRF
- グラフの最大誘導木を抽出する精度の高い発見的解法(一般)
- グラフの最大誘導木を抽出する精度の高い発見的解法(一般)
- 抑止辺を持つペトリネットの発火系列問題の解法について(デモ展示・ポスター講演,ネットワークプロセッサ,通信のための信号処理,無線LAN/PAN,一般)
- 抑止辺を持つペトリネットの発火系列問題の解法について(デモ展示・ポスター講演,ネットワークプロセッサ,通信のための信号処理,無線LAN/PAN,一般)
- 抑止辺を持つペトリネットの発火系列問題の解法について(デモ展示・ポスター講演,ネットワークプロセッサ,通信のための信号処理,無線LAN/PAN,一般)
- グラフの最大誘導木の発見的抽出法(グラフ,ペトリネット,ニューラルネット,及び一般)
- グラフの最大誘導木の発見的抽出法(グラフ,ペトリネット,ニューラルネット,及び一般)
- グラフの最大誘導木を抽出する発見的解法の点除去に基づく性能強化
- グラフの最大誘導木抽出法の計算機実験による性能評価(デモ展示・ポスター講演,ネットワークプロセッサ,通信のための信号処理,無線LAN/PAN,一般)
- グラフの最大誘導木抽出法の計算機実験による性能評価(デモ展示・ポスター講演,ネットワークプロセッサ,通信のための信号処理,無線LAN/PAN,一般)
- 次数増加禁止点を持つグラフの指定点集合に対する2, 3点連結化問題の解法
- グラフの指定点3点連結化問題に対する解法
- 平面的2辺連結化問題に対する解法の実験的評価
- グラフの格子描画に対するコンパクション手法のプリント基板設計への応用(グラフ,ペトリ,ニューラルネット及び一般)
- グラフの格子描画に対するコンパクション手法のプリント基板設計への応用(グラフ,ペトリ,ニューラルネット及び一般)
- グラフの格子描画に対するコンパクション手法のプリント基板設計への応用
- ペトリネットの最大発火系列問題に対する発見的アルゴリズムFSDB
- ペトリネットインバリアント算出のためのFourier-Motzkin法の改良実装
- A-12-5 時間付ペトリネットによるスケジューリングに対する発見的解法SDS
- A-12-4 指定プレース集合を含むサポートを持つペトリネットインバリアントの算出法
- 各種情報の収集・編集・表示機能を有する大学運営業務支援システムSUMOSYS(システム構築,ライフログ活用技術,オフィス情報システム,ライフインテリジェンス)
- グラフに対する最大供給分割問題解法の性能評価
- 制約付きビア数最小化問題に対する改良解法K-LAG-VおよびK-LAG-VL
- U-MOS:各種情報の収集・編集・表示機能を有する大学運営業務支援システム
- CONTEC : 辺交差の制御機能を有するグラフ描画システム
- グラフの2点または3点連結化アルゴリズムの計算機実験に基づく性能評価
- 複数の指定点集合に対する2辺-及び2点-連結化問題の解法
- 指定矩形形状を持つプリント基板設計のための回路2分割法(ネットワークプロセッサ,通信のための信号処理,符号理論,一般)
- 指定矩形形状を持つプリント基板設計のための回路2分割法(ネットワークプロセッサ,通信のための信号処理,符号理論,一般)
- 2層配線における制約付きビア数最小化手法の高速化と多層配線問題への応用
- AP-1-3 工学系数学基礎における到達目標と学力評価について : EMaTを例として(AP-1.回路基礎教育 : 何をどこまで,パネルセッション,ソサイエティ企画)
- 指定矩形形状を持つプリント基板設計のための回路2分割法(ネットワークプロセッサ,通信のための信号処理,符号理論,一般)
- 指定サイズ矩形内への矩形双対グラフ描画手法
- 動的最短経路問題アルゴリズムの性能比較(グラフ, ペトリ, ニューラルネット及び一般)
- いくつかのハイパーグラフ問題に対するPrimal-Dual近似アルゴリズムについて
- 通信ネットワークの(σ+1)辺連結化問題に対する効率的分散アルゴリズムDECA-1
- 通信ネットワークの(σ+1)辺連結化問題に対する効率的分散アルゴリズムDECA-1
- A-3-4 プリント基板レイアウト設計におけるコンパクション手法の性能強化(A-3.VLSI設計技術,一般セッション)
- EMaT工学系数学統一試験の現状報告
- 端子頂点グラフの全域平面部分グラフ抽出法に対する切断対とネット描画変更に基づく高精度化
- グラフ最大重みマッチング問題に対する高速・高精度の近似解法 : 重み増加パス探索の改良による性能強化(グラフ,ペトリ,ニューラルネット及び一般)
- グラフ最大重みマッチング問題に対する高速・高精度の近似解法 : 重み増加パス探索の改良による性能強化(グラフ,ペトリ,ニューラルネット及び一般)
- グラフ最大重みマッチング問題に対する高速・高精度の近似解法 : 重み増加パス探索の改良による性能強化
- 工学系数学基礎学力の評価と保証 : EMaT工学系数学統一試験について(高専・大学,第90回全国算数・数学教育研究(福島)大会第57回東北地区算数・数学教育研究(福島)大会第46回福島県高等学校教育研究会数学部会日本数学教育学会第90回総会)
- 指定点集合のk辺連結化問題に対する解法
- 禁止領域を持つ格子スタイナー木問題の発見的解法DR
- 格子スタイナー木問題に対する領域分割に基づく並列解法(画像,ネットワークプロセッサ,通信のための信号処理,無線LAN/PAN,一般)
- 格子スタイナー木問題に対する領域分割に基づく並列解法(画像,ネットワークプロセッサ,通信のための信号処理,無線LAN/PAN,一般)
- 格子スタイナー木問題に対する領域分割に基づく並列解法(画像,ネットワークプロセッサ,通信のための信号処理,無線LAN/PAN,一般)
- B-020 工学系数学基礎学力の評価と保証 : グローバルスタンダードをめざして(ポスター発表論文,(B)工学教育に関するGood Practice)
- 6-106 工学系数学統一試験について(口頭発表論文,(13)教育評価・自己点検・評価システム-II)
- 回路の端子頂点グラフモデルにおける全域平面部分グラフ抽出法(通信のための信号処理,符号理論,一般)
- 回路の端子頂点グラフモデルにおける全域平面部分グラフ抽出法(通信のための信号処理,符号理論,一般)
- 回路の端子頂点グラフモデルにおける全域平面部分グラフ抽出法(通信のための信号処理,符号理論,一般)
- 重み増加パス探索改良によるグラフ最大重みマッチング近似解法の性能強化 (第20回 回路とシステム軽井沢ワークショップ論文集) -- (アルゴリズム)
- 工学系数学の標準的学力検査に向けて--工学系数学統一試験 (シンポジウム 学士課程における理系基礎教育--教養教育からキャリア教育まで)
- 障害物を有する格子グラフにおけるスタイナー木構成法 : スタイナー候補点の改良選択法による性能強化(グラフ,ペトリ,ニューラルネット及び一般)
- 障害物を有する格子グラフにおけるスタイナ一木構成法 : スタイナー候補点の改良選択法による性能強化(グラフ,ペトリ,ニューラルネット及び一般)
- 反転禁止部分グラフを含む平面グラフ抽出法の効率化(FPGAとその応用及び一般)
- 反転禁止部分グラフを含む平面グラフ抽出法の効率化(FPGAとその応用及び一般)
- 反転禁止部分グラフを含む平面グラフ抽出法の効率化(FPGAとその応用及び一般)
- 反転禁止部分グラフを有する平面グラフ抽出法
- 反転禁止部分グラフを有する平面グラフ抽出法
- 描画固定部分グラフを有するグラフにおける全域平面グラフの階層的抽出法
- グラフ彩色問題に対するPCクラスタ並列分枝限定解法の性能評価
- 最小重み点被覆問題に対する並列分枝限定法の性能評価
- 最小費用流問題アルゴリズムに対する実験的性能評価(セッション4)
- 禁止領域を持つ格子スタイナー木問題の発見的解法
- Terminal Representation Graphに対する平面的スタイナー森を求める発見的解法
- 禁止領域を持つ格子スタイナー木問題の発見的解法
- Terminal Representation Graphに対する平面的スタイナー森を求める発見的解法
- 禁止領域を持つ格子スタイナー木問題の発見的解法
- Terminal Representation Graphに対する平面的スタイナー森を求める発見的解法
- 最大重みマッチング問題に対する2つの近似解法
- 指定形状多層プリント基板レイアウト設計のための矩形双対グラフ構成法 (信号処理)
- 指定形状多層プリント基板レイアウト設計のための矩形双対グラフ構成法 (回路とシステム)
- 指定形状多層プリント基板レイアウト設計のための矩形双対グラフ構成法 (通信方式)
- 描画固定部分グラフを有するグラフの平面性 (回路とシステム)
- 動的最短経路問題アルゴリズムの性能比較(グラフ, ペトリ, ニューラルネット及び一般)
- AP-1-3 工学系数学基礎における学力評価について : EMaTを例として(AP-1.回路基礎教育:何をどこまで,パネルセッション,ソサイエティ企画)
- 描画固定部分グラフを有するグラフの平面性(一般)
- 指定形状多層プリント基板レイアウト設計のための矩形双対グラフ構成法(ネットワークプロセッサ,通信のための信号処理,無線LAN/PAN,一般)
- 指定形状多層プリント基板レイアウト設計のための矩形双対グラフ構成法(ネットワークプロセッサ,通信のための信号処理,無線LAN/PAN,一般)
- 指定形状多層プリント基板レイアウト設計のための矩形双対グラフ構成法(ネットワークプロセッサ,通信のための信号処理,無線LAN/PAN,一般)
- 描画固定部分グラフを有するグラフの平面性
- 格子グラフ上の二重入れ子状矩形境界間を接続する互いに点素なパスについて(学生セッション)