hal@UTDALLAS.EDU (Hal Sudborough) (09/25/90)
********************* !! ANNOUNCEMENT !! ****************************
( 2nd Meeting of )
Workshop on Algorithmic Research in the Midsouthwest ( WARM )
Friday, October 12
Final Schedule
********************************************************************************
**
LOCATION: Performance Hall ( Jonsson 2.604 )
The University of Texas at Dallas
Richardson, Texas 75083-0688
CONTACT: Hal Sudborough, Head
Computer Science Program
(214)-690-2184
Please call or send e-mail if you'd like information
on a special rate at a local hotel, routing information
from the airport, etc.
********************************************************************************
**
[11:00 - 11:45 a.m.]
SYMMETRY IN INTERCONNECTION NETWORKS
S.Lakshmivarahan
Parallel Processing Institute
School of Electrical Engineering and Computer Science
University of Oklahoma, Norman, Oklahoma
Abstract: This talk will review various notions
of symmetry in graphs including vertex symmetry,
edge symmetry, distance transitivity, distance
regularity, etc. Analysis of symmetry of interconnection
networks based on Star graphs and other graphs
relating to the symmetric permutation group, even
graphs and orthogonal graphs will be presented.
********************************************************************************
**
[11:45-12:30 noon]
LOWER BOUNDS FOR PARALLEL COMPUTATION ON LINKED STRUCTURES
Vijaya Ramachandran
Department of Computer Sciences
The University of Texas at Austin
(joint work with Faith Fich.)
Abstract: We present the following results on parallel computation
on linked structures:
We give a tight relationship between the time required on a
decision tree and the time required on a CREW PRAM
to compute any function of a collection of circular doubly linked
lists. We show that this relationship does not hold for
singly linked lists.
We derive a tight lower bound of OMEGA(log^*n) time on
a decision tree for the problem of coloring an n-node
doubly linked circular linked list with a constant number of
colors. By applying the first result, we then derive a tight
lower bound of OMEGA(log log^*n) time on a CREW PRAM
for the problem of coloring a collection of circular doubly linked
lists on n nodes.
********************************************************************************
**
[12:30 noon - 2:00 p.m] --------- lunch ---------------
********************************************************************************
**
[2:00 - 2:45 p.m.]
THE COMPUTATIONAL COMPLEXITY OF OPTIMAL SORTING NETWORK VERIFICATION
by Ian Parberry
Center for Research in Parallel and Distributed Computing
Department of Computer Sciences
University of North Texas
Denton, Texas
A sorting network is a combinational circuit for sorting,
constructed from comparison-swap units. The depth of such a
circuit is a measure of its running time. It is reasonable to
hypothesize that only the fastest (that is, the shallowest) sorting
networks are likely to be fabricated. It is shown that the
verification of shallow sorting networks is computationally
intractable. More precisely, it is shown that the problem of
verifying sorting networks with depth very close to the optimum
is Co-NP complete, and further that any deterministic or randomized
algorithm that has access only to the inputs and outputs of the
sorting network must take exponential time to verify it.
Despite the computational intractability of the shallow sorting
network verification problem, we describe a construction and
verification algorithm which was recently executed on a supercomputer
to demonstrate that there is no 9-input sorting network
of depth 6, a question which had remained open for over 15 years.
********************************************************************************
**
[2:45 -3:30 p.m.]
A COMBINATORIAL VIEW OF VISIBILITY GRAPHS
by James M. Abello
Distributed Laboratory for Algorithms Design
Department of Computer Science
Texas A&M University
College Station, Texas
( joint work with Omer Egecioglu and Krishna Kumar )
We address the polynomial time recognition problem
for vertex graphs of staircase-like polygons.
These graphs are given a coordinate free combinatorial
representation in terms of linear orders induced on
Ferrer's diagrams of shape (n-1, n-2, .. , 1). This opens
up a surprising connection between these graphs and maximal
chains in the Permutohedron. It turns out that various
properties of the underlying graphs can be studied in terms
of restricted types of Coxeter transformations. As a byproduct
a generalization of chordal graphs is obtained settling
several open questions posed by O'Rourke.
********************************************************************************
**
[3:30 -4:00 p.m.] ----------Break-------------
********************************************************************************
**
[4:00 - 4:45 p.m.]
PARALLEL ALGORITHMS FOR COMBINATORIAL SEARCH PROBLEMS
by Yanjun Zhang
Department of Computer Science
Southern Methodist University
Dallas, Texas
Abstract: In this talk we present parallel algorithms for
backtrack search, branch-and-bound computation and game-tree search.
Our model of parallel computation is a network of processors
communicating via messages. Our primary interest in a parallel
algorithm is its speed-up over the sequential ones. Our goal is to
design parallel algorithms that achieve a speed-up proportional
to the number of processors used.
For backtrack search, we propose a simple randomized method
for parallelizing sequential backtrack search algorithms for solving
enumeration problems. We show that, uniformly on all instances,
this method is likely to achieve a nearly best possible speed-up.
For branch-and-bound computation, we present a randomized method
called Local Best-First Search for parallelizing sequential
branch-and-bound algorithms. We show that, uniformly on all
instances, the execution time of Local Best-First Search is unlikely
to exceed a certain inherent lower bound by more than a constant
factor. For game-tree search, we present a class of parallel
algorithms that parallelize the `left-to-right' algorithm for
evaluating AND/OR trees and the alpha-beta pruning algorithm for
evaluating MIN/MAX trees, and prove that the algorithm achieves a
linear speed-up over the left-to-right algorithm on uniform AND/OR
trees when the number of processors used is close to the height of
the input tree. We conjecture that the same conclusion holds for the
speed-up of the algorithm over the alpha-beta pruning algorithm.
********************************************************************************
**
There will be a dinner trip afterward to a restaurant in North Dallas for
those interested.