Breaking the Cubic Barrier for All-Pairs Max-Flow: Gomory-Hu Tree in Nearly Quadratic Time

Amir Abboud, Robert Krauthgamer, Jason Li, Debmalya Panigrahi, Thatchaphol Saranurak, Ohad Trabelsi

Type: Preprint

Publication Date: 2021-01-01

Citations: 0

DOI: https://doi.org/10.48550/arxiv.2111.04958

View Publication

Locations

arXiv (Cornell University) - View
DataCite API - View

Similar Works

Action	Title	Year	Authors
+ PDF Chat	Breaking the Cubic Barrier for All-Pairs Max-Flow: Gomory-Hu Tree in Nearly Quadratic Time	2022	Amir Abboud Robert Krauthgamer Jason Li Debmalya Panigrahi Thatchaphol Saranurak Ohad Trabelsi
+ PDF Chat	New Algorithms and Lower Bounds for All-Pairs Max-Flow in Undirected Graphs	2019	Amir Abbou Robert Krauthgamer Ohad Trabelsi
+	APMF < APSP? Gomory-Hu Tree for Unweighted Graphs in Almost-Quadratic Time	2021	Amir Abboud Robert Krauthgamer Ohad Trabelsi
+	APMF < APSP? Gomory-Hu Tree for Unweighted Graphs in Almost-Quadratic Time.	2021	Amir Abboud Robert Krauthgamer Ohad Trabelsi
+	New Algorithms and Lower Bounds for All-Pairs Max-Flow in Undirected Graphs	2019	Amir Abboud Robert Krauthgamer Ohad Trabelsi
+	New Algorithms and Lower Bounds for All-Pairs Max-Flow in Undirected Graphs	2019	Amir Abboud Robert Krauthgamer Ohad Trabelsi
+	A Nearly Optimal All-Pairs Min-Cuts Algorithm in Simple Graphs	2021	Jason Li Debmalya Panigrahi Thatchaphol Saranurak
+ PDF Chat	A Nearly Optimal All-Pairs Min-Cuts Algorithm in Simple Graphs	2022	Jason Li Debmalya Panigrahi Thatchaphol Saranurak
+	Gomory-Hu Tree in Subcubic Time	2021	Amir Abboud Robert Krauthgamer Jason Li Debmalya Panigrahi Thatchaphol Saranurak Ohad Trabelsi
+	Subcubic Algorithms for Gomory-Hu Tree in Unweighted Graphs	2020	Amir Abboud Robert Krauthgamer Ohad Trabelsi
+	Subcubic Algorithms for Gomory-Hu Tree in Unweighted Graphs	2020	Amir Abboud Robert Krauthgamer Ohad Trabelsi
+	(Almost) Ruling Out SETH Lower Bounds for All-Pairs Max-Flow	2023	Ohad Trabelsi
+	Gomory-Hu Trees in Quadratic Time	2021	Tianyi Zhang
+ PDF Chat	Gomory-Hu Trees in Quadratic Time	2021	Tianyi Zhang
+	Faster Cut-Equivalent Trees in Simple Graphs	2021	Tianyi Zhang
+	Approximate Gomory-Hu Tree Is Faster Than $n-1$ Max-Flows	2021	Jason Li Debmalya Panigrahi
+	A Local-to-Global Theorem for Congested Shortest Paths	2022	Shyan Akmal Nicole Wein
+ PDF Chat	A Simple Framework for Finding Balanced Sparse Cuts via APSP	2023	Li Chen Rasmus Kyng Maximilian Probst Gutenberg Sushant Sachdeva
+	Vertex Connectivity in Poly-logarithmic Max-flows	2021	Jason Li Danupon Nanongkai Debmalya Panigrahi Thatchaphol Saranurak Sorrachai Yingchareonthawornchai
+	An Efficient Algorithm for All-Pairs Bounded Edge Connectivity	2023	Shyan Akmal Ce Jin

Works That Cite This (0)

Action	Title	Year	Authors

Works Cited by This (0)

Action	Title	Year	Authors