Original title: Délkově omezené řezy v grafech
Translated title: Length bounded cuts in graphs
Authors: Berg, Michal ; Kolman, Petr (advisor) ; Dvořák, Pavel (referee)
Document type: Master’s theses
Year: 2019
Language: cze
Abstract: [cze] [eng]
V této práci se budeme zabývat problémem délkově omezeného řezu, nazývaného také L-omezený řez. Ukážeme kombinatorický algoritmus pro hledání minimálního L-omezeného řezu na grafech omezené stromové šířky založený na dynamickém programování. Následně také ukážeme, že se tento algoritmus dá použít i pro hledání L-omezeného řezu na rovinných grafech. Také se podíváme na problém (dG(s, t) + 1)-omezeného řezu. Je známé, že tento problém je NP-těžký na obecných grafech. Ale to, jestli je NP-těžký i na rovinných grafech se speciálními vrcholy na vnější stěně, je otevřený problém. Pokusíme se nastínit způsob, kterým bychom možná mohli ukázat, že tento problém je řešitelný v polynomiálním čase. In this thesis we will focus on a problem of length bounded cut, also known as L-bounded cut. We are going to show a combinatorial algorithm for finding a minimal L-bounded cut on graphs with bounded treewidth based on dynamic programming. Then we going to show that this algorithm can also be used for finding minimal L-bounded cut on plannar graphs. We are also going to look at problem of (dG(s, t) + 1)-bounded cut. This problem is known to be NP-hard for general graphs. But it is an open problem whether this problem is also NP-hard on plannar graphs with special vertices on the outer face. We will try to outline a way, which might lead to showing that this problem is solvable in a polynomial time.
Keywords: cut; dynamic programming; planar graph; tree width; dynamické programování; rovinný graf; stromová šířka; řez

Institution: Charles University Faculties (theses) (web)
Document availability information: Available in the Charles University Digital Repository.
Original record: http://hdl.handle.net/20.500.11956/110234

Permalink: http://www.nusl.cz/ntk/nusl-406059


The record appears in these collections:
Universities and colleges > Public universities > Charles University > Charles University Faculties (theses)
Academic theses (ETDs) > Master’s theses