Conference on Graph Classes, Optimization and Width Parameters hosted by CIS Department
Over thirty professors and graduate students from 19 institutions in North and South America and Europe attended a symposium called "Third Workshop on Graph Classes, Optimization and Width Parameters," or GROW '07, Oct. 18-20 on the University campus. The participants investigate graphs which model relationships between objects such as roads between cities, links between network routers and even human social relationships.
"To optimize the use of resources, one has to solve -- most often with the help of computers -- problems that frequently can be translated into properties of graphs," said Andrzej Proskurowski. "One of the most celebrated of such problems is the Hamiltonian path. Given a network of cities and roads, one must find the shortest route that visits all cities."
Algorithms, like those that determine the Hamiltonian routes are often caught in "combinatorial explosion," when the time required to compute the solution grows exponentially with the size of the problem. Researchers study restricted classes of graphs in hope of finding more efficient solution algorithms. Many problems become tractable, Proskurowski said, when values of certain "graph-width" parameters of the input graphs are bounded.
CIS faculty members have been on the cutting edge of such research for more than three decades. Because of that leadership, international scientists came to the UO in 1989 for the first of what has become a series of related gatherings. The first one focused on "efficient algorithms on partial k-trees," which refers to tree-width and separability restrictions on graph structure. Since 1989, the researchers have met in Barcelona in 2001 and in Prague in 2005. The workshops are funded through research foundations in host countries.
This year's workshop featured a keynote address by Norway native Jan Arne Telle. Telle, a professor at the University of Bergen who earned his doctorate in computer science from the University of Oregon in 1994. The conference was organized by Proskurowski, Professor Pinar Heggernes of the University of Bergen who is spending her sabbatical leave at UO, and Professor Jan Kratochvil of Charles University in Prague, a former Fulbright fellow at UO. The organizers plan to publish the results in a special volume of the journal Discrete Applied Mathematics.