Mediaspace scheduled maintenance: Aug 25, 2026 07:00 - 12:00 AM. During this time, videos will be temporarily unavailable. Check status updates.

Publication

Weighted Matchings via Unweighted Augmentations

Ola Nils Anders Svensson, Slobodan Mitrovic, Buddhima Ruwanmini Gamlath Gamlath Ralalage, Sagar Sudhir Kale
2019
Conference Papers

Résumé

We design a generic method to reduce the task of finding weighted matchings to that of finding short augmenting paths in unweighted graphs. This method enables us to provide efficient implementations for approximating weighted matchings in the massively parallel computation (MPC) model and in the streaming model.

Source officielle

https://infoscience.epfl.ch/entities/publication/2d69cefe-e0a7-47cb-b802-bbcb4f9470b2

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Ola Nils Anders Svensson, Slobodan Mitrovic, Buddhima Ruwanmini Gamlath Gamlath Ralalage, Sagar Sudhir Kale
2019
Conference Papers

Résumé

Source officielle

https://infoscience.epfl.ch/entities/publication/2d69cefe-e0a7-47cb-b802-bbcb4f9470b2

À propos de ce résultat

Proximité ontologique

Mathématiques

Mathématiques discrètes: Théorie des graphes

Concepts associés (32)

Couplage (théorie des graphes)

En théorie des graphes, un couplage ou appariement (en anglais matching) d'un graphe est un ensemble d'arêtes de ce graphe qui n'ont pas de sommets en commun. Soit un graphe simple non orienté G = (S, A) (où S est l'ensemble des sommets et A l'ensemble des arêtes, qui sont certaines paires de sommets), un couplage M est un ensemble d'arêtes deux à deux non adjacentes. C'est-à-dire que M est une partie de l'ensemble A des arêtes telle que Un couplage maximum est un couplage contenant le plus grand nombre possible d'arêtes.

Maximum weight matching

In computer science and graph theory, the maximum weight matching problem is the problem of finding, in a weighted graph, a matching in which the sum of weights is maximized. A special case of it is the assignment problem, in which the input is restricted to be a bipartite graph, and the matching constrained to be have cardinality that of the smaller of the two partitions. Another special case is the problem of finding a maximum cardinality matching on an unweighted graph: this corresponds to the case where all edge weights are the same.

Théorème de Kőnig (théorie des graphes)

vignette|Exemple d'un graphe biparti avec un couplage maximum (en bleu) et une couverture de sommets minimale (en rouge), tous les deux de taille 6. Le théorème de Kőnig est un résultat de théorie des graphes qui dit que, dans un graphe biparti, la taille du transversal minimum (i. e. de la couverture par sommets minimum) est égale à la taille du couplage maximum. La version pondérée du théorème est appelée théorème de Kőnig-. Un couplage d'un graphe G est un sous-ensemble d'arêtes de G deux-à-deux non adjacentes ; un sommet est couplé s'il est extrémité d'une arête du couplage.

Afficher plus

Publications associées (30)

Afficher plus

Weighted Matchings via Unweighted Augmentations

Graph Chatbot

A Distributed Augmenting Path Approach for the Bottleneck Assignment Problem

Recovering Static and Time-Varying Communities Using Persistent Edges

The Power of Two Matrices in Spectral Algorithms for Community Recovery