6 papers · 1 filter
Paths and Intersections: Recognizing Outerplanar Metrics
Yu Chen, Zihan Tan
We study the following distance realization problem: given a metric on a set of terminals, does there exist an (edge-weighted) outerplanar graph , such that $T\subseteq…
Paths and Intersections: Minimum Realization of Okamura-Seymour Instances
Yu Chen, Pavlo Pylyavskyy, Zihan Tan
We study the inverse problem for shortest-path metrics of Okamura-Seymour (OS) instances. Given an OS metric on a cyclically ordered terminal set , the goal is to find minim…
Lower Bounds on Flow Sparsifiers with Steiner Nodes
Yu Chen, Zihan Tan, Mingyang Yang
Given a large graph with a set of its vertices called terminals, a \emph{quality- flow sparsifier} is a small graph that contains the terminals and preserves all mu…
Lower Bounds on Tree Covers
Yu Chen, Zihan Tan, Hangyu Xu
Given an -point metric space , a tree cover is a set of trees on such that every pair of vertices in has a low-distortion path i…
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 on a set of terminals, does there exist a directed Okamura-Seymour graph that realizes as the…
Cut-Preserving Vertex Sparsifiers for Planar and Quasi-bipartite Graphs
Yu Chen, Zihan Tan
We study vertex sparsification for preserving cuts. Given a graph with a subset of its vertices called terminals, a \emph{quality- cut sparsifier} is a graph th…