Original title: Toky a cesty s omezením
Translated title: Flows and cuts with restriction
Authors: Knop, Dušan ; Kolman, Petr (advisor) ; Krčál, Marek (referee)
Document type: Master’s theses
Year: 2012
Language: cze
Abstract: [cze] [eng]
Název práce: Toky a cesty s omezením Autor: Dušan Knop Katedra: Katedra aplikované matematiky Vedoucí diplomové práce: Doc. Mgr. Petr Kolman, PhD, Katedra aplikované matematiky Abstrakt: V předložené práci studujeme problém délkou omezených řezů mezi dvojicí vr- cholů grafu. V tomto problému je cílem odebrat hrany z grafu tak, aby po jejich odebrání měla předem specifikovaná dvojice vrcholů předepsanou vzdálenost. Práce poskytuje přehled o základní literatuře o tomto problému a prezentuje souvislosti s jinými problémy. V rámci tohoto také nabízí mnoho aplikací délkou omezených toků a řezů. Pro tento NP-těžký problém popisuje heuristiky pro redukci dat. Hlavním výsledkem práce pak je polynomiální algoritmus pro sériově-paralelní grafy. Klíčová slova: řezy, sériově-paralelní grafy, algoritmus, složitost Title: Flows and cuts with constraints Author: Dušan Knop Department: Department of applied mathematics Supervisor: Doc. Mgr. Petr Kolman, PhD, Department of applied mathematics Abstract: In this thesis we study the problem of length bounded cuts between two vertices of a graph. In this problem the task is to find a set of edges such that after its removal the minimal distance between the two vertices is as prescribed. The work provides a basic overview of the literature on this problem and presents it in the context of other theoretical problems. It also offers some applications of length bounded cuts and flows. We describe some heuristics for data reduction. The main result of this thesis is a polynomial time algorithm in series-parallel graphs for problem of length bounded cut, which is NP-hard in general. Keywords: cuts, series-parallel graphs, algorithm, complexity
Keywords: algorithm; complexity; cut; series-parallel graphs; algoritmus; složitost; sériově-paralelní grafy; ř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/40785

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


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