Information for

Prabhakar Ragde

Professor, and Director of Undergraduate Studies

Prabhakar RagdeResearch interests

Professor Ragde's work addresses problems for which there is evidence (such as NP-completeness) of intractability in sequential or parallel computation environments, but which may admit efficient solutions for special cases. Problems defined on linear structures such as paths and branching structures such as trees often permit the application of classic algorithm design techniques such as greedy algorithms or dynamic programming. However, these structures may be too narrowly defined.

For example, adding a single edge to a tree creates a cycle and may render incorrect an algorithm that depends on the tree being partitioned by removal of a vertex. Graphs of bounded pathwidth and treewidth are natural and more robust generalizations of paths and trees. They subsume other well-studied classes, such as series-parallel and outer planar graphs, and can be effective in modeling progress or evolution over time. They also arise in some surprising contexts -- for example, as variable-interference graphs used in register allocation for compiled versions of commonly-used programming languages. Professor Ragde's approach is to extend algorithmic techniques to solve problems defined on these types of graphs, while simultaneously looking for limitations (completeness results) on the reach of these extensions.

There are interesting connections between graphs of bounded treewidth and pathwidth and the emerging field of fixed-parameter tractability. Many problems have a natural parameter associated with them and turn out to be tractable if that parameter is bounded. For example, finding a set of k vertices that touch all edges of a graph of n vertices or proving that no such set exists is NP-hard. In contrast, the problem can be solved in time polynomial in n if k is fixed. Other problems appear to be difficult even when their parameters are bounded. The graphs described above have natural parameters (treewidth or pathwidth) but the full range of fixed-parameter techniques have not yet been explored in this context.

Professor Ragde is also interested in the theory and practice of functional programming and its relationship to persistent data structures and concurrent algorithms.

Degrees and awards

BMath (Waterloo), PhD (California, Berkeley)

Industrial and sabbatical experience

After finishing his PhD, Professor Ragde held an NSERC Postdoctoral Fellowship at the University of Toronto from 1986 to 1988. In 1997-98, he was a Visiting Associate Professor at Simon Fraser University in Burnaby, British Columbia.

Representative publications

P. Ragde. Simple balanced binary search trees. Electronic Proceedings in Theoretical Computer Science, to appear, 2014.

P. Ragde. Mathematics is imprecise. Electronic Proceedings in Theoretical Computer Science, 106: 40-49, 2012.

M. R. Fellows, C. Knauer, N. Nishimura, P. Ragde, F. Rosamond, U. Stege, D. M. Thilikos, and S. Whitesides. Faster fixed-parameter tractable algorithms for matching and packing problems. Algorithmica, 52(2): 167-176, 2008.

V. Dujmovic, M. Fellows, M. Hallett, M. Kitching, G. Liotta, C. McCartin, N. Nishimura, P. Ragde, F. Rosemand, M. Suderman, S. Whitesides, and D. R. Wood. On the parameterized complexity of layered graph drawing. Algorithmica, 52(2):267-292, 2008.

University of Waterloo
Contact information: