Topics in combinatorics and combinatorial algorithms
Madej, Thomas
This item is only available for download by members of the University of Illinois community. Students, faculty, and staff at the U of I may log in with your NetID and password to view the item. If you are trying to access an Illinois-restricted dissertation or thesis, you can request a copy through your library's Inter-Library Loan office or purchase a copy directly from ProQuest.
Permalink
https://hdl.handle.net/2142/20233
Description
Title
Topics in combinatorics and combinatorial algorithms
Author(s)
Madej, Thomas
Issue Date
1989
Doctoral Committee Chair(s)
Liu, Jane W.S.
Department of Study
Computer Science
Discipline
Computer Science
Degree Granting Institution
University of Illinois at Urbana-Champaign
Degree Name
Ph.D.
Degree Level
Dissertation
Date of Ingest
2011-05-07T12:33:05Z
Keyword(s)
Mathematics
Computer Science
Language
eng
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.)
Use this login method if you
don't
have an
@illinois.edu
email address.
(Oops, I do have one)
IDEALS migrated to a new platform on June 23, 2022. If you created
your account prior to this date, you will have to reset your password
using the forgot-password link below.
