Title:	Observations on logical ways to avoid complexity for graph problems
Date:	November 30, 2006 (Thursday)
Time:	11:30 a.m. - 12:30 p.m.
Venue:	Room 121, 1/F, Ho Sin-hang Engineering Building, The Chinese University of Hong Kong, Shatin, N.T.
Speaker:	Prof. Detlef Seese University of Karlsruhe Germany

ABSTRACT:

Many algorithmic problems interesting from a theoretical or practical point of view are NP-hard and permit at least till now no efficient algorithmic solution. Usually one tries to get solutions in polynomial time by restricting the structure of the input objects. While on one side almost all problems for arbitrary graphs are NP-hard they become usually solvable in polynomial or even linear time if the input structures are restricted to structures of bounded width (band-width, tree-width, branch-width, path-width, ... ). The talk gives a survey on combinatorial and logical results which try to explain some of these phenomena and discusses some open problems in this area.

BIOGRAPHY:

Detlef Seese studied Mathematics at the Humboldt-University in Berlin, where he got 1976 his PhD. (Dr. rer. nat.) From 1975 - 1991 he worked at the Academy of Sciences in Berlin, where he received the degree Dr. sc. nat. and was appointed 1985 as Head of the Division of Discrete Mathematics, Algebra, Logic and Theoretical Computer Science at the Karl-Weierstrass-Institute for Mathematics. 1990 - 1992 he had a replacement Professorship for Applied Computer Science at the University Duisburg. 1992 he became Professor for Applied Computer Science at the University of Karlsruhe (TH). Since 1999 he is Head of the group Complexity Management and Member of the Board of Directors of the Institute AIFB (www.aifb.uni-karlsruhe.de). He is member of the Board of Directors of the Institute for Applications of Informatics of the University Karlsruhe (since 2000) and Founding Member of the Center for Risk Management and Disaster Reduction Technology (www.cedim.de, since 2002). He is author of more than 100 scientific papers and 3 books in the areas Mathematical Logic, Theoretical Computer Science, Graph Theory, Computational Finance, Market Engineering, Computer Based Training and Software Development. He was Guest Professor at the University of Toronto and worked for more than 3 years at universities abroad (Budapest, Bordeaux, Eindhoven, Eugene, Florence, Lund, Milan, Moscow (Idaho), Sydney, Newcastle (Australia), Novosibirsk, Pisa, Prague, Pullman, Stockholm, Toronto, Umea, Utrecht, Warsaw, Wellington, Wroclaw). Since 1999 he is Member of the editorial board of the Journal of Universal Computer Science (J. UCS).

Enquiries: Miss Temmy So at tel 2609 8444

For more information, please refer to http://www.cse.cuhk.edu.hk/seminar