Bakalářská práce
Získaná ocenění: Cena děkana FI za vynikající závěrečnou práci

Implementing Robust Matching Augmentation

Tomáš Jelínek
Anotace

Cílem této práce je implementace grafového algoritmu pro problém Robust Matching Augmentation s jednotkovým ohodnocením hran navržený autory Hommelsheim, Mühlenthaler a Schaudt. Úkolem je přidat do bipartitního grafu co nejméně hran tak, aby existovalo perfektní párování i poté, co protivník odebere libovolnou hranu. Rozebereme nezbytné algoritmické základy a navrhneme efektivní implementaci tohoto …více

Abstract

The goal of the thesis is to implement a graph algorithm for the unit-cost Robust Matching Augmentation problem due to Hommelsheim, Mühlenthaler, and Schaudt. The task is to add to a bipartite graph as few edges as possible in order to ensure that the graph admits a perfect matching even after an adversary removes an arbitrary edge. We provide the necessary algorithmic foundations and propose an …více

Klíčová slova
graph algorithms matchings in graphs approximation algorithms bipartite graphs
Zadání práce
The goal of the thesis is to implement the algorithm for Robust Matching Augmentation problem due to Hommelsheim, Mühlenthaler, and Schaudt. The thesis should provide a discussion of the algorithmic implementation of the algorithm, including any auxiliary algorithms. The main outcome of the thesis is a practical implementation of the algorithm, using some suitable graph algorithms library. The implementation should also be accompanied by a set of functionality tests. The implementation is expected to reflect the specifics of the chosen library and programming language.
Administrativní informace
Práce zkontrolována:
16. 12. 2019 11:03, doc. Mgr. Jan Obdržálek, PhD., učo 1552
Plný text práce
412 KB / soubor PDF
Přílohy (1)
Jazyk práce
angličtina angličtina
Termín obhajoby
13. 2. 2020
Práce byla úspěšně obhájena

Vedoucí

doc. Mgr. Jan Obdržálek, PhD., učo 1552
KTP FI MU

Oponent

prof. RNDr. Ivana Černá, CSc., učo 1419
KTP FI MU

Literatura

  • HOMMELSHEIM, Felix; Moritz MÜHLENTHALER a Oliver SCHAUDT. How to Secure Matchings Against Edge Failures. Leibniz International Proceedings in Informatics (LIPIcs). Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2019, roč. 126, s. 38:1--38:16. Dostupné z: https://doi.org/10.4230/LIPIcs.STACS.2019.38.
Citovat tuto práci
Masarykova univerzita Fakulta informatiky
Studijní program
Informatika
Obor

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

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

  • 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.