Douglas R. Shier

Department of Mathematical Sciences

Clemson University

Clemson, SC 29634-0975

Abstract: To carry out network optimization algorithms, careful attention needs to be paid to the data structures supporting these algorithms. In particular, there are several different ways to represent a network—and these differ in their storage requirements as well as their ease in enabling certain fundamental operations. These representations need to incorporate both the topology of the underlying graph and also any quantitative information present in the network (such as cost, length, capacity, demand, supply). Standard representations of networks are surveyed in this section. In addition, since trees are important objects in optimization problems as well as useful data structures in their own right, additional representations and features of trees are also discussed.

Key Words: adjacency matrix, adjacency set, forward star, linked adjacency list, predecessor map