Majority Spanning Trees, Cotrees and their Applications
Speaker: Prof M Kaykobad, Department of Computer Science and Engineering,Bangladesh University of Engineering
When: 2008-05-26 12:00:00
Venue: N16_0.10, Nathan Campus, Griffith University
Host: Rebecca Bailey
Abstract:We define a new class of spanning trees, called majority spanning trees, and
cotrees, called majority cotrees, in directed graphs. We prove their
existence in any digraph with non-negative weights on edges. We prove that
there exists a majority spanning tree T of G such that G-T is a majority
cotree. We show its applications in scheduling period transportation system
by criterion of minimizing waiting times in connections, and in settling
multiple debts. We also devise an algorithm for ranking players of a round
robin tournament using the same structure in tournament digraph.
Biography:Educational Background
Dr Kaykobad received M.S.(Hons.) in Engineering from OMEI, now Odessa
Maritime University, in 1979. In 1982 he received an M.Eng. Degree from AIT,
Thailand. He completed his Ph.D. in 1986 from the Flinders University of
South Australia.
Institution
Dr Kaykobad worked at the Institute of Computer Science, AERE before joining
CSE Department, BUET (in Bangladesh) in 1991. He has been a Professor there
since 1997 and head during 1996-1999.
Research and Publication Area
He has published research papers in Physical Review, International Journals
of Computer Mathematics, Computers & Operations Research, Computers &
Mathematics with Applications, Linear Algebra & its Applications, IPL,
Information Processing and Management and Computers & Graphics. Dr. Kaykobad
has published about 40 papers in various international journals. He has
authored, coauthored or edited 13 books.
Achievements
Dr Kaykobad led/was associated with BUET teams to the World Finals of ACM
ICPC for ten years in a row. The best result coming in year 2000 when BUET
teams occupied 11th position among 60 teams selected from 1968 teams of 1041
universities of 69 countries on 6 continents. He was recognized as the
Outstanding Coach in the 26th World Finals of ACM ICPC in 2002.
Dr Kaykobad was a Visiting Professor at the CSE Department, the Chinese
University of Hong Kong during 2000 and 2001. He also held the prestigious
IT Scholar Visiting Professorship award at Kyung Hee University, Korea. He
was recognized as the best IT teacher in 2000 by Bangladesh Computer
Samitee. In year 2005 the president of the country presented him with a Gold
Medal awarded Bangladesh Computer Society for his contribution to computer
programming culture in the country. In year 2006 the Prime Minister of the
country presented him with the Gold Medal for physical sciences in the
senior group awarded by the Bangladesh Academy of Sciences.
He is a frequent column writer in National Dailies authoring over 200
articles. He has been one of the pioneers in introducing Mathematics
Olympiad and Olympiad in Informatics in Bangladesh. He was the observer and
leader of Bangladesh team to IOI respectively in 2004 and 2005.
Dr Kaykobad has widely traveled across Europe, Asia, Australia and North
America and visited many prestigious institutions all over the world like
MIT, Harvard, Stanford, Berkeley and Labs like IBM TJ Watson and he is a
strong believer that a developing nation can survive and flourish in the
21st century only through ensuring world class education.
Type: IIIS seminar
Contact:Rebecca Bailey, seminar host (r.bailey@griffith.edu.au)
or Guido Governatori (ITEE seminar co-ordinator)
(guido@itee.uq.edu.au)