Associate Professor
Joined School 1991
BS (Yale),
MSc (Toronto),
PhD (Toronto)
| nishi@uwaterloo.ca | |
| Web | http://cs.uwaterloo.ca/~nishi |
| Voice | 519-888-4567 x34835 |
| Fax | 519-885-1208 |
|
| Naomi Nishimura
Associate Professor Joined School 1991 BS (Yale),
|
Graph algorithms are used to solve fundamental problems in a diverse set of areas, in computer science as well as in other disciplines. Since a graph is specified as a set of nodes and a set of edges (where each edge can be seen as a link between a pair of nodes), a graph can be used to represent the relations (edges) among data items (nodes). For example, graphs can be used to represent relationships among species of animals, words in a document, features of an image, data in a database or links between processors in a parallel or distributed computing environment.
Unfortunately, many problems can be solved only for restricted classes of graphs. The solutions depend on structural properties absent from more complicated graphs; for example, computations on trees exploit the fact that the removal of a single node will separate the tree into disjoint subtrees. Professor Nishimura's research objectives include identifying and representing structural properties in graph classes, of interest in their own right, in addition to extending the boundaries around graph classes for which efficient algorithms are known.
Examples of exploiting graph structure include results on graphs of bounded path width and tree width (graphs characterized by path-like and tree-like representations, respectively), phylogenetic trees (structures used in computational biology), and networks (representations of the flow of information or other resources). An example of a less obvious application of graphs is found in work on satisfiability. The types of results obtained include determining structural properties and investigating the interplay among various representations.
Parameterized and exact computation allow the development of efficient algorithms for various problems which, when considered in full generality, are considered to be intractable. The aim of the parameterized approach is to identify the source of complexity as one or more parameters of the problem, obtaining algorithms that are polynomial in the size of the input but possibly exponential in the parameters. In situations in which the parameters are guaranteed to be small in comparison to the size of the input, these techniques yield polynomial-time algorithms. Professor Nishimura's work in this area relates to her interest in graph structure, and also extends to problems in other domains.
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. M. Thilikos. Fast fixed-parameter tractable algorithms for nontrivial generalizations of vertex cover. Discrete Applied Mathematics, 152(1-3): 229-245, 2005.
E. D. Demaine, M. Hajiaghayi, N. Nishimura, P. Ragde, and D. M. Thilikos. Approximation algorithms for classes of graphs excluding single-crossing graphs as minors. Journal of Computer and System Sciences, 69: 166-195, 2004.
David R. Cheriton School of Computer Science
University of Waterloo
Waterloo, Ontario, Canada N2L 3G1
Tel: 519-888-4567 x33293
Fax: 519-885-1208
Contact | Feedback: cs-webmaster@cs.uwaterloo.ca | David R. Cheriton School of Computer Science | Faculty of Mathematics
Last modified: Monday, 20-Dec-2010 14:30:02 EST
