# Lund University Publications

## LUND UNIVERSITY LIBRARIES

### New Results on Combinatorial Algorithms

(1998)
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... (More)
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. (Less)
author
supervisor
opponent
• Prof. Seese, Detlef, Karlsruhe
organization
publishing date
type
Thesis
publication status
published
subject
keywords
Sorting, Subgraph isomorphism, Partial k-trees, computer technology, Time complexity, Parallel computation, Data- och systemvetenskap, Convex layers, Systems engineering, Broadcasting
pages
118 pages
publisher
Department of Computer Science, Lund University
defense location
E:1406, building E, Lund Institute of Technology
defense date
1998-09-16 10:15:00
external identifiers
• other:ISRN: LUNFD6/(NFCS-1013)/1-118/(1998)
language
English
LU publication?
yes
id
5883b0c3-173a-4e8e-b785-7807f4e858c9 (old id 18928)
2016-04-04 10:49:08
date last changed
2018-11-21 21:00:57
```@phdthesis{5883b0c3-173a-4e8e-b785-7807f4e858c9,
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 &lt;i&gt;k&lt;/i&gt;-connected partial &lt;i&gt;k&lt;/i&gt;-tree is isomorphic to subgraph of another partial &lt;i&gt;k&lt;/i&gt;-tree is shown to be solvable in time &lt;i&gt;O(n&lt;sup&gt;k+2&lt;/sup&gt;)&lt;/i&gt;. The problem of determining the maximum number of node-disjoint subgraphs of a partial &lt;i&gt;k&lt;/i&gt;-tree &lt;i&gt;H&lt;/i&gt; on &lt;i&gt;n&lt;sub&gt;H&lt;/sub&gt;&lt;/i&gt; nodes that are isomorphic to a &lt;i&gt;k&lt;/i&gt;-connected partial &lt;i&gt;k&lt;/i&gt;-tree &lt;i&gt;G&lt;/i&gt; on &lt;i&gt;n&lt;sub&gt;G&lt;/sub&gt;&lt;/i&gt; nodes is shown to be solvable in time &lt;i&gt;O(n&lt;sub&gt;G&lt;/sub&gt;&lt;sup&gt;k+1&lt;/sup&gt;n&lt;sub&gt;H&lt;/sub&gt; + n&lt;sub&gt;H&lt;/sub&gt;&lt;sup&gt;k&lt;/sup&gt;)&lt;/i&gt;. The maximum two-dimensional pattern matching problem is proved to admit an &lt;i&gt;O(n&lt;/i&gt; log &lt;i&gt;n)&lt;/i&gt; time approximation algorithm with relative error &lt;i&gt;O(1/(&lt;/i&gt;log log &lt;i&gt;n)&lt;sup&gt;1/2&lt;/sup&gt;)&lt;/i&gt; 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 &lt;i&gt;k&lt;/i&gt;-dependent and &lt;i&gt;f&lt;/i&gt;-dependent set problem in trees, partial &lt;i&gt;k&lt;/i&gt;-trees, cographs and splitgraphs. The problem is shown to be NP-complete for planar bipartite graphs when &lt;i&gt;k &gt; 1&lt;/i&gt;. A combinatorial generalization of the convex layer problem, termed &lt;i&gt;multi-list layering&lt;/i&gt; 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 &lt;i&gt;n&lt;/i&gt; integers of size &lt;i&gt;n&lt;sup&gt;O(1)&lt;/sup&gt;&lt;/i&gt; can be sorted in time &lt;i&gt;O(&lt;/i&gt;log&lt;i&gt;&lt;sup&gt;3/2&lt;/sup&gt; n)&lt;/i&gt; on an EREW PRAM with &lt;i&gt;n/&lt;/i&gt;log &lt;i&gt;n&lt;/i&gt; processors, improving the previous best work bound from &lt;i&gt;O(n (&lt;/i&gt;log &lt;i&gt;n&lt;/i&gt; log log &lt;i&gt;n)&lt;sup&gt;1/2&lt;/sup&gt;)&lt;/i&gt; to &lt;i&gt;O(n (&lt;/i&gt;log &lt;i&gt;n)&lt;sup&gt;1/2&lt;/sup&gt;)&lt;/i&gt;. 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 &lt;i&gt;k&lt;/i&gt;-tree of bounded degree are presented.}},
author       = {{Dessmark, Anders}},
keywords     = {{Sorting; Subgraph isomorphism; Partial k-trees; computer technology; Time complexity; Parallel computation; Data- och systemvetenskap; Convex layers; Systems engineering; Broadcasting}},
language     = {{eng}},
publisher    = {{Department of Computer Science, Lund University}},
school       = {{Lund University}},
title        = {{New Results on Combinatorial Algorithms}},
year         = {{1998}},
}

```