Maximum Matching in Two, Three, and a Few More Passes Over Graph Streams

Last updated 27th Jul 2017
Follow pinboard

CURATOR

A pinboard by Sumedh Tirodkar

Post Doctoral Fellow, School of Technology and Computer Science, Tata Institute of Fundamental Research, Mumbai, India

PINBOARD SUMMARY

Maximum Matching on graphs in the semi-streaming model

Maximum Matching in simple undirected graphs is a subset of maximum number of edges such that at most one edge is incident on any vertex. We study this problem in the semi-streaming model, in which...

4 ITEMS PINNED

#1
Online Weighted Matching: Beating the $\frac{1}{2}$ Barrier
Research published 18th Apr 2017 in arXiv - Com...
Pinned 27th Jul 2017
#2
The Stochastic Matching Problem: Beating Half with a Non-Adaptive Algorithm
Research published 5th May 2017 in arXiv - Comp...
Pinned 27th Jul 2017
#3
Fully Dynamic Approximate Maximum Matching and Minimum Vertex Cover in $O(\log^3 n)$ Worst Case Update Time
Research published 10th Apr 2017 in arXiv - Com...
Pinned 27th Jul 2017
#4
Online bipartite matching with amortized $O(\log^2 n)$ replacements
Research published 19th Jul 2017 in arXiv - Com...
Pinned 27th Jul 2017
Followers (0)
Share
Pinboard URL (click to copy)
Embed on website (click to copy)