Controllability and matchings in random bipartite graphs. / Balister, Paul; Gerke, Stefanie.

Surveys in Combinatorics 2015. ed. / Artur Czumaj; Agelos Georgakopoulos; Daniel Král; Vadim Lozin; Oleg Pikhurko. Vol. 424 Cambridge University Press, 2015. p. 119-146 (London Mathematical Society Lecture Note Series; Vol. 424).

Research output: Chapter in Book/Report/Conference proceedingChapter

Published

Abstract

Motivated by an application in controllability we consider maximum matchings in random bipartite graphs G = (A, B). First we analyse Karp–Sipser's algorithm to determine the asymptotic size of maximum matchings in random bipartite graphs with a fixed degree distribution. We then allow an adversary to delete one edge adjacent to every vertex in A in the more restricted model where each vertex in A chooses d neighbours uniformly at random from B.
Original languageEnglish
Title of host publicationSurveys in Combinatorics 2015
EditorsArtur Czumaj, Agelos Georgakopoulos, Daniel Král, Vadim Lozin, Oleg Pikhurko
PublisherCambridge University Press
Chapter3
Pages119-146
Number of pages28
Volume424
ISBN (Electronic)9781316106853
DOIs
Publication statusPublished - Jul 2015

Publication series

NameLondon Mathematical Society Lecture Note Series
Volume424
This open access research output is licenced under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.

ID: 28895882