4 papers
Faster Deterministic Streaming Vertex Coloring
Shiri Chechik, Hongyi Chen, Tianyi Zhang
Graph coloring is a fundamental problem in computer science. In the semi-streaming model, an input graph on vertices and maximum degree is presented as a stream of edge…
Paths and Intersections: Exact Emulators for Planar Graphs
George Z. Li, Zihan Tan, Tianyi Zhang
We study vertex sparsification for preserving distances in planar graphs. Given an edge-weighted planar graph with terminals, the goal is to construct an emulator, which is a s…
Improved Streaming Edge Coloring
Shiri Chechik, Hongyi Chen, Tianyi Zhang
Given a graph, an edge coloring assigns colors to edges so that no pairs of adjacent edges share the same color. We are interested in edge coloring algorithms under the W-streaming…
Faster Algorithms for Dual-Failure Replacement Paths
Shiri Chechik, Tianyi Zhang
Given a simple weighted directed graph on vertices as well as two designated terminals , our goal is to compute the shortest path from to avo…