平成１０年度第３回KSMAP

日時：７月１４日（火） １５：００〜１７：００

場所：京都大学 工学部８号館３Ｆ 共同５講義室

       京都大学へのアクセス

講演題目と講演者：

● 石井利昌 (京都大学), 論文紹介: 
   M. Thorup, "Undirected Single Source Shortest Paths in Linear Time,"
   Proc. FOCS (1997) 12-21.

講演要旨：
  本発表では、1997年、M. Thorupによって提案された、整数枝重み無向グラフに
  おける、単一始点最短路問題(SSSP)を解く線形時間アルゴリズムについての論文
  紹介を行います。

  SSSPを解くためのアルゴリズムとしては、Dijkstraのアルゴリズムがよく知られ
  ています。これまで、Dijkstraのアルゴリズムの高速化について、多くの研究が
  なされてきましたが、ソート問題に相当するボトルネックのため、線形時間を達
  成することはできませんでした。M. Thorupは、このボトルネックを回避するため
  の新しい概念を導入し、最小木問題の線形時間アルゴリズムや過去に研究された
  データ構造などを利用して、線形時間を達成しました。