Department of Computer Science University of Colorado Boulder
 cu: home | engineering | mycuinfo | about | cu a-z | search cu | contact cu cs: about | calendar | directory | catalog | schedules | mobile | contact cs
 home | quick links | site map | who's where | cs a-z
home · events · thesis defenses · 2007-2008 ·

# Thesis Defense - Nie

7/18/2008
2:00pm-4:00pm
ECCR 1B06

Algorithms on Long Paths and Cycles in Graphs
Shuxin Nie
Computer Science PhD Candidate

Finding a longest path or cycle in a graph is a basic problem in graph theory. This problem is NP-hard since it has the Hamiltonian path or cycle problem as a special case. The thesis is working on finding good approximation algorithms in both directed and undirected graphs.

In graph theory, n is always used to denote the number of vertices in the graph. In directed graphs, the thesis includes an algorithm that can find a cycle of length at least log n / log log n in polynomial time, if one exists. Then it is generalized to an algorithm that can find a vw-path of length at least log n / log log n in polynomial time. These are the best known results so far and the hardness results show that there is no polynomial time algorithm can find a cycle of length >= log n under appropriate complexity assumption. The previously known technique of color coding can find cycles of length exactly k, for any k<= log n, in poly time. However finding a cycle of length >=k is a much harder problem, e.g. it might require finding a Hamiltonian cycle.

For undirected graphs, the thesis gives an algorithm that can find a cycle of superpolylogarithmic length in polynomial time. It not only simplifies a previous result of Gabow's algorithm but also improves his result.

In the thesis we also extend the algorithms from finding simple cycles to finding edge simple closed walks, which is a field no substantial results are proved before. The thesis includes a reduction from the latter problem to the cycle problem, showing that all algorithms on cycles can be used to find edge simple closed walks. The thesis also proved the same hardness results for both problems.

 Committee: Harold (Hal) Gabow, Professor (Chair) Richard Byrd, Professor Debra Goldberg, Assistant Professor Michael Main, Associate Professor San Skulrattanakulchai, Gustavus Adolphus College

 Department of Computer Science College of Engineering and Applied Science University of Colorado Boulder Boulder, CO 80309-0430 USA Questions/Comments? Send email to webmaster at cs.colorado.edu Engineering Center Office Tower ECOT 717 +1-303-492-7514 FAX +1-303-492-2844
 XHTML 1.0/CSS2 ©2012 Regents of the University of Colorado Privacy · Legal · Trademarks May 5, 2012 (13:40)

.