Majority Spanning Trees, Cotrees and Their Applications

M Kaykobad (Bangladesh University of Engineering and Technology)

MSI Computational Mathematics Seminar Series

DATE: 2008-05-19
TIME: 11:00:00 - 12:00:00
LOCATION: John Dedman G35
CONTACT: JavaScript must be enabled to display this email address.

ABSTRACT:
We have defined a new class of spanning trees, called majority spanning trees and cotrees, called majority cotrees, in directed graphs. We have shown existence of these structures in any digraph with non-negative weights on their edges. We have further shown their simultaneous existence, that is, there exists a majority spanning tree T such that G-T is a majority cotree. The structure of majority spanning trees arose in conenction with the scheduling problem of periodic transportation system by criterion of minimizing weighted connection time. The structure was used to devise an algorithm for ranking players of a round robin tournament by criterion of minimizing number of upsets or violations. Settling multiple debts by minimizing number of transactions or transaction costs also results in such a spanning tree.
BIO:
http://www.buet.ac.bd/cse/faculty/facdetail.php?id=kaykobad