Nishizeki Laboratory

Algorithm Theory / Department of System Information Sciences (Graduate School of Information Sciences)
Algorithm Theory / Department of Information Engineering

[JAPANESE VERSION] /[ENGLISH VERSION]

[STAFF LIST][Nishizeki Laboratory Homepage]


Fig.1: VLSI layout design	Fig.2: planar graph

　Main interests of the laboratory are developing unified methodology todesign and analyze efficient algorithms, and investigating datastructures for such algorithms. In particular we focus on discretealgorithms for solving problems modeled by graphs or networks.
　A graph, that is an ordered pair consisting of a set of vertices and aset of edges, each joining a pair of vertices, has immediateapplications to many practical problems such as VLSI layoutdesign. Our algorithm for finding shortest non-crossing paths in planegraphs can be well applied to VLSI routing. Such efficient algorithmsare in a great need. We extend our research to algorithms formulticommodity network flows, graph drawing, and graph partitioningproblems. In addition, we are engaged in design and analysis ofalgorithms for various types such as parallel, distributed,approximation.