平面グラフにおける辺遊離操作と辺連結度増大問題について
スポンサーリンク
概要
- 論文の詳細を見る
本論文では, k辺連結な平面グラフ G (ただし, kは偶数あるいは k=3)の任意の点 s において, グラフのk辺連結性と平面性を同時に保つような完全な辺遊離操作が存在することを示し, そのような辺遊離操作を求めるO(n^3log n)時間のアルゴリズムを与える. ここで, n は点の数. kが5以上の奇数の場合にはそのような辺遊離操作を持たないグラフの例が存在する. 新しい辺遊離操作を用いると, 外平面グラフに最小数の辺を加え平面性を保ったままk辺連結に最適に増大させる問題をO(n^3log n)時間で解くことができる(ただし, kは偶数あるいは k=3).
- 一般社団法人情報処理学会の論文
- 1998-01-22
著者
関連論文
- 格子型光波網におけるパス割り当て問題に関する考察
- 辺連結度増加関数をO^^〜(mn)時間で計算するアルゴリズム
- フローゲームの凸性について(ゲーム理論(2))
- マトロイド上の最小基ゲーム
- ある種の平面有向ネットワークの多品種流問題について(計算アルゴリズムと計算量の基礎理論)
- 最小容量カットアルゴリズムのプログラムによる効率の良い実現法
- 多重グラフにおける(λ+1)-カット
- 無向グラフ上の辺分離問題を解く簡単なO(mn)時間アルゴリズム
- グラフ上の搬送スケジューリング問題の計算の複雑さについて(スケジューリング(2))
- グラフ上の搬送スケジューリング問題の計算の複雑さについて
- サブツアー交換交叉に対する二つのコメント
- サブツアー交換交叉に対する2つのコメント
- ジャンケンのトーナメント表現と意味のある拡張(アルゴリズムと計算量理論)
- T-混合カットにおける領域間連結度の性質(グラフ・ネットワーク(5))
- 最小カット問題の簡潔かつ構成的な証明
- 平面グラフにおける辺遊離操作と辺連結度増大問題について
- 組合せ最適化ゲーム
- 反復ラインダイグラフの深さの浅い独立全域木
- グラフのサム数に対する上下界について
- 格子型光波ネットワークの再構成アルゴリズムについて
- 光波ネットワークのノード再配置アルゴリズムについて
- 双方向マンハッタン・ストリート・ネットワークの網再構成について