# Topics in combinatorics and combinatorial algorithms

Bookmark or cite this item: http://hdl.handle.net/2142/20233

## Files in this item

File Description Format
9010947.pdf (5MB) (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 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 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 Type: Text Language: English URI: http://hdl.handle.net/2142/20233 Rights Information: Copyright 1989 Madej, Thomas Date Available in IDEALS: 2011-05-07 Identifier in Online Catalog: AAI9010947 OCLC Identifier: (UMI)AAI9010947