Approximation algorithms for maximum matchings in undirected graphs - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2018

Approximation algorithms for maximum matchings in undirected graphs

Résumé

We propose heuristics for approximating the maximum cardinality matching on undirected graphs. Our heuristics are based on the theoretical body of a certain type of random graphs, and are made practical for real-life ones. The idea is based on judiciously selecting a subgraph of a given graph and obtaining a maximum cardinality matching on this subgraph. We show that the heuristics have an approximation guarantee of around 0.866 − log(n)/n for a graph with n vertices. Experiments for verifying the theoretical results in practice are provided.
Fichier principal
Vignette du fichier
undirectedGraph1out-toHal.pdf (522.49 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-01740403 , version 1 (21-03-2018)
hal-01740403 , version 2 (22-03-2018)
hal-01740403 , version 3 (29-03-2018)

Identifiants

Citer

Fanny Dufossé, Kamer Kaya, Ioannis Panagiotas, Bora Uçar. Approximation algorithms for maximum matchings in undirected graphs. CSC 2018 - SIAM Workshop on Combinatorial Scientific Computing, Jun 2018, Bergen, Norway. pp.56-65, ⟨10.1137/1.9781611975215.6⟩. ⟨hal-01740403v3⟩
415 Consultations
1863 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More