TALK: Majority Spanning Trees, Cotrees and Their Applications


Bangladesh University of Engineering & Technology


Sumaiya Nazeen
Abstract: We show that in any digraph on a connected underlying graph with non-negative weights on its edges, there is a Majority Spanning Tree for which sum of weights of edges of a fundamental cutset running along each edge of the spanning tree determining the cutset is not less than sum of those running in opposite direction. Similarly, existence of Majority Cotrees and simultaneous existence of majority spanning trees and majority cotrees have been established. We have shown how these structures are important in scheduling transports by minimizing sum of weighted connection times, ranking round robin tournaments by minimizing number of upsets, in settling multiple debts and in construction of transport networks with unbalanced road capacity.

Speaker Bio: Dr. Kaykobad is currently a Professor at CSE Department, Bangladesh University of Engineering and Technology (BUET), the leading engineering university of Bangladesh. He has also served as a Visiting Professor at the Chinese University of Hong Kong, Kyung Hee University, Korea, Australian National University (ANU) and Monash University, Australia, and Amritapuri University, India for different lengths of time. He has an MSc in Engineering from OMEI, now Odessa State Maritime University, Ukraine and an M.Eng. from AIT, Thailand. He did his Ph.D at the Flinders University of South Australia. Dr Kaykobad is a Fellow of Bangladesh Academy of Sciences (BAS), and has served as an Associate Secretary of its Executive Council. He was the Organizing Chair of the inaugural International Conference on Computer and Information Technology (ICCIT). He is also the Chair of the Steering Committee for International Workshop on Algorithms and Computing (WALCOM), proceedings of which are published as Lecture Notes in Computer Science by Springer.

Dr. Kaykobad has published at many prestigious venues including Physical Review, International Journals of Computer Mathematics, Computers & Operations Research, Computers & Mathematics with Applications, Linear Algebra & Its Applications, Information Processing Letters, Information Processing and Management, Applied Mathematics E-Notes, Journal of Computing and Information Technology, Electronic Notes in Discrete Mathematics, Journal of International Olympiad in Informatics and Computers & Graphics. He authored, coauthored or edited 13 books. He is a guest co-editor of the proceedings of International Conference on Computer and Information Technology (ICCIT) published by Academy Publisher.

He has been one of the pioneers in introducing Mathematics Olympiad, Informatics Olympiad and Science Olympiad in Bangladesh. He has been leading Bangladesh IOI team since 2008 from which Bangladesh received a silver medal in 2008 from Bulgaria, 2 bronze medals in 2012 from Italy and one from Australia. He has served as the director of ICPC Asia Region Dhaka site during 2001-2003. He was also the Chief Judge of IIT Kanpur Asia Region Site of ICPC in 2010, 2011 and 2013. He was adjudged as the outstanding coach of ICPC in 2002 at Honolulu, Hawaii. He was the only Senior Coach award recipient at the World Finals of ICPC held at St. Petersburg, Russia in 2013. He was also awarded a gold medal by Bangladesh Physics Olympiad.