57 citations · 245 across the 48 of their papers we have counts for
Showing 2017 · cs.DSShow all
2 papers · 2 filters
cs.DS2017
Fully Dynamic Almost-Maximal Matching: Breaking the Polynomial Barrier for Worst-Case Time Bounds
Moses Charikar, Shay Solomon
Despite significant research efforts, the state-of-the-art algorithm for maintaining an approximate matching in fully dynamic graphs has a polynomial {worst-case} update time, even…
cs.DS2017
Local Guarantees in Graph Cuts and Clustering
Moses Charikar, Neha Gupta, Roy Schwartz
Correlation Clustering is an elegant model that captures fundamental graph cut problems such as Min Cut, Multiway Cut, and Multicut, extensively studied in combinatorial opti…