NC State University

Department of Computer Science Colloqua 1999-2000

Date: Thursday, February 10, 2000
Time: 3:30 PM (refreshments), 4:00 PM (talk)
Place: Withers 402A, NCSU Historical Campus (click for courtesy parking request)

Speaker: Matthias Stallmann, Computer Science, NCSU

Heuristics and Experimental Design for Bigraph Crossing Number Minimization

Abstract: The bigraph crossing problem, embedding the two node sets of a bipartite graph G = (V0,V1,E) along two parallel lines so that edge
crossings are minimized, has application to circuit layout and graph drawing. We consider the case where both V0 and V1 can be permuted arbitrarily (most previous research has assumed that the order of V0 is fixed - the problem is NP-hard either way).

The results of carefully-designed experiments evaluating relative performance of several well-known heuristics and two new heuristics will be presented. Emphasis is on the interplay between algorithm design, experimental methodology, and evaluation of experimental results, and how advances in any one of these lead to new insights for the others.

Early publications, datasets, and results of experiments related to this talk are available at:

Short Bio: Matthias Stallmann was born in Giessen, Germany, and emigrated with his family to the US in 1961. He received a B.A. degree in Mathematics and Computer Science from Yale University in 1974, an M.S. in Computer Science from Yale in 1978, and a Ph.D. in Computer Science from the University of Colorado at Boulder in 1982 (thesis advisor: Prof. Hal Gabow). From January, 1983 to June, 1984 he was Visiting Assistant Professor in the Department of Mathematics and Computer Science at the University of Denver. Since the fall of 1984 he has been on the Computer Science faculty at North Carolina State University.

Dr. Stallmann's primary research interests are in combinational optimization, specifically graph and network algorithms, with emphasis on dealing with intractability (NP-completeness), either by looking for polynomial special cases or developing good heuristics. Current projects include (a) minimizing edge crossings in embeddings of graphs (b) layout and routing problems related to VLSI design, (c) experimental analysis of algorithms and heuristics, and (d) tools for implementation and visualization of graph algorithms.

Host: Franc Brglez, Computer Science, NCSU

Colloquia Home Page.