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 kdependent 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 kdependent set, if each vertex in Q has no more than k neighbours in Q. Thus an independent set is a 0dependent set.
We prove that the maximum kdependent set problem is NPcomplete 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 kdependent sets. We observe that these problems can be solved in linear time when restricted to partial ktrees.
While the problem of finding a maximum kdependent set in a graph is NP hard, finding a maximal kdependent 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 fmatching 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 fmatching problem is NC reducible to the maximum matching problem. A maximal fmatching 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:
http://lup.lub.lu.se/record/17590
 author
 Garrido Gómez, Oscar
 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, EHuset, Lund Technologi Institute, Lund, Sweden
 defense date
 19960316 10:15
 external identifiers

 other:LUNSFD6/(NFCS1009)/172/(1996)
 language
 English
 LU publication?
 no
 id
 4788f1ecbfeb47319128a31fbb97d492 (old id 17590)
 date added to LUP
 20070524 09:43:40
 date last changed
 20180529 10:34:49
@phdthesis{4788f1ecbfeb47319128a31fbb97d492, 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 kdependent set, if each vertex in Q has no more than k neighbours in Q. Thus an independent set is a 0dependent set.<br/><br> <br/><br> We prove that the maximum kdependent set problem is NPcomplete 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 kdependent sets. We observe that these problems can be solved in linear time when restricted to partial ktrees.<br/><br> <br/><br> While the problem of finding a maximum kdependent set in a graph is NP hard, finding a maximal kdependent 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 fmatching 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 fmatching problem is NC reducible to the maximum matching problem. A maximal fmatching 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}, keyword = {Matematik,Mathematics,Data och systemvetenskap,computer technology,Systems engineering,matchings.,independent sets,graphs,parallel algorithms}, language = {eng}, pages = {72}, publisher = {Department of Computer Science, Lund University}, title = {Efficient Parallel Algorithms for Combinatorial Problems}, year = {1996}, }