{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/20233"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/20233","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Topics in combinatorics and combinatorial algorithms","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.","abstract_html":"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.","abstract_has_math":false,"creators":["Madej, Thomas"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Liu, Jane W.S."],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2011,"date_issued":"2011-05-07T12:33:05Z","date_published":"2011-05-07T12:33:05Z","updated_at":"2026-07-22T22:25:15Z","subjects":["Mathematics","Computer Science"],"languages":["eng"],"rights":["Copyright 1989 Madej, Thomas"],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["AAI9010947","(UMI)AAI9010947"],"render_values":[{"text":"AAI9010947","href":null,"code":true},{"text":"(UMI)AAI9010947","href":null,"code":true}]}]},"links":{"outbound_url":"http://hdl.handle.net/2142/20233","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Liu, Jane W.S."]},{"key":"dc:creator","label":"Author","values":["Madej, Thomas"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2011-05-07T12:33:05Z","10000-01-01","1989"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Mathematics","Computer Science"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["eng"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 1989 Madej, Thomas"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["AAI9010947","(UMI)AAI9010947","http://hdl.handle.net/2142/20233"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["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.)","Made available in DSpace on 2011-05-07T12:33:05Z (GMT). No. of bitstreams: 2 license.txt: 4922 bytes, checksum: 910b249b4beec47e7ab768910c8f966f (MD5) 9010947.pdf: 4830106 bytes, checksum: bb4b6195ff8dafb93b69e434ddbd43e0 (MD5) Previous issue date: 1989","Item marked as restricted to the 'UIUC Users [automated]' Group (id=2) by Howard Ding (hding2@illinois.edu) on 2011-05-07T14:42:31Z Item is restricted indefinitely.","Restriction data tranferred 2014-07-01T11:18:29-05:00 Original Data Group with Access UIUC Users [automated] Release Date: none Reason: ETDs are only available to UIUC Users without author permission","ETDs are only available to UIUC Users without author permission","U of I Only"]},{"key":"dc:title","label":"Title","values":["Topics in combinatorics and combinatorial algorithms"]}]}],"canonical_facts":{"dc:contributor":["Liu, Jane W.S."],"dc:creator":["Madej, Thomas"],"dc:date":["2011-05-07T12:33:05Z","10000-01-01","1989"],"dc:description":["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.)","Made available in DSpace on 2011-05-07T12:33:05Z (GMT). No. of bitstreams: 2 license.txt: 4922 bytes, checksum: 910b249b4beec47e7ab768910c8f966f (MD5) 9010947.pdf: 4830106 bytes, checksum: bb4b6195ff8dafb93b69e434ddbd43e0 (MD5) Previous issue date: 1989","Item marked as restricted to the 'UIUC Users [automated]' Group (id=2) by Howard Ding (hding2@illinois.edu) on 2011-05-07T14:42:31Z Item is restricted indefinitely.","Restriction data tranferred 2014-07-01T11:18:29-05:00 Original Data Group with Access UIUC Users [automated] Release Date: none Reason: ETDs are only available to UIUC Users without author permission","ETDs are only available to UIUC Users without author permission","U of I Only"],"dc:identifier":["AAI9010947","(UMI)AAI9010947","http://hdl.handle.net/2142/20233"],"dc:language":["eng"],"dc:rights":["Copyright 1989 Madej, Thomas"],"dc:subject":["Mathematics","Computer Science"],"dc:title":["Topics in combinatorics and combinatorial algorithms"],"dc:type":["text"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:25:15Z"}