第330回研究講演会開催報告

日時:　2007年3月16日（金）16:00−17:00
会場：東北大学工学部電気情報系2号館　403号室
講師：
Professor Mohammad Kaykobad
Bangladesh University of Engineering and Technology

演題:
Majority Spanning Trees and　Their Applications to Scheduling and Ranking
Problems

概要:
   The main contribution in this research is the discovery of a new
class of spanning trees, termed as majority spanning trees, in directed
graphs with non-negative weights on edges, and its applications to optimal
scheduling of a periodic transportation system and ranking players of a
round robin tournament.  The scheduling problem under consideration
minimizes total waiting time of all passengers in the system, and has been
shown to be NP-Hard. The optimal solution has been shown to correspond to a
majority spanning tree in the corresponding digraph. Interestingly, the
optimal solution to the  problem of ranking players in a round-robin
tournament by criterion of minimizing number of  upsets also corresponds to
a majority spanning tree in the tournament digraph. We have investigated
existence of other relevant structures in digraphs, and indicated  possible
applications of these structures for finding  solutions to both the
problems.

参加者：35名
報告
　多数決全域木という新しい木の定義を与えるとともに、スケジュリング問題やラン
キング問題への応用が述べられた。参加者から多くの質問が寄せられ、活発な討論が
行われた。

報告者：西関隆夫（東北大）