BORA - UiB

Bergen Open Research Archive

Comparing 17 graph parameters

Bergen Open Research Archive

Show simple item record

dc.contributor.author Sasák, Róbert eng
dc.date.accessioned 2010-12-02T12:10:41Z
dc.date.available 2010-12-02T12:10:41Z
dc.date.issued 2010-08-02 eng
dc.date.submitted 2010-08-02 eng
dc.identifier.uri http://hdl.handle.net/1956/4329
dc.description.abstract Many parametrized problems were decided to be FPT or W-hard. However, there is still thousands of problems and parameters for which we do not know yet whether are FPT or W-hard. In this thesis, we provide a tool for extending existing results to additional parametrized problems. We use the comparison relation for comparing graph parameters, i.e. we say that parameter p1 is bounded by parameter p2 if exists a function f that for every graph G holds p1(G)<=f(p2(G)). This allows us to extend results for parametrized problem P in two ways. If problem P parametrized by p1 is FPT then also P parametrized by p2 is FPT. Or wise-versa, if problem P parametrized by p2 is W-hard then also P parametrized by p1 is W-hard. Moreover, we show whether is a parameter bounded by another parameter for the 17 graph parameters: path-width, tree-width, branch-width, clique-width, rank-width, boolean-width, maximum independent set, minimum dominating set, vertex cover number, maximum clique, chromatic number, maximum matching, maximum induced matching, cut-width, carving-width, degeneracy and tree-depth. To avoid all 272 different comparisons, we introduce methodology for examining graph parameters which rapidly reduce number of comparisons. And finally, we provide comparison diagram for all 17 parameters. en
dc.format.extent 745190 bytes eng
dc.format.mimetype application/pdf eng
dc.language.iso eng eng
dc.publisher The University of Bergen eng
dc.title Comparing 17 graph parameters eng
dc.type Master thesis eng
dc.type.degree Master i Informatikk nob
dc.type.course INF399 eng
dc.subject.nsi VDP::Matematikk og Naturvitenskap: 400::Informasjons- og kommunikasjonsvitenskap: 420 nob
dc.subject.archivecode Mastergrad eng
dc.subject.nus 754199 eng
dc.type.program MAMN-INF eng
dc.rights.holder Copyright the author. All rights reserved
dc.rights.holder The author eng


Files in this item

 

This item appears in the following Collection(s)

Show simple item record

Search BORA


Browse

My Account