Algorithms for some problems on trees and graphs

Abstract

Design and analysis of graph algorithms is an active area of research in Computer Science. Trees form an important subclass of graphs and have vast applications. In this thesis, we present some new algorithmic results on trees. We also present certain additional results in algorithmic graph theory. We present a very simple linear-time algorithm for the problem of constructing a binary tree from its preorder and inorder traversals. The algorithm leads to an optimal O(log n) time parallel algorithm on the EREW PRAM model. We present a simple one-to-one correspondence between binary trees of n nodes and 321-avoidable permutations of size n. We give the first loopless algorithms for generation of:

(a) All k-ary trees of n nodes (b) All binary trees with a given degree sequence (c) All legal parenthesis sequences of size 2n

We solve the problem of repair of tree-generating regular systems in time linear in the number of vertices of the tree, assuming that the number of states of the tree automata is constant. We also present two other results of algorithmic interest:

First, we present a simple O(n log n) time algorithm for finding a maximum independent set of a permutation graph. This algorithm is used to solve a problem in memory allocation in O(n log n) time. Next, we present two randomized algorithms for the problem of online layered graph traversal, assuming that the width of the graph is equal to two. The algorithms achieve competitive ratios of 5.5 and 7, respectively. This improves the known results for the problem