Professor Hisao Tamaki, Department of Computer Science, Meiji University, Japan - September 5 2003
posted: Wednesday, September 3 2003
COMPUTING SCIENCE SEMINAR
Professor Hisao Tamaki
Department of Computer Science
Meiji University, Japan
Host: Dr. Qianping Gu
Friday, September 5th @ 11:30am, ASB 9705
A linear time heuristic for the branch-decomposition of planar graphs
Abstract:
Branch decomposition is one of the graph decomposition notions introduced by Robertson and Seymour in their graph minor project. The quality of a branch decomposition is measured by its "width" and many combinatorial problems on a graph can be solved in time linear in the size of the graph and exponential in its width (i.e., the width of its optimal decomposition). It is NP-hard to decide the width of a given general graph. For planar graphs, there is an O(n^2) time algorithm to decide whether a graph has a decomposition of given width, but the best-known algorithm for constructing the optimal decomposition takes O(n^4) time. In this talk, we present a linear time heuristic for constructing a branch decomposition of planar graphs, which performs extremely well on some test instances used by previous researchers.
Short biography of the speaker:
Dr. Hisao Tamaki got his PhD from Toronto University. He is currently a professor at Department of Computer Science, Meiji University, Japan. His research interests include algorithms, combinatorial optimization, computational geometry, and interconnection networks.
|
