3 papers
cs.DS2026
Nearly Optimal Sparse Navigable Graphs in General Metrics
Hongyi Chen, Tianyi Zhang
We study approximation algorithms for constructing sparse navigable graphs in general metrics. Given an -point metric and a parameter , a directed graph on is…
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 edge…
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…