著者

沖 忠親 田岡 智志 渡邉 敏正

雑誌

研究報告アルゴリズム(AL)

巻号頁・発行日

vol.2010-AL-129, no.7, pp.1-8, 2010-02-26

---

2 部グラフの k 辺連結化問題 (以下,UW-Bipartite- (k+1) ECA (*, MA) と略記) は以下のように定義される: 「無向 2 部グラフ G = (V + ∪V-,E) が与えられたとき,辺付加後のグラフ G' = (V + ∪V- ,E∪E') が (k + 1) 辺連結 2 部グラフであるような最小の付加辺集合 E' を求めよ.」本稿では,G が k 辺連結であるときに最適解を算出する高速アルゴリズムを提案し,k ∈ {1, 2} のとき線形時間で解けることを示す.

著者

慶祐 俊文 高藤 大介 田岡 智志 渡邉 敏正

雑誌

情報処理学会研究報告アルゴリズム(AL)

巻号頁・発行日

vol.2006, no.7(2006-AL-104), pp.67-74, 2006-01-20

---

最小費用流問題とは,「有向グラフG(V E)と各辺(i j)∈Eに対する単位フローあたりの非負整数コストc(i j),各辺に流すフロー上界値の非負整数容量u(i j)及び始点から終点に流す最大フローkが与えられたとき,流量がkでありかつ,各辺に流れるフローf(i j)とコストc(i j)の積の総和で求められるz(f)が最小であるフローfを求めよ」と定義される.本問題は輸送計画問題などに広く応用され,本問題を高速に解くことは重要である.本稿では,最小費用流問題における既存解法アルゴリズムの性能を計算機実験により評価を行い,RELAXが最も高速な解法であることを示す.

著者

田岡 智志 渡邊 敏正

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. COMP, コンピュテーション (ISSN:09135685)

巻号頁・発行日

vol.99, no.549, pp.73-80, 2000-01-19

参考文献数

24

---

k辺連結化問題とは、与えられた無向グラフG=(V, E)に付加して得られるグラフG'=(V, E∪E')がk辺連結となるような最小辺集合E'を求める問題である。本稿では、"辺付加により新たに多重辺を作らない"、という条件を加えたk辺連結化問題を扱う。一般には、この問題はNP-hardであり、Gの葉と呼ばれる点集合の総数により問題の難しさが変わることが知られている。本稿では、Gの辺連結度をσとするとき、k=σ+1且つGが2σ+6個未満の葉を持つ場合を考え、リーフグラフの最大マッチングにより生成される葉数と不飽和葉数の関係により、多項式時間の最適解法、あるいは、近似比3 / 2の近似解法、それぞれを提案する。

著者

沖 忠親 田岡 智志 渡邉 敏正

出版者

情報処理学会

雑誌

研究報告アルゴリズム(AL) (ISSN:09196072)

巻号頁・発行日

vol.2010, no.7, pp.1-8, 2010-02-26

---

2 部グラフの k 辺連結化問題 (以下,UW-Bipartite- (k+1) ECA (*, MA) と略記) は以下のように定義される: 「無向 2 部グラフ G = (V + ∪V-,E) が与えられたとき,辺付加後のグラフ G' = (V + ∪V- ,E∪E') が (k + 1) 辺連結 2 部グラフであるような最小の付加辺集合 E' を求めよ.」本稿では,G が k 辺連結であるときに最適解を算出する高速アルゴリズムを提案し,k ∈ {1, 2} のとき線形時間で解けることを示す.The k-edge-connectivity augmentation problem of bipartite graphs (UW-Bipartite-kECA(*, MA) for short) is defined as follows: "Given an undirected bipartite graph G = (V+ ∪V-,E), find a smallest set E' of edges such that G' = (V+ ∪V-,E∪E') is a k-edge-connected bipartite one." In this paper we propose a fast algorithm for finding an optimum solution to UW-Bipartite-(k + 1)ECA(*, MA) when G is k-edge-connected with k > 0, and show that it can be solved in linear time for k ∈ {1, 2}.

著者

井口 貴志 高藤 大介 田岡 智志 渡邉 敏正

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. CAS, 回路とシステム (ISSN:09135685)

巻号頁・発行日

vol.105, no.387, pp.41-46, 2005-11-03

---

辺重み付き有向グラフをネットワークと呼び, 辺重みの増減という辺操作を考える.なお辺重みを無限から有限に減少(それぞれ, 有限から無限に増加)させることは, 辺の追加(辺の削除)に対応する.動的最短経路問題(DSPPと略記)は次のように定義される: "任意のネットワーク, ソースと呼ばれる指定頂点s, 任意の辺操作系列が与えられたとき, 各辺操作の実行後のネットワークにおける最短経路木を再構成せよ".DSPPの応用として, OSPFやIS-ISのようなリンクステート・アルゴリズムに基づいたルーティングプロトコルにおいて, DSPPを効率良く解くことが必要となる.大規模なネットワークと非常に長い辺操作系列に対する実験結果では, Narvaez(2000年)らがで提案したNST(BF)が, 我々が試した現在の10種類の解法の中で最も高速に解を求めることを示した.また, DSPPを解くには, 静的な解法を繰り返して解くよりも, 動的な解法の方が高速に解を求めることも示した.