Files in this item
Files  Description  Format 

application/pdf 9010947.pdf (5MB)  (no description provided) 
Description
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 UrbanaChampaign 
Degree:  Ph.D. 
Genre:  Dissertation 
Subject(s):  Mathematics
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 wellstudied 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 onepoint 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 NPhardness results are derived. The third topic concerns algorithmic properties of graphs induced by point sets in Euclidean ddimensional 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 NPcomplete 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 busbased computer architectures. (Abstract shortened with permission of author.) 
Issue Date:  1989 
Type:  Text 
Language:  English 
URI:  http://hdl.handle.net/2142/20233 
Rights Information:  Copyright 1989 Madej, Thomas 
Date Available in IDEALS:  20110507 
Identifier in Online Catalog:  AAI9010947 
OCLC Identifier:  (UMI)AAI9010947 
This item appears in the following Collection(s)

Graduate Dissertations and Theses at Illinois
Graduate Theses and Dissertations at Illinois 
Dissertations and Theses  Computer Science
Dissertations and Theses from the Dept. of Computer Science