TU Berlin

Algorithmics and Computational Complexity Research GroupTalk 11.07.2019

isti-logo

Page Content

to Navigation

Popular Matchings in Complete Graphs

Ágnes Cseh (Hungarian Academy of Sciences)

 

Our input is a complete graph G=(V,E) on n vertices where each vertex has a strict ranking of all other vertices in G. Our goal is to construct a matching in G that is popular. A matching M is popular if M does not lose a head-to-head election against any matching M′, where each vertex casts a vote for the matching in {M,M′} where it gets assigned a better partner. The popular matching problem is to decide whether a popular matching exists or not. The popular matching problem in G is easy to solve for odd n. Surprisingly, the problem becomes NP-hard for even n, as we show in our paper. Joint work with T. Kavitha, appeared at FSTTCS'18.

 

Date
Speaker
Location
Language
11.07.2019
16:15
Ágnes Cseh
TEL 512
English

Back to the research colloquium site.

To top

Navigation

Quick Access

Schnellnavigation zur Seite über Nummerneingabe