Yu Chen

collaborators

Showing cs.DSShow all

2 papers · 1 filter

cs.DS2024

Query Complexity of the Metric Steiner Tree Problem

Yu Chen, Sanjeev Khanna, Zihan Tan

We study the query complexity of the metric Steiner Tree problem, where we are given an $n \times n$ metric on a set $V$ of vertices along with a set $T \subseteq V$ of $k$ termina…

cs.DS2024

On the Streaming Complexity of Expander Decomposition

Yu Chen, Michael Kapralov, Mikhail Makarov +1

In this paper we study the problem of finding $(I^µ, I ¨ )$ -expander decompositions of a graph in the streaming model, in particular for dynamic streams of edge insertions and deletio…