EECS Seminar: Majority Spanning Trees, Cotrees and their Applications

Harut Barsamian Colloquia Room, EH 2430
Mohammad Kaykobad, Ph.D.

Department of Computer Science and Engineering
Bangladesh University of Engineering & Technology

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 the sum of weights of edges of a fundamental cutset running along each edge of the spanning tree determining the cutset is not less than the 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 the 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.

Bio: Kaykobad is a fellow of the Bangladesh Academy of Sciences (BAS), and was an associate secretary of its Executive Council. Kaykobad has been a professor of computer science and engineering at the Bangladesh University of Engineering & Technology since 1997, dean of the faculty of electrical and electronic engineering during 2015- 2017, and CSE head during 1996-1999. He has published many papers in 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 also has authored, coauthored or edited 13 books. 

Kaykobad was the organizing chair of the first ever international computer conference ICCIT held in Bangladesh. He also is chair of the Steering Committee for Workshop on Algorithms (WALCOM) proceedings of which are published as Lecture Notes in Computer Science by Springer. 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 the Bangladesh IOI team since 2008; Bangladesh received a silver medal in 2008 from Bulgaria, two bronze medals in 2012 from Italy and one from Australia. He was director of the ICPC Asia Region Dhaka site during 2001-2003. He was chief judge of the IIT Kanpur Asia Region Site of ICPC in 2010, 2011 and 2013. He was named as outstanding coach of ICPC in 2002 in Honolulu, Hawaii. He was the only Senior Coach award recipient at the World Finals of ICPC held in St. Petersburg, Russia in 2013. He also was awarded a gold medal by Bangladesh Physics Olympiad.

Kaykobad was a visiting professor in the CSE Department, Chinese University of Hong Kong, Kyung Hee University, Korea, ANU and Monash University, Australia, and Amritapuri University, India. In 2005 the president of the country presented him with a Gold Medal awarded by Bangladesh Computer Society for his contribution to computer programming culture. In 2006, he won the BAS Gold Medal for physical sciences in the senior group, which was awarded by the prime minister of the country. Kaykobad is a member of the Executive Council of Bangla Academy. He plays an active role in the computerization of both public and private enterprises. 

Upcoming Events