Back to search

Cornell University

Implementations of Cut Algorithms

Abstract

dc:description.abstract

Graphs offer a way to naturally represent data from different sources, such as social networks, road networks, the web and many others. Over the last few years, a lot of these networks have grown significantly in size, requiring the development of efficient algorithms that partition the networks into smaller, easier comprehensible blocks. We develop highly efficient algorithms for the problem of finding all minimum cutsand finding all near-minimum cuts. Using several data reduction techniques, we are able to reduce a given input graph by orders of magnitude. We then implement optimized versions of some existing algorithms, which allows us to solve both problems on huge graphs in a few minutes.

Degree

thesis:*
Name thesis:degree_name
Ph. D., Operations Research and Information Engineering
Level thesis:degree_level
Doctor of Philosophy
Discipline thesis:degree_discipline
Operations Research and Information Engineering
Grantor
Cornell University
Year dc:date.issued
2024

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Ntanavaras, Sotiris
Chair dc:contributor.chair
  • Williamson, David
Committee members dc:contributor.committeemember
  • Banerjee, Siddhartha
  • Gunluk, Oktay

Rights

dc:rights
Statement dc:rights
  • Attribution 4.0 International
Language dc:language.iso
en

Identifiers

dc:identifier.*
Dc Identifier Bibid
16611968
Dc Identifier Other
ProQuest Submission ID: 14550
ProQuest Publication ID: 31487935

Chain of custody

source
Harvested from
Cornell University
Base URL
ecommons.cornell.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Ntanavaras, Sotiris. Implementations of Cut Algorithms. Doctor of Philosophy thesis, Cornell University, 2024. https://hdl.handle.net/1813/116538