TY - JOUR

T1 - Dynamic trees as search trees via Euler tours, applied to the network simplex algorithm

AU - Tarjan, Robert E.

N1 - Funding Information:
J Research at Princeton University partially supported by the National Science Foundation, Grant No. CCR-8920505, and the Office of Naval Research, Contract No. N0014-91-J-1463. Work during a visit to MI.T. partially supported by ARPA Contract No. 14-95-1-1246. Email: [email protected].

PY - 1997/8/1

Y1 - 1997/8/1

N2 - 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, 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.

AB - 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, 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.

UR - http://www.scopus.com/inward/record.url?scp=0031212426&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0031212426&partnerID=8YFLogxK

U2 - 10.1007/BF02614369

DO - 10.1007/BF02614369

M3 - Article

AN - SCOPUS:0031212426

SN - 0025-5610

VL - 78

SP - 169

EP - 177

JO - Mathematical Programming, Series B

JF - Mathematical Programming, Series B

IS - 2

ER -