Files in this item



application/pdf9010947.pdf (5MB)Restricted to U of Illinois
(no description provided)PDF


Title:Topics in combinatorics and combinatorial algorithms
Author(s):Madej, Thomas
Doctoral Committee Chair(s):Liu, Jane W.S.
Department / Program:Computer Science
Discipline:Computer Science
Degree Granting Institution:University of Illinois at Urbana-Champaign
Computer Science
Abstract:In this dissertation we investigate three topics. The first is a structural parameter for partially ordered sets (posets). The parameter that we study is the interval number of a poset, denoted by i(P) for a poset P. The interval number is related to a well-studied poset parameter, partial order dimension. We derive an upper bound on the interval number of a poset in terms of its dimension. We determine the interval number exactly for several classes of posets, such as the Boolean algebras. The behavior of interval number under poset operations is studied and so are one-point removal theorems. Asymptotic bounds on the interval number of almost every poset are derived, as well as results concerning the computational complexity of this parameter.
For the second topic we investigate aspects of parallel group testing and apply it to solve the file comparison problem. This problem involves the detection of differences between two copies of the same file located at different sites in a distributed computing system. We derive bounds on the number of group tests needed to detect up to d differing pages, where d is a fixed integer. Related NP-hardness results are derived.
The third topic concerns algorithmic properties of graphs induced by point sets in Euclidean d-dimensional space. For a point set V we define a graph ${\cal G}(V)$ with vertex set V by taking u adjacent to v if and only if there is a line parallel to one of the d coordinate axes and containing both u and v. For such graphs we consider the following algorithmic problems: (1) find an independent set of maximum size; (2) find a cover by cliques of minimum size; (3) for $X\subseteq V$, find a connected cover for X of minimum size; (4) determine the chromatic number of ${\cal G}(V)$; and (5) determine whether or not ${\cal G}(V)$ is Hamiltonian. We prove that these problems are NP-complete in 3 or more dimensions. For problems (1), (2), and (4) we consider approximation algorithms that have relative asymptotic performance ratios bounded by the dimension. These graphs are useful as models for the interconnection network of a family of multiple bus-based computer architectures. (Abstract shortened with permission of author.)
Issue Date:1989
Rights Information:Copyright 1989 Madej, Thomas
Date Available in IDEALS:2011-05-07
Identifier in Online Catalog:AAI9010947
OCLC Identifier:(UMI)AAI9010947

This item appears in the following Collection(s)

Item Statistics