skip to main content
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 · events · thesis defenses · 2007-2008 · 

Thesis Defense - Nie


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

See also:
Department of Computer Science
College of Engineering and Applied Science
University of Colorado Boulder
Boulder, CO 80309-0430 USA
Send email to

Engineering Center Office Tower
ECOT 717
FAX +1-303-492-2844
XHTML 1.0/CSS2 ©2012 Regents of the University of Colorado
Privacy · Legal · Trademarks
May 5, 2012 (13:40)