Název: Toky a cesty s omezením
Překlad názvu: Flows and cuts with restriction
Autoři: Knop, Dušan ; Kolman, Petr (vedoucí práce) ; Krčál, Marek (oponent)
Typ dokumentu: Diplomové práce
Rok: 2012
Jazyk: cze
Abstrakt: [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
Klíčová slova: algoritmus; složitost; sériově-paralelní grafy; řez; algorithm; complexity; cut; series-parallel graphs

Instituce: Fakulty UK (VŠKP) (web)
Informace o dostupnosti dokumentu: Dostupné v digitálním repozitáři UK.
Původní záznam: http://hdl.handle.net/20.500.11956/40785

Trvalý odkaz NUŠL: http://www.nusl.cz/ntk/nusl-305088


Záznam je zařazen do těchto sbírek:
Školství > Veřejné vysoké školy > Univerzita Karlova > Fakulty UK (VŠKP)
Vysokoškolské kvalifikační práce > Diplomové práce