New Results on Combinatorial Algorithms

In this thesis improved upper bounds for several important combinatorial problems are provided. Below is a list of the main results showed in the thesis. The problem of determining whether a k-connected partial k-tree is isomorphic to subgraph of another partial k-tree is shown to be solvable in time O(nk+2). The problem of determining the maximum number of node-disjoint subgraphs of a partial k-tree H on nH nodes that are isomorphic to a k-connected partial k-tree G on nG nodes is shown to be solvable in time O(nGk+1nH + nHk). The maximum two-dimensional pattern matching problem is proved to admit an O(n log n) time approximation algorithm with relative error O(1/(log log n)1/2) for constant size patterns. Also, a fast efficient parallel approximation scheme for the problem is given. Efficient sequential and parallel algorithms are presented for the maximum k-dependent and f-dependent set problem in trees, partial k-trees, cographs and splitgraphs. The problem is shown to be NP-complete for planar bipartite graphs when k > 1. A combinatorial generalization of the convex layer problem, termed multi-list layering is shown to be P-complete. Fast efficient parallel algorithms for multi-list layering when the number of lists or the layer size is bounded by a constant are given. We show that n integers of size nO(1) can be sorted in time O(log3/2 n) on an EREW PRAM with n/log n processors, improving the previous best work bound from O(n (log n log log n)1/2) to O(n (log n)1/2). Efficient algorithms for constructing minimum broadcasting schemes for several types of weakly cyclic graphs and a polynomial-time algorithm for constructing a minimum broadcasting scheme for a partial k-tree of bounded degree are presented