教 授： 西関
隆夫
研究目的
１．効率の良いアルゴリズムの開発
２．グラフ理論（描画問題，分割問題など）や，回路計算量理論に関する研究
３．近似手法を用いた実用的アルゴリズムの開発
1
0
3
2
4
6
7
5
9
1
20
17
9
8
18
8
13
10
11
16
14
12
18
15
15
20
17
2
4
0
7
14
11
アルゴリズム
16
19
3
19 13 10
12
5
6
主な研究テーマ
1. グラフの描画アルゴリズム
グラフを“構造が理解しやすく”かつ“きれいに”描画する．
例： 指定された面積（VLSIチップのサイズ）と隣接関係（配線）を保ちながら，
各面を軸平行な多角形で描画する（VLSIのフロアプランニングに応用）
E6
D 11
E6
C 10
F8
A 11
D 11
A 11
F8
B 15
G 10
西関研究室
C
10
アルゴリズム
G 10
B 15
www.nishizeki.ecei.tohoku.ac.jp
2. グラフの分割アルゴリズム
グラフの点を供給点と需要点に分類し，それぞれに供給量と需要量を与える．
全ての需要点に供給するためには，どのようにグラフを分割すればよいか？
25
4
8
6
15
5
7
6
4
12
25
4
3
5
8
6
15
7
2
10
13
アルゴリズム
4
12
5
3
5
6
2
10
13
5 ：需要点（数字は需要量）
25 ：供給点（数字は供給量）
応用
(1)電力網の配電融通
(2)VLSIの電力供給
(3)ネットワークサーバーの割当
電力網
3. 脳のエネルギー消費を模倣する閾値回路
神経細胞の計算理論モデルである閾値素子を用いて，与えられたタスクを処理し，かつ
発火する素子の少ない（即ち，エネルギー効率の良い）回路の設計を行う． どのような
回路構造がエネルギー効率の面で有利に働くのか？
w2
or
w1
モデル化
1
≧t
or
0
wk
例）パリティ関数を計算する２つの回路の比較
① 高々4個の素子が発火する回路（消費エネルギー高）
0 or 1
0 or 1
0 or 1
0 or 1
x1
1
1
≧1
x2
≧2
x3
≧3
x4
西関研究室
x1
1
-1
≧1
1
1
≧4
1
② 高々2個の素子が発火する回路（消費エネルギー低）
x2
x3
-1
x4
1
1
≧1
≧2
≧3
-4
1 ≧4
-4
1
-4 1
1
≧1
www.nishizeki.ecei.tohoku.ac.jp