Fast Algorithms for Maximal Matching Approximation

Student: Daniliuk Aleksei

Supervisor: Gleb Olegovich Evstropov

Educational Programme: Applied Mathematics and Information Science (Bachelor)

Year of Graduation: 2019

A matching in a graph is a subset of edges such that no two edges are adjacent. The problem of finding a maximum matching in a graph is well studied, and polynomial-time algorithms are known for both bipartite and general case. However, for large graphs such as social network graph of friends these algorithms might be too slow. Real-life problems often require only an approximation of the maximum matching. This research aims to study existing and develop new faster ways to construct matchings that are almost maximum. We have constructed linear-time approximation algorithms for maximal matching with approximation factor of 2/3 for general case and 1-\varepsilon for bipartite case. Index terms — graph, matching, approximation

Student Theses at HSE must be completed in accordance with the University Rules and regulations specified by each educational programme.

Summaries of all theses must be published and made freely available on the HSE website.

The full text of a thesis can be published in open access on the HSE website only if the authoring student (copyright holder) agrees, or, if the thesis was written by a team of students, if all the co-authors (copyright holders) agree. After a thesis is published on the HSE website, it obtains the status of an online publication.

Student theses are objects of copyright and their use is subject to limitations in accordance with the Russian Federation’s law on intellectual property.

In the event that a thesis is quoted or otherwise used, reference to the author’s name and the source of quotation is required.

Search all student theses