Zihan Tan

activity

20232026

most citedOn

(1 + ε)

-Approximate Flow Sparsifiers

1 citations · 1 across the 9 of their papers we have counts for

collaborators

Showing cs.DSShow all

10 papers · 1 filter

cs.DS2026

Paths and Intersections: Repelling Pairs

Yu Chen, Pavlo Pylyavskyy, Zihan Tan

We study two inverse problems for shortest-path metrics of Okamura-Seymour instances: recognizing metrics realizable by outerplanar graphs, and computing minimum-edge Okamura-Seymo…

cs.DS2026

Paths and Intersections: Recognizing Outerplanar Metrics

Yu Chen, Zihan Tan

We study the following distance realization problem: given a metric $D$ on a set $T$ of terminals, does there exist an (edge-weighted) outerplanar graph $G$ , such that $T\subseteq…

cs.DS2026

Lower Bounds on Flow Sparsifiers with Steiner Nodes

Yu Chen, Zihan Tan, Mingyang Yang

Given a large graph $G$ with a set of its $k$ vertices called terminals, a \emph{quality- $q$ flow sparsifier} is a small graph $G^{'}$ that contains the terminals and preserves all mu…

cs.DS2025

Lower Bounds on Tree Covers

Yu Chen, Zihan Tan, Hangyu Xu

Given an $n$ -point metric space $(X, d_{X})$ , a tree cover $T$ is a set of $∣ T ∣ = k$ trees on $X$ such that every pair of vertices in $X$ has a low-distortion path i…

cs.DS2024

Paths and Intersections: Characterization of Quasi-metrics in Directed Okamura-Seymour Instances

Yu Chen, Zihan Tan

We study the following distance realization problem. Given a quasi-metric $D$ on a set $T$ of terminals, does there exist a directed Okamura-Seymour graph that realizes $D$ as the…

cs.DS2024

Cut-Preserving Vertex Sparsifiers for Planar and Quasi-bipartite Graphs

Yu Chen, Zihan Tan

We study vertex sparsification for preserving cuts. Given a graph $G$ with a subset $∣ T ∣ = k$ of its vertices called terminals, a \emph{quality- $q$ cut sparsifier} is a graph $G^{'}$ th…

cs.DS2024

Lower Bounds on $0$ -Extension with Steiner Nodes

Yu Chen, Zihan Tan

In the $0$ -Extension problem, we are given an edge-weighted graph $G = (V, E, c)$ , a set $T \subseteq V$ of its vertices called terminals, and a semi-metric $D$ over $T$ , and the goal i…

cs.DS2023

An $Ω ~ (lo g ∣ T ∣)$ Lower Bound for Steiner Point Removal

Yu Chen, Zihan Tan

In the Steiner point removal (SPR) problem, we are given a (weighted) graph $G$ and a subset $T$ of its vertices called terminals, and the goal is to compute a (weighted) graph $H$ …

cs.DS2023★ 1 cited

On $(1 + ε)$ -Approximate Flow Sparsifiers

Yu Chen, Zihan Tan

Given a large graph $G$ with a subset $∣ T ∣ = k$ of its vertices called terminals, a quality- $q$ flow sparsifier is a small graph $G^{'}$ that contains $T$ and preserves all multicommodi…

cs.DS2023

Towards the Characterization of Terminal Cut Functions: a Condition for Laminar Families

Yu Chen, Zihan Tan

We study the following characterization problem. Given a set $T$ of terminals and a $(2^{∣ T ∣} - 2)$ -dimensional vector $π$ whose coordinates are indexed by proper subsets of $T$ , is…

Paths and Intersections: Repelling Pairs

Paths and Intersections: Recognizing Outerplanar Metrics

Lower Bounds on Flow Sparsifiers with Steiner Nodes

Lower Bounds on Tree Covers

Paths and Intersections: Characterization of Quasi-metrics in Directed Okamura-Seymour Instances

Cut-Preserving Vertex Sparsifiers for Planar and Quasi-bipartite Graphs

Lower Bounds on 0-Extension with Steiner Nodes

An Ω~(log∣T∣​) Lower Bound for Steiner Point Removal

On (1+ε)-Approximate Flow Sparsifiers

Towards the Characterization of Terminal Cut Functions: a Condition for Laminar Families

Lower Bounds on $0$ -Extension with Steiner Nodes

An $Ω ~ (lo g ∣ T ∣)$ Lower Bound for Steiner Point Removal

On $(1 + ε)$ -Approximate Flow Sparsifiers