{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/121433"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/121433","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Cuts and partitions: solving, counting, and enumerating","abstract":"Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2023-12-04 without embargo terms","abstract_html":"Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2023-12-04 without embargo terms","abstract_has_math":false,"creators":["Beideman, Calvin"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Chandrasekaran, Karthekeyan","Chekuri, Chandra","Har-Peled, Sariel","Mukhopadhyay, Sagnik"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2023,"date_issued":"2023-08","date_published":"2023-08","updated_at":"2026-07-22T22:24:57Z","subjects":["Min-cut","Connectivity","Hypergraphs","Min-k-cut","Combinatorial Optimization","Multicriteria Optimization"],"languages":["en","eng"],"rights":["Copyright 2023 Calvin Beideman"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"https://hdl.handle.net/2142/121433","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Chandrasekaran, Karthekeyan","Chekuri, Chandra","Har-Peled, Sariel","Mukhopadhyay, Sagnik"]},{"key":"dc:creator","label":"Author","values":["Beideman, Calvin"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2023-08","2023-06-27"]},{"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":["Min-cut","Connectivity","Hypergraphs","Min-k-cut","Combinatorial Optimization","Multicriteria Optimization"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en","eng"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2023 Calvin Beideman"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://hdl.handle.net/2142/121433"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2023-12-04 without embargo terms","The student, Calvin Beideman, accepted the attached license on 2023-06-26 at 16:58.","The student, Calvin Beideman, submitted this Dissertation for approval on 2023-06-26 at 17:09.","This Dissertation was approved for publication on 2023-06-27 at 15:26.","DSpace SAF Submission Ingestion Package generated from Vireo submission #19465 on 2023-12-04 at 17:00:12","The problem of finding a global minimum cut in an undirected graph is fundamental to combinatorial optimization. It has numerous applications including network reliability, clustering, and the Travelling Salesman Problem. In addition to this computational problem, structural and enumerative aspects of minimum cuts are also foundational to representation and algorithmic results. The number of constant-approximate global minimum cuts in a connected graph is polynomial in the number of vertices. This structural result has applications in constructing cut sparsifiers, sketching and streaming algorithms, and approximation algorithms for TSP. In this thesis we consider various generalizations of the minimum cut problem. We focus on solving these variants and on counting and enumerating optimum solutions. Our results include: - A new and faster algorithm for computing connectivity in hypergraphs, - The first deterministic polynomial time algorithm for enumerating hypergraph min-$k$-cut-sets, - The first polynomial bound on the number of Multiobjective Min-cuts for a constant number of cost functions as well as the first polynomial time algorithm for enumerating all of them, and - Inapproximability results for representing symmetric submodular functions using hypergraph cut functions."]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Cuts and partitions: solving, counting, and enumerating"]}]}],"canonical_facts":{"dc:contributor":["Chandrasekaran, Karthekeyan","Chekuri, Chandra","Har-Peled, Sariel","Mukhopadhyay, Sagnik"],"dc:creator":["Beideman, Calvin"],"dc:date":["2023-08","2023-06-27"],"dc:description":["Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2023-12-04 without embargo terms","The student, Calvin Beideman, accepted the attached license on 2023-06-26 at 16:58.","The student, Calvin Beideman, submitted this Dissertation for approval on 2023-06-26 at 17:09.","This Dissertation was approved for publication on 2023-06-27 at 15:26.","DSpace SAF Submission Ingestion Package generated from Vireo submission #19465 on 2023-12-04 at 17:00:12","The problem of finding a global minimum cut in an undirected graph is fundamental to combinatorial optimization. It has numerous applications including network reliability, clustering, and the Travelling Salesman Problem. In addition to this computational problem, structural and enumerative aspects of minimum cuts are also foundational to representation and algorithmic results. The number of constant-approximate global minimum cuts in a connected graph is polynomial in the number of vertices. This structural result has applications in constructing cut sparsifiers, sketching and streaming algorithms, and approximation algorithms for TSP. In this thesis we consider various generalizations of the minimum cut problem. We focus on solving these variants and on counting and enumerating optimum solutions. Our results include: - A new and faster algorithm for computing connectivity in hypergraphs, - The first deterministic polynomial time algorithm for enumerating hypergraph min-$k$-cut-sets, - The first polynomial bound on the number of Multiobjective Min-cuts for a constant number of cost functions as well as the first polynomial time algorithm for enumerating all of them, and - Inapproximability results for representing symmetric submodular functions using hypergraph cut functions."],"dc:format":["application/pdf"],"dc:identifier":["https://hdl.handle.net/2142/121433"],"dc:language":["en","eng"],"dc:rights":["Copyright 2023 Calvin Beideman"],"dc:subject":["Min-cut","Connectivity","Hypergraphs","Min-k-cut","Combinatorial Optimization","Multicriteria Optimization"],"dc:title":["Cuts and partitions: solving, counting, and enumerating"],"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:24:57Z"}