dc.contributor.author Gaspers, Serge eng dc.date.accessioned 2009-09-07T08:28:51Z dc.date.available 2009-09-07T08:28:51Z dc.date.issued 2008-12-05 eng dc.identifier.isbn 978-82-308-0714-9 (print version) en_US dc.identifier.uri https://hdl.handle.net/1956/3436 dc.description.abstract This thesis studies exponential time algorithms, more precisely, algorithms exactly solving problems for which no polynomial time algorithm is known and likely to exist. Interested in worst–case upper bounds on the running times, several known techniques to design and analyze such algorithms are surveyed. A detailed presentation of the design and especially the analysis of branching algorithms is given. Then, the branching paradigm is used to design faster algorithms for various problems, including the Feedback Vertex Set problem, #Maximal Independent Sets, Max 2-Sat, Max 2-CSP, and mixed instances of the latter two problems. The analysis of these algorithms heavily relies on problem–specific measures of the instances. These measures capture the structure of the instances, not merely their size. This makes them more appropriate to quantify the progress an algorithm makes in the process of solving a problem for an instance. Upper bounds on mathematical objects are also proved in this thesis. A bound on the maximum number of minimal feedback vertex sets is derived via the same methodology as the one used to upper bound the running time of branching algorithms. For the maximum number of maximal bicliques, a simple reduction is used to bound it in terms of the maximum number of maximal independent sets in a graph. Finally, bounds for the treewidth of a graph are proved using inductive and geometric arguments. Expanding the methodology to design exponential time algorithms, new techniques are presented. Two of them combine treewidth based algorithms with branching or enumeration algorithms. Another one is the well known technique of Iterative Compression, prominent in the design of parameterized algorithms, and adapted here to the design of exponential time algorithms. en_US dc.language.iso eng eng dc.publisher The University of Bergen en_US dc.title Exponential time algorithms: Structures, measures, and bounds en_US dc.type Doctoral thesis dc.rights.holder Copyright 2008 Serge Gaspers. en_US dc.subject.nsi VDP::Matematikk og Naturvitenskap: 400::Informasjons- og kommunikasjonsvitenskap: 420::Algoritmer og beregnbarhetsteori: 422 nob
﻿