-
Uddannelse
Find uddannelse
Studievejledning
Kvalitet
- Forskning
-
Samarbejde
Virksomheder
Kommuner og regioner
Gymnasier
Myndigheder
-
Om AU
Organisation
Kontakt
Om AU
- Organisation
- Ledelse
- Strategi
- AU i tal
- AU's historie
- Internationalt samarbejde
- Bæredygtighed
- Campus 2.0
- Diversitet og ligestilling
- Ledige stillinger
- Presse
- Kontakt
Nash Stability in Additively Separable Hedonic Games and Community Structures
Publikation: Bidrag til tidsskrift/Konferencebidrag i tidsskrift /Bidrag til avis › Tidsskriftartikel › Forskning › peer review
- Datalogisk Institut
We prove that the problem of deciding whether a Nash stable
partition exists in an Additively Separable Hedonic Game is
NP-complete. We also show that the problem of deciding whether a
non trivial Nash stable partition exists in an
Additively Separable Hedonic Game with
non-negative and symmetric
preferences is NP-complete. We motivate our study of the
computational complexity by linking Nash stable partitions in
Additively Separable Hedonic Games to community structures in
networks. Our results formally justify that computing community
structures in general is hard.
partition exists in an Additively Separable Hedonic Game is
NP-complete. We also show that the problem of deciding whether a
non trivial Nash stable partition exists in an
Additively Separable Hedonic Game with
non-negative and symmetric
preferences is NP-complete. We motivate our study of the
computational complexity by linking Nash stable partitions in
Additively Separable Hedonic Games to community structures in
networks. Our results formally justify that computing community
structures in general is hard.
| Originalsprog | Engelsk |
|---|---|
| Tidsskrift | Theory of Computing Systems |
| Vol/bind | 45 |
| Nummer | 4 |
| Sider (fra-til) | 917-925 |
| Antal sider | 9 |
| ISSN | 1432-4350 |
| DOI | |
| Status | Udgivet - 2009 |
Se relationer på Aarhus Universitet Citationsformater
ID: 16095577