Author

Thatchaphol Saranurak

3 papers indexed here

We haven’t gathered this author’s papers yet. Follow them and we’ll fetch their work.

Not the right person? Other researchers publish under this name.

Preprint Oct 2026

Directed Global Minimum Cut in Almost-Linear Time

We give a randomized reduction from global minimum cut in a directed graph with $n$ vertices and $m$ weighted edges to maximum-flow computations on graphs of total size $\widetilde{O}(m)$. For polynomially bounded integral weights, this yields the first almost-linear $m^{1+o(1)}$-time algorithm [vdBCK+23], improving th...

Henry L. Fleischmann, Jason Li, Thatchaphol Saranurak et al. · 1 citation

Preprint Sep 2026

Connectivity Oracles Under Vertex Failures via a Simple and Fast Low-Degree Steiner Forest Decomposition

We study the low-degree Steiner forest decomposition. Given a graph $G=(V,E)$ and a terminal set $U\subseteq V$, the standard decomposition returns a set $X\subseteq V$ of size at most $|U|/2$ and a forest $T\subseteq G-X$ of maximum degree $\Delta$ such that, for every connected component $C$ of $G-X$, some connected...

Sayan Bhattacharya, Ermiya Farokhnejad, Thatchaphol Saranurak et al. · 0 citations

#edge computing Preprint Sep 2026

Deterministic Edge-Fault-Tolerant Connectivity Labeling Schemes with Nearly Optimal Label Size

This paper presents a labeling scheme that uses $O(\log^{2}n)$-bit labels that can be computed in deterministic polynomial time and is the first labeling scheme that produces an $\tilde{O}(1)$-size labeling which is simultaneously correct across all queries.

Yao-Wei Long, Seth Pettie, Thatchaphol Saranurak · 0 citations