Vis enkel innførsel

dc.contributor.authorStrømme, Torstein Jarl Fagerbakke
dc.date.accessioned2020-05-06T09:25:18Z
dc.date.available2020-05-06T09:25:18Z
dc.date.issued2020-05-07
dc.date.submitted2020-05-01T15:28:10.550Z
dc.identifiercontainer/35/1d/9b/c1/351d9bc1-e8dd-47ab-83b1-3ee41df1b235
dc.identifier.urihttps://hdl.handle.net/1956/22108
dc.description.abstractCoping with NP-hard graph problems by doing better than simply brute force is a field of significant practical importance, and which have also sparked wide theoretical interest. One route to cope with such hard graph problems is to exploit structures which can possibly be found in the input data or in the witness for a solution. In the framework of parameterized complexity, we attempt to quantify such structures by defining numbers which describe "how structured" the graph is. We then do a fine-grained classification of its computational complexity, where not only the input size, but also the structural measure in question come in to play. There is a number of structural measures called width parameters, which includes treewidth, clique-width, and mim-width. These width parameters can be compared by how many classes of graphs that have bounded width. In general there is a tradeoff; if more graph classes have bounded width, then fewer problems can be efficiently solved with the aid of a small width; and if a width is bounded for only a few graph classes, then it is easier to design algorithms which exploit the structure described by the width parameter. For each of the mentioned width parameters, there are known meta-theorems describing algorithmic results for a wide array of graph problems. Hence, showing that decompositions with bounded width can be found for a certain graph class yields algorithmic results for the given class. In the current thesis, we show that several graph classes have bounded width measures, which thus gives algorithmic consequences. Algorithms which are FPT or XP parameterized by width parameters are exploiting structure of the input graph. However, it is also possible to exploit structures that are required of a witness to the solution. We use this perspective to give a handful of polynomial-time algorithms for NP-hard problems whenever the witness belongs to certain graph classes. It is also possible to combine structures of the input graph with structures of the solution witnesses in order to obtain parameterized algorithms, when each structure individually is provably insufficient to provide so under standard complexity assumptions. We give an example of this in the final chapter of the thesis.en_US
dc.language.isoengeng
dc.publisherThe University of Bergenen_US
dc.relation.haspartPaper I: A width parameter useful for chordal and co-comparability graphs. Dong Yeap Kang, O-joung Kwon, Torstein J. F. Strømme and Jan Arne Telle. In Theoretical Computer Science, Volume 704, 2017, Pages 1–17. The article is available in the main thesis. The article is also available at: <a href="https://doi.org/10.1016/j.tcs.2017.09.006" target="blank"> https://doi.org/10.1016/j.tcs.2017.09.006</a>en_US
dc.relation.haspartPaper II: Mim-width III. Graph powers and generalized distance domination problems. Lars Jaffke, O-joung Kwon, Torstein J. F. Strømme and Jan Arne Telle. In Theoretical Computer Science, Volume 796, 2019, Pages 216–236. The article is available at: <a href="http://hdl.handle.net/1956/22107" target="blank">http://hdl.handle.net/1956/22107</a>en_US
dc.relation.haspartPaper III: Subgraph complementation. Fedor V. Fomin, Petr A. Golovach, Torstein J. F. Strømme and Dimitrios M. Thilikos. In Algorithmica, Volume 82, 2020, Pages 1859–1880. The article is available at: <a href="https://hdl.handle.net/11250/2727209" target="blank"> https://hdl.handle.net/11250/2727209</a>en_US
dc.relation.haspartPaper IV: Time-inconsistent planning: simple motivation is hard to find Fedor V. Fomin and Torstein J. F. Strømme. The article is available in the main thesis. The article is also available at: <a href="https://arxiv.org/abs/1911.07536" target="blank"> https://arxiv.org/abs/1911.07536</a>en_US
dc.rightsAttribution (CC BY)eng
dc.rights.urihttps://creativecommons.org/licenses/by/4.0/eng
dc.titleExploiting graph structures for computational efficiencyen_US
dc.typeDoctoral thesis
dc.date.updated2020-05-01T15:28:10.550Z
dc.rights.holderCopyright the Author.en_US
dc.contributor.orcid0000-0002-3896-3166
fs.unitcode12-12-0


Tilhørende fil(er)

Thumbnail

Denne innførselen finnes i følgende samling(er)

Vis enkel innførsel

Attribution (CC BY)
Med mindre annet er angitt, så er denne innførselen lisensiert som Attribution (CC BY)