Parallel Computation of Constrained Spanning Trees
--------------------------------------------------

Speaker: Prof. Narsingh Deo, University of central Florida

 
Abstract: 
--------

Computing spanning trees with specific properties and constraints lies
at the heart of many real-life network optimization problems.  Most of
these problems turn out to be NP-complete and are required to be
solved on large graphs.  Therefore, good heuristics and parallel
platforms are needed for any meaningful solutions.

In this talk we will first outline some of these problems, arising
from a wide variety of applications.  Then we will develop two general
solution-strategies and apply them to the Degree-Constrained MST
problem and the Minimum-Length Fundamental-Cycle Set
problem. Promising computational results (on problems of upto 5000
nodes and 12 million edges) on a massively parallel
machine--MasPar--will be discussed.

Professor Narsingh Deo holds the Charles E. Millican Eminent Scholar's
chair in Computer Science at University of Central Florida, Orlando.
He is also the Director of UCF's Center for Parallel Computation.
Prior to accepting the current endowed chair in 1986, he was Professor
(and the chairman for a three-year term) of Computer Science at
Washington State University, Pullman for nine years.  Narsingh Deo
received his Ph.D.  (EE) from Northwestern University.  A Fellow of
IEEE and a Fellow of the ACM, Dr. Deo has authored four textbooks and
some 150 papers in graph theory, discrete optimization, combinatorial
algorithms, and parallel computation.