Bakalářská práce

Partitioning of Weighted Graphs into k Connected Subgraphs

Jozef Janovský, učo 273898
Anotace

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.

Abstract

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.

Klíčová slova
teorie grafů členění grafů balans spojitost gerrymandering graph theory graph partitioning balance connectivity
Zadání práce
Student will 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. An illustration of a partitioning algorithm as a gerrymandering tool on real-world electoral data will follow.
  • Assuncao, T. 2008. “A Heuristic Method for Balanced Graph Partitioning: An Application for the Demarcation of Preventive Police Patrol Areas.” Lecture notes in computer science. (5290): 62-72.
  • Ito, Takehiro, Xiao Zhou, and Takao Nishizeki. 2004. “Partitioning a Weighted Graph to Connected Subgraphs of Almost Uniform Size.” Lecture notes in computer science. (3353): 365-376.
  • Karypis, G. 2001. “Multilevel k-way Hypergraph Partitioning.” VLSI DESIGN-LANGHORNE- 11: 285-300.
  • Kernighan, B. W. - Lin, Shen. 1970. "An efficient heuristic procedure for partitioning graphs". Bell Systems Technical Journal 49: 291-307.
Administrativní informace
Práce zkontrolována:
6. 6. 2011 08:34, prof. RNDr. Petr Hliněný, Ph.D., učo 168881
Plný text práce
8,7 MB / soubor PDF
Jazyk práce
angličtina angličtina
Termín obhajoby
28. 6. 2011
Práce byla úspěšně obhájena

Vedoucí

prof. RNDr. Petr Hliněný, Ph.D., učo 168881
KTP FI MU

Oponent

Mgr. Radek Šlesinger, Ph.D.
Citovat tuto práci
Masarykova univerzita Přírodovědecká fakulta
Studijní program
Aplikovaná matematika
Obor

Práce na příbuzné téma

Seznam prací, které mají shodná klíčová slova.

Podobné práce
 
Název
Vložil
Vloženo
Práva
Archiv závěrečné práce Jozef Janovský PřF B-AM STAT, učo 273898 hnfgt/6
Janovský, J.
3. 6. 2011
Složky
Soubory
Anotace anglicky annotation_english.txt
Janovský, J.
3. 6. 2011
Anotace česky annotation.txt
Janovský, J.
3. 6. 2011
Klíčová slova keywords.txt
Janovský, J.
3. 6. 2011
Plný text práce bakalarka.pdf
Janovský, J.
3. 6. 2011
Posudek oponenta janovsky-oponent.pdf
Šlesinger, R.
25. 6. 2011

  • Přidání souboru

    Soubor nebo složku lze nahrát pomocí tlačítka Přidat.

  • Další operace se soubory

    Podrobnosti lze zjistit označením příslušného řádku.

  • Pohled pro experty

    Pro častou práci je možné zvolit režim Více možností.

  • Vyhledávání souborů

    Vyhledávaný výraz můžete zadat přímo do adresního řádku.

  • Rychlý přístup k souborům

    Pomocí funkce Nedávné je možné se rychle vrátit k právě prohlíženým souborům. Oblíbené soubory je také možné označit Hvězdičkou.