6 citations · 8 across the 5 of their papers we have counts for
6 papers · 1 filter
Combinatorial Maximum Flow via Weighted Push-Relabel on Shortcut Graphs
Aaron Bernstein, Joakim Blikstad, Jason Li +2
We give a combinatorial algorithm for computing exact maximum flows in directed graphs with vertices and edge capacities from in time,…
All-Subsets Important Separators with Applications to Sample Sets, Balanced Separators and Vertex Sparsifiers in Directed Graphs
Aditya Anand, Euiwoong Lee, Jason Li +1
Given a directed graph with vertices and edges, a parameter and two disjoint subsets , we show that the number of all-subsets important separato…
Unbreakable Decomposition in Close-to-Linear Time
Aditya Anand, Euiwoong Lee, Jason Li +2
Unbreakable decomposition, introduced by Cygan et al. (SICOMP'19) and Cygan et al. (TALG'20), has proven to be one of the most powerful tools for parameterized graph cut problems i…
Low-Step Multi-Commodity Flow Emulators
Bernhard Haeupler, D Ellis Hershkowitz, Jason Li +2
We introduce the concept of low-step multi-commodity flow emulators for any undirected, capacitated graph. At a high level, these emulators contain approximate multi-commodity flow…
Hypergraph Unreliability in Quasi-Polynomial Time
Ruoxu Cen, Jason Li, Debmalya Panigrahi
The hypergraph unreliability problem asks for the probability that a hypergraph gets disconnected when every hyperedge fails independently with a given probability. For graphs, the…
Approximating Small Sparse Cuts
Aditya Anand, Euiwoong Lee, Jason Li +1
We study polynomial-time approximation algorithms for (edge/vertex) Sparsest Cut and Small Set Expansion in terms of , the number of edges or vertices cut in the optimal solutio…