Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Tuesday, October 25, 2005, 12:15 pm
Duration: This information is not available in the database
Location: This information is not available in the database
Speaker: Ryuhei Uehara (Japan Advanced Institute of Science and Technology)
The longest path problem is to find a longest path in a given graph. While the graph classes in which the Hamiltonian path problem can be solved efficiently are widely investigated, few graph classes are known to be solved efficiently for the longest path problem. For a tree, a simple linear time algorithm for the longest path problem is known. We first generalize the algorithm, and show that the longest path problem can be solved efficiently for tree-like graph classes. We next propose some polynomial time algorithms for the longest path problems on some graph classes which have natural interval representations.
Automatic MiSe System Software Version 1.4803M | admin login