Search for dissertations about: "Exact algorithms"
Showing result 1 - 5 of 91 swedish dissertations containing the words Exact algorithms.
-
1. Exact Algorithms for Exact Satisfiability Problems
Abstract : This thesis presents exact means to solve a family of NP-hard problems. Starting with the well-studied Exact Satisfiability problem (XSAT) parents, siblings and daughters are derived and studied, each with interesting practical and theoretical properties. READ MORE
-
2. Studies in Efficient Discrete Algorithms
Abstract : This thesis consists of five papers within the design and analysis of efficient algorithms.In the first paper, we consider the problem of computing all-pairs shortest paths in a directed graph with real weights assigned to vertices. We develop a combinatorial randomized algorithm that runs in subcubic time for a special class of graphs. READ MORE
-
3. Exact and approximation algorithms for graph problems with some biological applications
Abstract : In this thesis we study several combinatorial problems in algorithmic graph theory and computational biology, and different algorithmical approaches for solving them. In particular, we focus on graph algorithms, seeking for the most part polynomial or sub-exponential exact solutions, but in some cases also approximate solutions. READ MORE
-
4. Algorithms, measures and upper bounds for satisfiability and related problems
Abstract : The topic of exact, exponential-time algorithms for NP-hard problems has received a lot of attention, particularly with the focus of producing algorithms with stronger theoretical guarantees, e.g. upper bounds on the running time on the form O(c^n) for some c. READ MORE
-
5. Algorithmic Bounds for Presumably Hard Combinatorial Problems
Abstract : In this thesis we present new worst case computational bounds on algorithms for some of the most well-known NP-complete and #P-complete problems and their optimization variants. We consider graph problems like Longest Path, Maximum Cut, Number of Perfect Matchings, Chromatic and Domatic Number, as well as Maximum k-Satisfiability and Set Cover. READ MORE