3 papers
cs.DS2020
A Scaling Algorithm for Weighted -Factors in General Graphs
Ran Duan, Haoqing He, Tianyi Zhang
We study the maximum weight perfect -factor problem on any general simple graph with positive integral edge weights , and , . When we have a functio…
cs.DS2019
Fully Dynamic Maximal Independent Set in Expected Poly-Log Update Time
Shiri Chechik, Tianyi Zhang
In the fully dynamic maximal independent set (MIS) problem our goal is to maintain an MIS in a given graph while edges are inserted and deleted from the graph. The first non-tr…
cs.DS2016
Improved distance sensitivity oracles via tree partitioning
Ran Duan, Tianyi Zhang
We introduce an improved structure of distance sensitivity oracle (DSO). The task is to pre-process a non-negatively weighted graph so that a data structure can quickly answer repl…