ζ330ρ€uοJΓΔΰ
ϊ:@2007N316ϊiΰj16:00-17:00
οκFkεwHwdCξρn2Ω@403Ί
utF
Professor Mohammad Kaykobad
Bangladesh University of Engineering and Technology
θ:
Majority Spanning Trees and@Their Applications to Scheduling and Ranking
Problems
Tv:
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@ό@Ε