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)
Please use this url to cite or link to this publication:
https://lup.lub.lu.se/record/18928
- author
- Dessmark, Anders LU
- supervisor
- opponent
-
- Prof. Seese, Detlef, Karlsruhe
- organization
- publishing date
- 1998
- 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)
- date added to LUP
- 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 <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.}},
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}},
}