Partitioning of Weighted Graphs into k Connected Subgraphs
Formulujeme a analyzujeme problém dělení vrcholově váženého grafu do k souvislých podgrafů přibližně stejné váhy za současné optimalizace funkce definované na množině možných dělení. Motivací je studium gerrymanderingu, tedy překleslování hranic volebních obvodů s cílem manipulace s volebními výsled...
Uloženo v:
| Hlavní autor: | |
|---|---|
| Další autoři: | |
| Typ dokumentu: | VŠ práce nebo rukopis |
| Jazyk: | Angličtina |
| Vydáno: |
2011
|
| Témata: | |
| On-line přístup: | http://is.muni.cz/th/273898/prif_b/ |
| Shrnutí: | Formulujeme a analyzujeme problém dělení vrcholově váženého grafu do k souvislých podgrafů přibližně stejné váhy za současné optimalizace funkce definované na množině možných dělení. Motivací je studium gerrymanderingu, tedy překleslování hranic volebních obvodů s cílem manipulace s volebními výsledky. Na datech ze skutečních voleb ilustrujeme aplikaci dělícího algoritmu jako nástroje gerrymanderingu. We formulate and analyze the problem of partitioning a vertex-weighted graph into k connected subgraphs of almost uniform size so as to optimize a function defined over the set of possible partitions. The motivation is to study gerrymandering, redrawing electoral boundaries with aim to manipulate electoral results. An illustration of a partitioning algorithm as a gerrymandering tool on real-world electoral data follows. |
|---|---|
| Popis jednotky: | Vedoucí práce: Petr Hliněný |
| Fyzický popis: | 45 l. + CD |