Bakalářská práce

Efektivní generování všech malých mnohočetných řezů

Efficient exhaustive generation of small multiway cuts

Ondřej Slámečka
Anotace

Zabýváme se problémem generování všech minimálních mnohočetných řezů do zadaného počtu hran ve velkém, ale řídkém grafu. Je podán podrobný popis nově navrhnutého "circuit-cocircuit" algoritmu a jeho úpravy pro téměř kanonické generování řezů, založené na technice generování kanonickou konstrukční cestou. Součástí práce je implementace tohoto algoritmu v podobě počítačového programu a vyhodnocení jeho …více

Abstract

Given a large but sparse graph the problem is to generate all minimal multiway edge-cuts up to a certain number of edges. We present a detailed description of a newly proposed "circuit-cocircuit" algorithm and its modification for almost canonical generation of cuts, based on the technique of generation by canonical construction path. We provide an implementation of the algorithm in a computer program …více

Zadání práce
Given a large but rather sparse graph (of a road network, say), the task is to efficiently generate all existing minimal multiway edge-cuts up to a certain number of edges. The student will implement and experimentally evaluate a new "circuit-cocircuit" algorithm (proposed by the advisor, unpublished) for this problem. Special attention will be paid to a practically fast implementation, and to so called canonical generation of the cuts (i.e., without repetition, achieved by observing certain unique canonical order for all the cuts).
Práce zkontrolována:
25. 5. 2015 11:19, prof. RNDr. Petr Hliněný, Ph.D., učo 168881
Jazyk práce
angličtina angličtina
Termín obhajoby
17. 6. 2015
Práce byla úspěšně obhájena

Vedoucí

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

Oponent

Mgr. Michal Kotrbčík, Ph.D.

Masarykova univerzita Fakulta informatiky
Studijní program
Aplikovaná informatika

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

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

 
Název
Vložil
Vloženo
Práva
  • 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.