New Results on Combinatorial Algorithms
Research output: Thesis › Doctoral Thesis (monograph)
Abstract
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<sup>k+2</sup>)</i>. The problem of determining the maximum number of nodedisjoint subgraphs of a partial <i>k</i>tree <i>H</i> on <i>n<sub>H</sub></i> nodes that are isomorphic to a <i>k</i>connected partial <i>k</i>tree <i>G</i> on <i>n<sub>G</sub></i> nodes is shown to be solvable in time <i>O(n<sub>G</sub><sup>k+1</sup>n<sub>H</sub> + n<sub>H</sub><sup>k</sup>)</i>. The maximum twodimensional 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)<sup>1/2</sup>)</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 NPcomplete for planar bipartite graphs when <i>k > 1</i>. A combinatorial generalization of the convex layer problem, termed <i>multilist layering</i> is shown to be Pcomplete. Fast efficient parallel algorithms for multilist 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<sup>O(1)</sup></i> can be sorted in time <i>O(</i>log<i><sup>3/2</sup> 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)<sup>1/2</sup>)</i> to <i>O(n (</i>log <i>n)<sup>1/2</sup>)</i>. Efficient algorithms for constructing minimum broadcasting schemes for several types of weakly cyclic graphs and a polynomialtime algorithm for constructing a minimum broadcasting scheme for a partial <i>k</i>tree of bounded degree are presented.
Details
Authors  

Research areas and keywords  Subject classification (UKÄ) – MANDATORY
Keywords

Original language  English 

Qualification  Doctor 
Awarding Institution  
Supervisors/Assistant supervisor 

Award date  1998 Sep 16 
Publisher 

Publication status  Published  1998 
Publication category  Research 
Bibliographic note
Defence details
Date: 19980916
Time: 10:15
Place: E:1406, building E, Lund Institute of Technology
External reviewer(s)
Name: Seese, Detlef
Title: Prof.
Affiliation: Karlsruhe
