‘ζ330‰ρŒ€‹†u‰‰‰οŠJΓˆΔ“ΰ

“ϊŽž:@2007”N3ŒŽ16“ϊi‹ΰj16:00-17:00
‰οκF“Œ–k‘εŠwHŠw•”“d‹Cξ•ρŒn2†ŠΩ@403†ŽΊ
uŽtF
Professor Mohammad Kaykobad
Bangladesh University of Engineering and Technology

‰‰‘θ:
Majority Spanning Trees and@Their Applications to Scheduling and Ranking
Problems

ŠT—v:
   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.

–β‚’‡‚ν‚ΉζF@Žό@‹Ε