2021/08/10 by Alexander Noe, Noe, Alexander
Computer Science · Engineering · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #VLSI and FPGA Design Techniques
paper · pdf · doi:10.48550/arxiv.2108.04566
openalex publication_date 2021/08/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Graphs are a natural representation of data from various contexts, such as social connections, the web, road networks, and many more. In the last decades, many of these networks have become enormous, requiring efficient algorithms to cut networks into smaller, more readily comprehensible blocks. In this work, we aim to partition the vertices of a graph into multiple blocks while minimizing the number of edges that connect different blocks. There is a multitude of cut or partitioning problems that have been the focus of research for multiple decades. This work develops highly-efficient algorithms for the (global) minimum cut problem, the balanced graph partitioning problem and the multiterminal cut problem. All of these algorithms are efficient in practice and freely available for use.