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 <i>k</i>-connected partial <i>k</i>-tree is isomorphic to subgraph of another partial <i>k</i>-tree is shown to be solvable in time <i>O(n^k+2)</i>. The problem of determining the maximum number of node-disjoint subgraphs of a partial <i>k</i>-tree <i>H</i> on <i>n_H</i> nodes that are isomorphic to a <i>k</i>-connected partial <i>k</i>-tree <i>G</i> on <i>n_G</i> nodes is shown to be solvable in time <i>O(n_G^k+1n_H + n_H^k)</i>. The maximum two-dimensional pattern matching problem is proved to admit an <i>O(n</i> log <i>n)</i> time approximation algorithm with relative error <i>O(1/(</i>log log <i>n)^1/2)</i> 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 <i>k</i>-dependent and <i>f</i>-dependent set problem in trees, partial <i>k</i>-trees, cographs and splitgraphs. The problem is shown to be NP-complete for planar bipartite graphs when <i>k > 1</i>. A combinatorial generalization of the convex layer problem, termed <i>multi-list layering</i> 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 <i>n</i> integers of size <i>n^O(1)</i> can be sorted in time <i>O(</i>log<i>^3/2 n)</i> on an EREW PRAM with <i>n/</i>log <i>n</i> processors, improving the previous best work bound from <i>O(n (</i>log <i>n</i> log log <i>n)^1/2)</i> to <i>O(n (</i>log <i>n)^1/2)</i>. 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 <i>k</i>-tree of bounded degree are presented.