3-連結グラフの3分割アルゴリズム
スポンサーリンク
概要
- 論文の詳細を見る
ここで,グラフの3分割問題とは,(1)無向単純グラフG,(2)互いに異なるGの3個の点a_1,a_2,a_3,(3)n_1+n_2+n_3=nなる自然数n_1,n_2,n_3を入力したときに,Gの三つの素な連結部分グラフG_1,G_2,G_3で各G_iがa_i を含み,その点数がn_iであるものを求める問題である.nはグラフGの点数である.グラフGが3-連結ならば3分割問題には必ず解が存在することをGyori とLovaszは独立に証明している.しかしその証明からは多項式時間アルゴリズムは得られない.なお,入力グラフGが3-連結と限らない一般の場合には,3分割問題はNP-困難であることが知られている.本文では3-連結グラフGの3分割問題を解く多項式時間のアルゴリズムを与えるそのアルゴリズムは二つのステップからなる.まず,3-連結性を保ったままGから何本かの辺を除去して辺数をO(n)に減らす.この部分はGの辺数に比例した時間で終了する次に得られた辺疎なグラフを用いて3分割問題を解く.この部分はグラフの辺数と点数の積に比例した時間で終了する.結局アルゴリズムは全体でO(n^2)時間で終了する.
- 一般社団法人情報処理学会の論文
- 1990-05-15
著者
-
西関 隆夫
東北大学大学院情報科学研究科
-
鈴木 均
茨城大学工学部
-
鈴木 均
東北大学工学部情報工学科
-
西関 隆夫
東北大学工学部情報工学科
-
宮野 浩
東京工業大学
-
上野 修一
東京工業大学
-
高橋 奈穂美
東北大学工学部通信工学科
-
上野 修一
東京工業大学工学部電気電子工学科
-
宮野 浩
東京工業大学工学部電気電子工学科
-
上野 修一
東京工大
-
西関 隆夫
東北大学工学部
関連論文
- バランスのよいグラフ分割を用いた平面グラフの小面積格子描画法
- ブール剰余関数を計算するしきい値論理回路のサイズとエネルギー複雑度のトレードオフ
- 木の均一分割問題
- 3連結平面グラフの細分の格子凸描画
- 多値2入力論理関数のAND-EXOR論理式の最小化(理論,回路,ネットワークプロセッサ,通信のための信号処理,無線LAN/PAN,一般)
- 需要点と供給点があるグラフの分割問題の近似可能性
- 内部三角化平面グラフの開矩形勢力描画
- 平面グラフの矩形外周格子凸描画
- 現在のWebにおけるHITSについて
- 平面グラフの外頂点数最小の凸描画
- 直並列グラフの折れ曲がり最小の直交描画
- グラフの距離辺彩色アルゴリズム
- 需要点と供給点のあるグラフの分割
- 鍵共有グラフのt-安全性について
- 平面グラフの内部矩形描画
- 需要と供給の木の分割
- 平面グラフで最短非交差道を求めるアルゴリズム
- 平面上で二組の端子対の間の長さの和が最小で辺素な道を求めるアルゴリズム
- 軸平行多角形障害物がある平面上の最短路
- 4つの端子からの距離の和が小さい領域を求めるアルゴリズム
- 障害物と交差領域のある平面上での最短な2本の道
- 平面領域で長さの総和最小な非交差道を求めるアルゴリズム
- 軸平行多角形障害物がある平面における最短路アルゴリズム
- 平面上で2本の最短な道を求めるアルゴリズム
- 3連結平面グラフの非分離耳分割を求める線形アルゴリズム
- 平面グラフで長さの総和最小な非交差道を求めるアルゴリズム
- Efficient Algorithms for Edge-Coloring Partial k-Trees
- A Parallel Algorithm for Drawing Planar Graphs on the Grid
- 3-連結グラフの3分割アルゴリズム
- 平面グラフで林を求めるアルゴリズム--指定された2つの面の両方にまたがるネットがある場合
- 平面グラフで内素な道を求めるアルゴリズム
- 平面グラフで林を求めるアルゴリズム--各ネットの端子が指定された2つの面の片方にある場合
- 可変優先キューとその応用(計算アルゴリズムの基礎理論)
- 入れ子状長方形格子グラフの辺素な道
- 入れ子状長方形領域で辺素な道を求めるアルゴリズム (ネットワ-ク問題論文)
- ある種の平面ネットワ-クに対する多種フロ-アルゴリズム
- 平面多種フロ-と最短路
- 平面的グラフの矩形描画
- 部分k-木で辺素な道をみつけるアルゴリズム
- 部分k木を全彩色する多項式時間アルゴリズム
- 最大カットセット及び2部グラフ化に関するNP-完全問題
- 平面グラフで長さの総和最小な非交差道を求めるアルゴリズム
- 3-連結グラフの3分割アルゴリズム
- 可変形状ラベリング問題に対するアルゴリズム
- 木の最小コスト辺彩色のマッチングへの帰着
- 一方向性落し戸環準同型に基づくメッセージ確認方式
- 非可換環上の多重署名についての考察
- 環準同型の性質をもつ暗号化関数の一構成
- 離散対数暗号系に付随する言語の複雑さについて
- 離散対数暗号に付随する言語の複雑さについて
- 平面多種フロ-アルゴリズム
- 平面グラフの多種フロ-を求める多項式時間アルゴリズム
- 平面3-グラフの折れ曲がり数最少な直交描画
- 3連結3次平面グラフを最小個のベンドを用いて直交描画する線形時間アルゴリズム
- 4連結平面グラフを4分割する線型時間アルゴリズム
- 多値2入力論理関数のAND-EXOR論理式の最小化(理論,回路,ネットワークプロセッサ,通信のための信号処理,無線LAN/PAN,一般)
- 多値2入力論理関数のAND-EXOR論理式の最小化(理論,回路,ネットワークプロセッサ,通信のための信号処理,無線LAN/PAN,一般)
- 平面グラフの面の面積を指定した8角形描画
- 対称関数を計算するユネイト回路のサイズとエネルギーのトレードオフ
- ブール剰余関数を計算するしきい値論理回路のサイズとエネルギー複雑度のトレードオフ
- A-026 グラフ分割を用いた格子描画法(モデル・アルゴリズム・プログラミング,一般論文)
- グラフの距離辺彩色アルゴリズム
- 直並列グラフの折れ曲がり最小の直交描画
- 2-連結グラフの2分割アルゴリズム
- 平面グラフの内部矩形描画
- 単調な木の平面連続変形
- 平面グラフで非交差スタイナ林を求めるアルゴリズム
- 端子からのL_1距離の和が最小な領域を求めるアルゴリズム
- 平面グラフで非交差な林を求めるアルゴリズム
- 端子からのL_1距離の和が最小な領域を求めるアルゴリズム
- 平面グラフの正規分割,リアライザ,Schnyderラベル付けおよび外三角凸描画
- 多重グラフの枝彩色アルゴリズム
- グラフの近似枝彩色アルゴリズム
- グラフの辺をf彩色する近似アルゴリズム
- グラフのfg辺彩色数の上界
- グラフのf彩色 (ネットワ-ク問題論文)
- グラフ問題の計算時間の下界について
- 格子グラフで枝素な道を求める線形時間アルゴリズム
- グラフ変形操作の効率的アルゴリズム
- 直並列グラフと計算複雑度
- 最大カットの近似算法 (組合せ構造とグラフ理論 II)
- ランダムグラフの統計的解析 (組合せ構造とグラフ理論 II)
- 極大2部マトロイドについて (組合せ構造とグラフ理論 II)
- 多種ネットワ-クフロ-とVLSI配線への応用
- 一般的なアクセス構造を実現する秘密共有法
- 4連結平面グラフの格子凸描画
- 4連結平面グラフの格子描画
- 4連結平面グラフの4本の独立全域木を求める線形時間アルゴリズム
- 4連結平面グラフの格子凸描画
- 4連結平面グラフの格子凸描画
- ランダムグラフの統計解析
- グラフ処理プログラム : GRAMP
- GO TO文最小プログラム記述の計算手数について
- 直並列グラフ及びDチャ-トの判定法(技術談話室)
- 量子カード配布
- A-3 量子カード配布(計算量・量子計算,A.アルゴリズム・基礎)
- 平面グラフの箱-矩形描画
- 平面グラフの格子矩形描画
- 部分k木で辺素な道を見つけるアルゴリズム
- サイト間グラフの最小カットを用いたウェブ上のコミュニティ発見法