Majority Spanning Trees, Cotrees and Their Applications

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.
Dr. Mohammad Kaykobad is a Professor at the CSE Department, BUET since 1997, and served as its chair during 1996-1999. He received M.S. (Hons.) in Engineering from OMEI, now Odessa State Maritime University, in 1979. In 1982, he received an M.Eng. Degree from AIT, Thailand, and Ph.D from the Flinders University of South Australia in 1988. Dr. Kaykobad is a Fellow of Bangladesh Academy of Sciences(BAS), and was an Associate Secretary of its Executive Council. He has published many research papers in top venues and authored, coauthored or edited 13 books. Many of these books are for inspiring young students develop either programming or mathematics skills.

Dr. Kaykobad was the Organizing Chair of the first ever international computer conference ICCIT held in the soil of Bangladesh. He is also the Chair of the Steering Committee for Workshop on Algorithms (WALCOM). He has guided more than a dozen undergraduate students whose research works were published in journals of international repute. Dr. Kaykobad participated as a Resource Person in Workshop on Science Communication sponsored by COSTED and UNESCO held at Goa during 18-23 November, 2001. He is a frequent column writer in National Dailies authoring over 300 articles, most of which are related to education of the country. He has been one of the pioneers in introducing Mathematics Olympiad, Olympiad in Informatics 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 was director of ICPC Asia Region Dhaka site during 2001-2003. He was 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.

Dr. Kaykobad was a Visiting Professor at the CSE Department, the Chinese University of Hong Kong, at Kyung Hee University, Korea, ANU and Monash University, Australia and Amritapuri University, India. In 2005, the President of Bangladesh presented him with a Gold Medal awarded by Bangladesh Computer Society for his contribution to computer programming culture in the country. In 2006, He won BAS Gold Medal for physical sciences in the senior group which was awarded by the Prime Minister of Bangladesh. Dr. Kaykobad is a member of the Executive Council of Bangla Academy.

Dr. Kaykobad has been playing active role in the computerization of both public and private enterprises. He worked as a Director of Dhaka and Chittagong Stock Exchanges for many years. Currently, he is an independent director of Dhaka Stock Exchange. Dr. Kaykobad is a member of Academic Council and Syndicate of several universities.