著者

沖 忠親 田岡 智志 渡邉 敏正

雑誌

研究報告アルゴリズム(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が最も高速な解法であることを示す.

著者

渡邉 敏正 高藤 大介

出版者

Japanese Society for Engineering Education

雑誌

工学教育 (ISSN:13412167)

巻号頁・発行日

vol.57, no.1, pp.1_78-1_83, 2009 (Released:2009-02-10)

参考文献数

3

被引用文献数

1 1

---

The aim of Engineering Mathematics Test (EMaT) is to make sure what essentials in curriculum of Engineering Mathematics is, and to assess university students’ core academic competence and achievement of Engineering Mathematics, helping assurance of students’ academic ability. It is useful for professors to evaluate teaching effect of the classes, and this evaluation would help them improve curricula. Scores can be available for both graduate school entrance examinations and employment tests, leading to selecting persons with basic academic ability in Engineering Mathematics. The scope includes fundamentals in Calculus, Linear Algebra, Differential Equations, and Probability and Statistics. It is open to all students free of charge, and is annually given once in December. In 2007, 2,396 students from 35 universities took EMaT, and the total number of students who have taken EMaT in these 5 years is 6,240.

著者

沖 忠親 田岡 智志 渡邉 敏正

出版者

情報処理学会

雑誌

研究報告アルゴリズム(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を解くには, 静的な解法を繰り返して解くよりも, 動的な解法の方が高速に解を求めることも示した.