New Results on Combinatorial Algorithms

Research output: ThesisDoctoral 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 node-disjoint 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 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)<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 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<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 polynomial-time algorithm for constructing a minimum broadcasting scheme for a partial <i>k</i>-tree of bounded degree are presented.

Details

Authors
  • Anders Dessmark
Research areas and keywords

Subject classification (UKÄ) – MANDATORY

  • Computer Science

Keywords

  • Sorting, Subgraph isomorphism, Partial k-trees, computer technology, Time complexity, Parallel computation, Data- och systemvetenskap, Convex layers, Systems engineering, Broadcasting
Original languageEnglish
QualificationDoctor
Awarding Institution
Supervisors/Assistant supervisor
  • [unknown], [unknown], Supervisor, External person
Award date1998 Sep 16
Publisher
  • Department of Computer Science, Lund University
Publication statusPublished - 1998
Publication categoryResearch

Bibliographic note

Defence details Date: 1998-09-16 Time: 10:15 Place: E:1406, building E, Lund Institute of Technology External reviewer(s) Name: Seese, Detlef Title: Prof. Affiliation: Karlsruhe ---