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.
Identifer | oai:union.ndltd.org:nusl.cz/oai:invenio.nusl.cz:406059 |
Date | January 2019 |
Creators | Berg, Michal |
Contributors | Kolman, Petr, Dvořák, Pavel |
Source Sets | Czech ETDs |
Language | Czech |
Detected Language | English |
Type | info:eu-repo/semantics/masterThesis |
Rights | info:eu-repo/semantics/restrictedAccess |
Page generated in 0.0013 seconds