The complexity of certain incremental code generation problems

This paper looks at the complexity of four different incremental problems. The following are the problems considered: (1) Interval partitioning of a f low graph (2) Breadth first search (BFS) of a directed graph (3) Lexicograp hic depth first search (DFS) of a directed graph (4) Constructing the posto rder listing of the nodes of a binary tree. The last problem arises out of the need for incrementally computing the Sethi-Ullman (SU) ordering [1] of the subtrees of a tree after it has undergone changes of a given type. Thes e problems are among those that claimed our attention in the process of our designing algorithmic techniques for incremental code generation. BFS and DFS have certainly numerous other applications, but as far as our work is c oncerned, incremental code generation is the common thread linking these pr oblems. The study of the complexity of these problems is done from two diff erent perspectives. In [2] is given the theory of incremental relative lowe r bounds (IRLB). We use this theory to derive the IRLBs of the first three problems. Then we use the notion of a bounded incremental algorithm [4] to prove the unboundedness of the fourth problem with respect to the locally p ersistent model of computation. Possibly, the lower bound result for lexicographic DFS is the most interest ing. In [5] the author considers lexicographic DFS to be a problem for whic h the incremental version may require the recomputation of the entire solut ion from scratch. In that sense, our IRLB result provides further evidence for this possibility with the proviso that the incremental DFS algorithms c onsidered be ones that do not require too much of preprocessing.