Associative parallel algorithms
of optimization
on graphs
1999. (supported by Russian Basic Research Foundation under grant
No. 99--01--00--548).
Nepomniaschaya A.S.
Dvoskina M.A.
This project is aimed at solving a group of graph optimizing problems by
means of vertical processing systems.
For directed graphs we are planning to design new associative parallel
algorithms for selecting optimum branchings, for finding shortest paths from
the given source vertex to all other vertices and finding the shortest path
between two given vertices. Typical shortest path algorithms for general
network topologies are Dijkstra's algorithm and the Bellman-Ford algorithm.
Other shortest path algorithms are variations of either Dijkstra's algorithm
or the Bellman-Ford algorithm. Our goal is to design efficient associative
versions of Dijkstra's algorithm and the Bellman-Ford algorithm by means of
the STAR-machine being a formal model of vertical processing systems.
For undirected graphs we are planning to study a group of dynamic
associative parallel algorithms for updating minimal spanning trees (MST).
Dynamic graph algorithms are designed to handle graph changes, that is,
a dynamic algorithm maintains some property of the graph more efficiently
than a recomputation from scratch. The group of associative parallel
algorithms will include designing a new MST from the current MST after
adding or deleting an edge in the given graph, after changing an edge weight,
after adding or deleting a vertex along with the incident edges.
Last update Jan
25, 2000