4 papers
Packing Compact Subgraphs with Applications to Districting
Ho-Lin Chen, Po-Yu Chou, Prathamesh Dharangutte +3
Packing disjoint subgraphs in a given graph is a fundamental problem with many applications. Motivated by political districting, we focus on connected subgraphs that are compact (e…
Disjoint Paths in Expanders in Deterministic Almost-Linear Time via Hypergraph Perfect Matching
Matija Bucić, Zhongtian He, Shang-En Huang +1
We design efficient deterministic algorithms for finding short edge-disjoint paths in expanders. Specifically, given an -vertex -edge expander of conductance and mini…
Cactus Representation of Minimum Cuts: Derandomize and Speed up
Zhongtian He, Shang-En Huang, Thatchaphol Saranurak
Given an undirected weighted graph with vertices and edges, we give the first deterministic -time algorithm for constructing the cactus representation of \emph{…
Cactus Representations in Polylogarithmic Max-flow via Maximal Isolating Mincuts
Zhongtian He, Shang-En Huang, Thatchaphol Saranurak
A cactus representation of a graph, introduced by Dinitz et al. in 1976, is an edge sparsifier of size that exactly captures all global minimum cuts of the graph. It is a ce…