Director of Research (if dissertation) or Advisor (if thesis)
Chandrasekaran, Karthekeyan
Doctoral Committee Chair(s)
Chekuri, Chandra
Committee Member(s)
Erickson, Jeff
Király, Tamás
Department of Study
Computer Science
Discipline
Computer Science
Degree Granting Institution
University of Illinois at Urbana-Champaign
Degree Name
Ph.D.
Degree Level
Dissertation
Date of Ingest
2018-09-04T20:27:15Z
Keyword(s)
hypergraph
cuts
Abstract
In this thesis, we consider cut and connectivity problems on graphs, digraphs, hypergraphs and hedgegraphs.
The main results are the following:
- We introduce a faster algorithm for finding the reduced graph in element-connectivity computations. We also show its application to node separation.
- We present several results on hypergraph cuts, including (a) a near linear time algorithm for finding a (2+epsilon)-approximate min-cut, (b) an algorithm to find a representation of all min-cuts in the same time as finding a single min-cut, (c) a sparse subgraph that preserves connectivity for hypergraphs and (d) a near linear-time hypergraph cut sparsifier.
- We design the first randomized polynomial time algorithm for the hypergraph k-cut problem whose complexity has been open for over 20 years. The algorithm generalizes to hedgegraphs with constant span.
- We address the complexity gap between global vs. fixed-terminal cuts problems in digraphs by presenting a 2-1/448 approximation algorithm for the global bicut problem.
Use this login method if you
don't
have an
@illinois.edu
email address.
(Oops, I do have one)
IDEALS migrated to a new platform on June 23, 2022. If you created
your account prior to this date, you will have to reset your password
using the forgot-password link below.
XU-DISSERTATION-2018.pdf
