Professor
Joined School 1988
BMath (Waterloo),
PhD (UC Berkeley)
| plragde@uwaterloo.ca | |
| Web | http://www.cs.uwaterloo.ca/~plragde |
| Voice | 519-888-4567 x34660 |
| Fax | 519-885-1208 |
|
| Prabhakar L Ragde
Professor Joined School 1988 BMath (Waterloo),
|
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.
Recent results include fixed-parameter-tractable (FPT) algorithms for covering, matching, and packing problems on graphs, for finding solutions and for counting the number of solutions to a given instance, as well as both FPT algorithms and complexity (hardness) results for problems related to polynomially-solvable instances of the Boolean satisfiability problem.
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.
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. To appear in Algorithmica.
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.
N. Nishimura, P. Ragde, and S. Szeider. Solving #SAT using vertex covers. Acta Informatica, 44(7-8):509-523, 2007.
N. Nishimura, P. Ragde, and D. Thilikos. Parameterized counting algorithms for general graph covering problems. Proceedings of 9th Workshop on Algorithms and Data Structures (WADS), 2005.
Please contact the server administrator, webmaster@cs.uwaterloo.ca and inform them of the time the error occurred, and anything you might have done that may have caused the error.
More information about this error may be available in the server error log.
