Class Central is learner-supported. When you buy through links on our site, we may earn an affiliate commission.

YouTube

Maximal Matching in Bounded-deletion Streams

Simons Institute via YouTube

Overview

Save Big on Coursera Plus. 7,000+ courses at $160 off. Limited Time Only!
Explore the intricacies of maximal matching in bounded-deletion graph streams through this 38-minute lecture by Christian Konrad from the University of Bristol, UK. Delve into the study of graphs revealed as sequences of edge insertions and deletions, with a focus on scenarios where deletions are limited to a parameter K. Examine the single-pass streaming space complexity of this problem, known to be Θ(n^2) for unrestricted K, where n represents the number of vertices. Discover a new algorithm and matching lower bound result that provide a comprehensive understanding of how space complexity evolves as a function of K. Gain insights into sublinear graph simplification techniques and their applications in this Simons Institute presentation.

Syllabus

Maximal Matching in Bounded-deletion Streams

Taught by

Simons Institute

Reviews

Start your review of Maximal Matching in Bounded-deletion Streams

Never Stop Learning.

Get personalized course recommendations, track subjects and courses with reminders, and more.

Someone learning on their laptop while sitting on the floor.