Quick links

Dynamic Trees as Search Trees via Euler Tours, Applied to the Network Simplex Algorithm

Report ID:
TR-503-95
Date:
August 1995
Pages:
10
Download Formats:

Abstract:

The dynamic tree is an abstract data type that allows
the maintenance of a collection of trees subject to joining by adding edges
(linking) and splitting by deleting edges (cutting),
while at the same time allowing reporting of certain combinations of vertex or
edge values. For many applications of dynamic trees, values must be
combined along paths. For other applications, values must be combined over
entire trees. For the latter situation, we show that an idea
used originally in parallel graph algorithms, to represent trees by Euler tours,
leads to a simple implementation with a time of O(log n) per tree
operation, where n is the number of tree vertices. We apply this
representation to the implementation of two versions of
the network simplex algorithm, resulting in a time of O(log n) per pivot,
where n is the number of vertices in the problem network.

Follow us: Facebook Twitter Linkedin