Andrzej Proskurowski: Research

Computer/Communication Network Topology

and

Complexity of Combinatorial Optimization Problems

Within the Network Research Group, Art Farley and myself have been investigating various graph theoretical models of communication in networks, from broadcasting through multicasting. These studies resulted in design of abstract communication protocols and structures robust with respect to site and link failures. Recently, we have approached the question of distilling the Internet topology through routing tables queries. The empirical data for this study is obtained from the Route Views project at the Advanced Network Topology Center at the University of Oregon.

Another area of my research concentrates on issues of complexity of combinatorial optimization problems. When restricted to graphs with bounded treewidth ("partial k-trees") many inherently difficult optimization problems are efficiently solvable. I have been working recently on developing efficient algorithms for problems on partial k-trees and on structural properties of those classes of graphs and their subclasses, as well as on finite recognition mechanisms for subclasses of those graphs.

My research has been supported by grants from the Office of Naval Research, the National Science Foundation, and the National Academy of Sciences. As a Fulbright scholar, I have lectured in Finland. Supported by national research foundations I have collaborated abroad with researchers in Australia, Canada, Czech Republic, Germany, France, Hong Kong, Mexico, The Netherlands, Norway, Poland, Spain and Sweden.

Here is the list of recent publications