National Repository of Grey Literature 2 records found  Search took 0.01 seconds. 
Length bounded cuts in graphs
Berg, Michal ; Kolman, Petr (advisor) ; Dvořák, Pavel (referee)
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.
Approximation of independence number of planar graphs
Berg, Michal ; Dvořák, Zdeněk (advisor) ; Fiala, Jiří (referee)
The independent set problem is a well-known NP-complete problem, which is NP- complete even for planar graphs. But unlike general graphs, there exists an polynomial- time approximation scheme for planar graphs. We are going to describe an exact algorithm for maximum independent set problem in planar graphs based on dynamic programming. This algorithm can be easily modified to an polynomial-time approximation scheme. We implemented both versions of this algorithm and tested them. We used a few random planar graph generators for that. We compared the exact algorithm with another two algorithms. We compared the approximation algorithm with its exact version and measured its real approximation ratio and also its time complexity in comparison with the exact version. We discovered that the exact algorithm usually finishes the computation faster than the other two algorithms. We also discovered that the approximation version has a better approximation ratio compared to the theoretical minimum with good time complexity. 1

Interested in being notified about new results for this query?
Subscribe to the RSS feed.