Computing large matchings fast

I. Rutter, A. Wolff

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

2 Citations (Scopus)

Abstract

In this paper we present algorithms for computing large matchings in 3-regular graphs, graphs with maximum degree 3, and 3-connected planar graphs. The algorithms give a guarantee on the size of the computed matching and take linear or slightly superlinear time. Thus they are faster than the best-known algorithm for computing maximum matchings in general graphs, which runs in O(vnm) time, where n denotes the number of vertices and m the number of edges of the given graph. For the classes of 3-regular graphs and graphs with maximum degree 3 the bounds we achieve are known to be best possible. We also investigate graphs with block trees of bounded degree, where the d-block tree is the adjacency graph of the d-connected components of the given graph. In 3-regular graphs and 3-connected planar graphs with bounded-degree 2- and 4-block trees, respectively, we show how to compute maximum matchings in slightly superlinear time.
Original languageEnglish
Title of host publicationProceedings 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'08, San Francisco CA, USA, January 20-22, 2008)
EditorsS.T. Huang
Place of PublicationPhiladelphia PA
PublisherSociety for Industrial and Applied Mathematics (SIAM)
Pages183-192
Publication statusPublished - 2008

Fingerprint Dive into the research topics of 'Computing large matchings fast'. Together they form a unique fingerprint.

Cite this