Efficient Parallel Algorithms for Combinatorial Problems
(1996)- Abstract
- This thesis is concerned with the design of efficient parallel algorithms for some optimization graph problems. A subset S of vertices or edges in a graph G is said to be maximum with respect to a property if, among all the subsets of G having this property, S is one having the largest cardinality. Set S is said to be maximal with respect to a property, if it is not a proper subset of another set having this property.
A subset of vertices in a graph, is called independent if no two of them are adjacent. The problems of finding maximum and maximal independent sets in a graph are well known. For any positive integer k, we call a set Q of vertices a k-dependent set, if each vertex in Q has no more than k neighbours in Q.... (More) - This thesis is concerned with the design of efficient parallel algorithms for some optimization graph problems. A subset S of vertices or edges in a graph G is said to be maximum with respect to a property if, among all the subsets of G having this property, S is one having the largest cardinality. Set S is said to be maximal with respect to a property, if it is not a proper subset of another set having this property.
A subset of vertices in a graph, is called independent if no two of them are adjacent. The problems of finding maximum and maximal independent sets in a graph are well known. For any positive integer k, we call a set Q of vertices a k-dependent set, if each vertex in Q has no more than k neighbours in Q. Thus an independent set is a 0-dependent set.
We prove that the maximum k-dependent set problem is NP-complete for every fixed integer k even when restricted to planar graphs. We extend known approximation heuristics for the maximum independent set for planar graphs to include maximum k-dependent sets. We observe that these problems can be solved in linear time when restricted to partial k-trees.
While the problem of finding a maximum k-dependent set in a graph is NP hard, finding a maximal k-dependent set can be easily done in linear time using a greedy algorithm. However, constructing efficient parallel algorithms for this problem is not trivial. We present the first NC algorithm for this problem.
A subset of the set of edges in a graph such that no two edges in the set are adjacent is called a matching. Let f be an integer valued function defined over the set of vertices, such that for each vertex v, 0 < f(v) < deg (v). An f-matching is a subset of edges such that for each vertex v at most f(v) edges of the subset are adjacent to v. Taking f(v) = 1 for all vertices v results in an "ordinary" matching.
We don't know whether it is possible to find an NC algorithm for finding a maximum matching. We show that the maximum f-matching problem is NC reducible to the maximum matching problem. A maximal f-matching can be trivially constructed by a greedy sequential algorithm. Designing parallel algorithms for this problem requires more complicated methods. Here we present the first deterministisc and randomized NC algorithms for this problem.
A hypergraph H=(V,E) is a natural generalization of a graph, where an edge in E is an arbitrary subset of the set V. An independent set in H is a subset of V which doesn't include any edge in E. The parallel complexity status of finding a maximal independent set in an arbitrary hypergraph is regarded as a major open problem in parallel complexity theory. We show that this problem admits NC algorithms if the input hypergraph is of so called polylogarithmic arboricity. (Less)
Please use this url to cite or link to this publication:
https://lup.lub.lu.se/record/17590
- author
- Garrido Gómez, Oscar
- supervisor
- opponent
-
- Prof. Sykora, Ondrzej
- publishing date
- 1996
- type
- Thesis
- publication status
- published
- subject
- keywords
- Matematik, Mathematics, Data- och systemvetenskap, computer technology, Systems engineering, matchings., independent sets, graphs, parallel algorithms
- pages
- 72 pages
- publisher
- Department of Computer Science, Lund University
- defense location
- Room E:1406, E-Huset, Lund Technologi Institute, Lund, Sweden
- defense date
- 1996-03-16 10:15:00
- external identifiers
-
- other:LUNSFD6/(NFCS-1009)/1-72/(1996)
- language
- English
- LU publication?
- no
- id
- 4788f1ec-bfeb-4731-9128-a31fbb97d492 (old id 17590)
- date added to LUP
- 2016-04-04 11:27:02
- date last changed
- 2018-11-21 21:04:56
@phdthesis{4788f1ec-bfeb-4731-9128-a31fbb97d492,
abstract = {{This thesis is concerned with the design of efficient parallel algorithms for some optimization graph problems. A subset S of vertices or edges in a graph G is said to be maximum with respect to a property if, among all the subsets of G having this property, S is one having the largest cardinality. Set S is said to be maximal with respect to a property, if it is not a proper subset of another set having this property.<br/><br>
<br/><br>
A subset of vertices in a graph, is called independent if no two of them are adjacent. The problems of finding maximum and maximal independent sets in a graph are well known. For any positive integer k, we call a set Q of vertices a k-dependent set, if each vertex in Q has no more than k neighbours in Q. Thus an independent set is a 0-dependent set.<br/><br>
<br/><br>
We prove that the maximum k-dependent set problem is NP-complete for every fixed integer k even when restricted to planar graphs. We extend known approximation heuristics for the maximum independent set for planar graphs to include maximum k-dependent sets. We observe that these problems can be solved in linear time when restricted to partial k-trees.<br/><br>
<br/><br>
While the problem of finding a maximum k-dependent set in a graph is NP hard, finding a maximal k-dependent set can be easily done in linear time using a greedy algorithm. However, constructing efficient parallel algorithms for this problem is not trivial. We present the first NC algorithm for this problem.<br/><br>
<br/><br>
A subset of the set of edges in a graph such that no two edges in the set are adjacent is called a matching. Let f be an integer valued function defined over the set of vertices, such that for each vertex v, 0 < f(v) < deg (v). An f-matching is a subset of edges such that for each vertex v at most f(v) edges of the subset are adjacent to v. Taking f(v) = 1 for all vertices v results in an "ordinary" matching.<br/><br>
<br/><br>
We don't know whether it is possible to find an NC algorithm for finding a maximum matching. We show that the maximum f-matching problem is NC reducible to the maximum matching problem. A maximal f-matching can be trivially constructed by a greedy sequential algorithm. Designing parallel algorithms for this problem requires more complicated methods. Here we present the first deterministisc and randomized NC algorithms for this problem.<br/><br>
<br/><br>
A hypergraph H=(V,E) is a natural generalization of a graph, where an edge in E is an arbitrary subset of the set V. An independent set in H is a subset of V which doesn't include any edge in E. The parallel complexity status of finding a maximal independent set in an arbitrary hypergraph is regarded as a major open problem in parallel complexity theory. We show that this problem admits NC algorithms if the input hypergraph is of so called polylogarithmic arboricity.}},
author = {{Garrido Gómez, Oscar}},
keywords = {{Matematik; Mathematics; Data- och systemvetenskap; computer technology; Systems engineering; matchings.; independent sets; graphs; parallel algorithms}},
language = {{eng}},
publisher = {{Department of Computer Science, Lund University}},
title = {{Efficient Parallel Algorithms for Combinatorial Problems}},
year = {{1996}},
}