理論情報科学領域【上原研究室】
■ 研究概要
計算機で解きたい問題の中には「どうしようもなく難しい」ということが理論的に示されてしまう場合があります。難しいからといってあきらめられればよいのですが，そうも言っていられません。こうした「計算が困難な問題」に対して，何らかの妥当性をもつ解を，現実的な時間で与えることが本研究室のメインテーマです。
■ もう少し詳しい概要
多くの問題は，点と線だけを使ったグラフと呼ばれる構造で表現することができます。こうしたモデル化や定式化を行い，その上で問題をあつかいます。つまりどちらかといえば理論的，基礎的な研究をしています。上で書いている妥当性として，具体的には次の３つのアプローチで研究をすすめています。
入力の条件を利用する
問題をモデル化したときに，問題に固有の性質を使って，入力に制限を与えることができる場合があります。例えば地図データなら，平面上に描くことができるし，寄り道をして距離が短くなることはありません。こうした固有の性質を利用すると，入力グラフに制限を加えることができます。制限された入力グラフに対して，グラフ理論の結果を使うことで，困難な問題が現実的な計算時間でなんとかなる場合があります。
近似解を求める
最適であることが保証されている厳密解でなくても，実用上は十分な場合があります。例えば最適解を求めるには１ヶ月かかるけれども，最適解の110％に収まることが保証されている解が10分で求まるなら，そちらを選ぶ人は多いのではないでしょうか。最適解を求める問題は計算困難でも，近似率が保証された近似解を求める問題はなんとかなる場合があります。特に「最適解が求められなくても近似率が理論的に保証できる」ことがあるのが面白いところです。
確率的な方法を使う
これは乱択アルゴリズムとも呼ばれています。具体的には乱数を利用した計算です。もっと簡単に言えば，コインを投げ，その結果に応じて次に行う処理を決める計算方法です。例えばx
回コインを投げて「連続して表が出た長さ」の最大値を求めると，それだけで関数log x を高い確率で「計算」することができます。このように，乱数を使わない場合よりも，ずっと単純な方法で問題が解決できたり，ずっと高速に解を計算できることがあります。
こうした３つのアプローチはそれぞれ独立なものではなく，組み合わせて使うとより効果的な場合もあります。
■ 国内活動
電子情報通信学会の和文論文誌の編集委員をしています。また同学会の英文論文誌の特集号の編集委員もときどきしています。
■ 国際活動
主にグラフアルゴリズム関連の国際会議に参加，発表しています。
■代表的な著書・論文
- 上原隆平：「グラフクラスとアルゴリズム」，電子情報通信学会誌（解説論文），Vol.88, No.2, pp.118-122,
2005.
- R. Uehara, S. Toda, and T. Nagoya : Graph Isomorphism Completeness
for Chordal Bipartite and Strongly Chordal Graphs, Discrete
Applied Mathematics, 145（3）, pp.479-482, 2004.
- R. Uehara, K. Tsuchida, and I. Wegener : Identification of
Partial Disjunction, Parity, and Threshold Functions, Theoretical
Computer Science, 230, pp.131-147, 1999
