2026-09-19T22:04:04Z https://www.ideals.illinois.edu/oai-pmh

oai:www.ideals.illinois.edu:2142/120258 2023-09-05 col_2142_5131 col_2142_16340 com_2142_5130 com_2142_16339 com_2142_8903

Chandrasekaran, Karthekeyan Balogh, József Chekuri, Chandra Kostochka, Alexandr 2023-05 application/pdf en text Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2023-09-01 without embargo terms The student, Weihang Wang, accepted the attached license on 2023-04-12 at 22:21. The student, Weihang Wang, submitted this Dissertation for approval on 2023-04-13 at 11:59. This Dissertation was approved for publication on 2023-04-24 at 09:11. DSpace SAF Submission Ingestion Package generated from Vireo submission #18965 on 2023-09-01 at 17:08:18 Algorithms for new objectives in graph partitioning and generalizations Wang, Weihang 2023-04-24 Graph Partitioning Hypergraph Partitioning Submodular Partitioning Algorithms Graph Theory In this thesis, we consider a class of graph partitioning problems: The input consists of a graph and a positive integer k, and the goal is to partition the vertex set of the graph into k parts while satisfying certain constraints in order to optimize an objective of interest. Varying constraints and objectives lead to a wide variety of graph partitioning problems. The classic Graph-MinCut and Graph-Min-(s,t)-Cut problems can be viewed as special cases of these problems. The study of these problems has led to novel algorithmic techniques and structural results as well as developed connections between graph theory and algorithms. Graph partitioning problems further generalize to hypergraph and submodular partitioning problems. In this thesis, we investigate new objectives in graph and hypergraph partitioning and long-standing objectives in submodular partitioning. We advance both algorithmic and structural aspects of the associated partitioning problems. We show hardness results for several graph partitioning problems under new objectives. We design approximation algorithms and fixed-parameter approximation scheme to solve these graph partitioning problems. We prove new structural results for graphs and hypergraphs that lead to polynomial-time algorithms to enumerate all optimum solutions of certain graph/hypergraph partitioning problems. We analyze the approximation factor of a classic algorithm for submodular partitioning based on principle partition sequence for monotone, symmetric, and posimodular submodular function families. Thesis eng https://hdl.handle.net/2142/120258 Copyright 2023 Weihang Wang Ph.D. Dissertation Mathematics University of Illinois at Urbana-Champaign Mathematics