12 citations · 20 across the 13 of their papers we have counts for
10 papers · 1 filter
Parallel Greedy Spanners
Bernhard Haeupler, D Ellis Hershkowitz, Zihan Tan
A -spanner of a graph is a subgraph that -approximates pairwise distances. The greedy algorithm is one of the simplest and most well-studied algorithms for constructing a spa…
Almost-Optimal Sublinear Additive Spanners
Zihan Tan, Tianyi Zhang
Given an undirected unweighted graph on vertices and edges, a subgraph is a spanner of with stretch function $f: \mathbb{R}_+ \rightarrow \m…
A New Conjecture on Hardness of Low-Degree 2-CSP's with Implications to Hardness of Densest -Subgraph and Other Problems
Julia Chuzhoy, Mina Dalirrooyfard, Vadim Grinberg +1
We propose a new conjecture on hardness of low-degree -CSP's, and show that new hardness of approximation results for Densest -Subgraph and several other problems, including…
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 metric on a set of vertices along with a set of termina…
Near-Linear -Emulators for Planar Graphs
Hsien-Chih Chang, Robert Krauthgamer, Zihan Tan
We study vertex sparsification for distances, in the setting of planar graphs with distortion: Given a planar graph (with edge weights) and a subset of terminal vertices, t…
Sublinear Algorithms and Lower Bounds for Estimating MST and TSP Cost in General Metrics
Yu Chen, Sanjeev Khanna, Zihan Tan
We consider the design of sublinear space and query complexity algorithms for estimating the cost of a minimum spanning tree (MST) and the cost of a minimum traveling salesman (TSP…
A Subpolynomial Approximation Algorithm for Graph Crossing Number in Low-Degree Graphs
Julia Chuzhoy, Zihan Tan
We consider the classical Minimum Crossing Number problem: given an -vertex graph , compute a drawing of in the plane, while minimizing the number of crossings between th…
Towards Better Approximation of Graph Crossing Number
Julia Chuzhoy, Sepideh Mahabadi, Zihan Tan
Graph Crossing Number is a fundamental problem with various applications. In this problem, the goal is to draw an input graph in the plane so as to minimize the number of cross…
On Packing Low-Diameter Spanning Trees
Julia Chuzhoy, Merav Parter, Zihan Tan
Edge connectivity of a graph is one of the most fundamental graph-theoretic concepts. The celebrated tree packing theorem of Tutte and Nash-Williams from 1961 states that every …
The Expander Hierarchy and its Applications to Dynamic Graph Algorithms
Gramoz Goranci, Harald Räcke, Thatchaphol Saranurak +1
We introduce a notion for hierarchical graph clustering which we call the expander hierarchy and show a fully dynamic algorithm for maintaining such a hierarchy on a graph with …