5 papers
Improved Space-Time Tradeoffs for Permutation Problems via Extremal Combinatorics
Afrouz Jabal Ameli, Jesper Nederlof, Shengzhe Wang
We provide improved space-time tradeoffs for permutation problems over additively idempotent semi-rings. In particular, there is an algorithm for the Traveling Salesperson Problem…
New Parameterized and Exact Exponential Time Algorithms for Strongly Connected Steiner Subgraph
Afrouz Jabal Ameli, Tomohiro Koana, Jesper Nederlof +1
The Strongly Connected Steiner Subgraph (SCSS) problem is a well-studied network design problem that asks for a minimum subgraph that strongly connects a given set of terminals. In…
Stronger Directed Low-Diameter Decompositions with Sub-Logarithmic Diameter and Separation
Bernhard Haeupler, Richard HladÃk, Shengzhe Wang +1
This paper significantly strengthens directed low-diameter decompositions in several ways. We define and give the first results for separated low-diameter decompositions in directe…
Parallel -Approximate Multi-Commodity Mincost Flow in Almost Optimal Depth and Work
Bernhard Haeupler, Yonggang Jiang, Yaowei Long +2
We present a parallel algorithm for computing -approximate mincost flow on an undirected graph with edges, where capacities and costs are assigned to both edges and ver…
Length-Constrained Directed Expander Decomposition and Length-Constrained Vertex-Capacitated Flow Shortcuts
Bernhard Haeupler, Yaowei Long, Thatchaphol Saranurak +1
We show the existence of length-constrained expander decomposition in directed graphs and undirected vertex-capacitated graphs. Previously, its existence was shown only in undirect…