{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/81597"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/81597","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Multichannel Communication and Graph Vertex Labeling Problems","abstract":"Depending on the type of data, error measure, and type of failure, the problem of designing these encoding schemes is equivalent to several classical problems in graph theory. For example, no-redundancy encodings that minimize maximum absolute error for complete loss of data correspond to the problem of bandwidth optimization of Hamming graphs (Cartesian products of cliques). The graph problem has been open since the 1960s. In this thesis, we demonstrate lower bounds and a nearly optimal solution to this problem. Using techniques developed for this solution, we give an algorithm for the wirelength optimization problem of grid graphs (products of paths) of arbitrary dimensions. This is the first constructive result for the product of more than two paths. In the communications setting, this problem is equivalent to designing no-redundancy encodings that minimize average error of a distance-1 type of medium failure. Similar techniques solved an unrelated graph edge isoperimetric problem. In addition, extending the algorithm to allow redundancy in the encoding improved the only previously known constructive result.","abstract_html":"Depending on the type of data, error measure, and type of failure, the problem of designing these encoding schemes is equivalent to several classical problems in graph theory. For example, no-redundancy encodings that minimize maximum absolute error for complete loss of data correspond to the problem of bandwidth optimization of Hamming graphs (Cartesian products of cliques). The graph problem has been open since the 1960s. In this thesis, we demonstrate lower bounds and a nearly optimal solution to this problem. Using techniques developed for this solution, we give an algorithm for the wirelength optimization problem of grid graphs (products of paths) of arbitrary dimensions. This is the first constructive result for the product of more than two paths. In the communications setting, this problem is equivalent to designing no-redundancy encodings that minimize average error of a distance-1 type of medium failure. Similar techniques solved an unrelated graph edge isoperimetric problem. In addition, extending the algorithm to allow redundancy in the encoding improved the only previously known constructive result.","abstract_has_math":false,"creators":["Berger-Wolf, Yonit"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Edward M. Reingold"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2015,"date_issued":"2015-09-25T20:19:24Z","date_published":"2015-09-25T20:19:24Z","updated_at":"2026-07-22T22:26:16Z","subjects":["Mathematics"],"languages":["eng"],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["(MiAaPQ)AAI3044052"],"render_values":[{"text":"(MiAaPQ)AAI3044052","href":null,"code":true}]}]},"links":{"outbound_url":"http://hdl.handle.net/2142/81597","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Edward M. Reingold"]},{"key":"dc:creator","label":"Author","values":["Berger-Wolf, Yonit"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2015-09-25T20:19:24Z","10000-01-01","2002"]},{"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"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["eng"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/81597","(MiAaPQ)AAI3044052"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Depending on the type of data, error measure, and type of failure, the problem of designing these encoding schemes is equivalent to several classical problems in graph theory. For example, no-redundancy encodings that minimize maximum absolute error for complete loss of data correspond to the problem of bandwidth optimization of Hamming graphs (Cartesian products of cliques). The graph problem has been open since the 1960s. In this thesis, we demonstrate lower bounds and a nearly optimal solution to this problem. Using techniques developed for this solution, we give an algorithm for the wirelength optimization problem of grid graphs (products of paths) of arbitrary dimensions. This is the first constructive result for the product of more than two paths. In the communications setting, this problem is equivalent to designing no-redundancy encodings that minimize average error of a distance-1 type of medium failure. Similar techniques solved an unrelated graph edge isoperimetric problem. In addition, extending the algorithm to allow redundancy in the encoding improved the only previously known constructive result.","Made available in DSpace on 2015-09-25T20:19:24Z (GMT). No. of bitstreams: 2 license.txt: 4848 bytes, checksum: 96035ab3f5e1c23cc7138a224ce498bd (MD5) 3044052.pdf: 4185701 bytes, checksum: 2a15a8eeb424d078ae9af8937f87682e (MD5) Previous issue date: 2002","Embargo set by: Seth Robbins for item 82878 Lift date: Forever Reason: Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs","Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs","U of I Only","90 p.","Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 2002."]},{"key":"dc:title","label":"Title","values":["Multichannel Communication and Graph Vertex Labeling Problems"]}]}],"canonical_facts":{"dc:contributor":["Edward M. Reingold"],"dc:creator":["Berger-Wolf, Yonit"],"dc:date":["2015-09-25T20:19:24Z","10000-01-01","2002"],"dc:description":["Depending on the type of data, error measure, and type of failure, the problem of designing these encoding schemes is equivalent to several classical problems in graph theory. For example, no-redundancy encodings that minimize maximum absolute error for complete loss of data correspond to the problem of bandwidth optimization of Hamming graphs (Cartesian products of cliques). The graph problem has been open since the 1960s. In this thesis, we demonstrate lower bounds and a nearly optimal solution to this problem. Using techniques developed for this solution, we give an algorithm for the wirelength optimization problem of grid graphs (products of paths) of arbitrary dimensions. This is the first constructive result for the product of more than two paths. In the communications setting, this problem is equivalent to designing no-redundancy encodings that minimize average error of a distance-1 type of medium failure. Similar techniques solved an unrelated graph edge isoperimetric problem. In addition, extending the algorithm to allow redundancy in the encoding improved the only previously known constructive result.","Made available in DSpace on 2015-09-25T20:19:24Z (GMT). No. of bitstreams: 2 license.txt: 4848 bytes, checksum: 96035ab3f5e1c23cc7138a224ce498bd (MD5) 3044052.pdf: 4185701 bytes, checksum: 2a15a8eeb424d078ae9af8937f87682e (MD5) Previous issue date: 2002","Embargo set by: Seth Robbins for item 82878 Lift date: Forever Reason: Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs","Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs","U of I Only","90 p.","Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 2002."],"dc:identifier":["http://hdl.handle.net/2142/81597","(MiAaPQ)AAI3044052"],"dc:language":["eng"],"dc:subject":["Mathematics"],"dc:title":["Multichannel Communication and Graph Vertex Labeling Problems"],"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:26:16Z"}