3 papers
cs.DS2026
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 edg…
cs.DS2025
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…
cs.DS2025
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…