Sökning: "Exact algorithms"
Visar resultat 1 - 5 av 91 avhandlingar innehållade orden Exact algorithms.
1. Exact Algorithms for Exact Satisfiability Problems
Sammanfattning : 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. LÄS MER
2. Studies in Efficient Discrete Algorithms
Sammanfattning : 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. LÄS MER
3. Exact and approximation algorithms for graph problems with some biological applications
Sammanfattning : 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. LÄS MER
4. Algorithms, measures and upper bounds for satisfiability and related problems
Sammanfattning : 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. LÄS MER
5. Algorithmic Bounds for Presumably Hard Combinatorial Problems
Sammanfattning : 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. LÄS MER