Vis enkel innførsel

dc.contributor.authorNordstrand, Joakim Alme
dc.date.accessioned2017-08-16T15:47:45Z
dc.date.available2017-08-16T15:47:45Z
dc.date.issued2017-07-04
dc.date.submitted2017-07-03T22:00:11Z
dc.identifier.urihttps://hdl.handle.net/1956/16325
dc.description.abstractIn a recent paper appearing at IPEC 2015, ”Maximum matching width: new characterization and fast algorithms for dominating set” [12], three similar treelike parameters, tree-width, branch-width and maximum matching-width, are studied using a common framework. Here we extend the work of that paper in several ways. First we will answer one of the open problems by proving that the ”last parameter” from the framework defining the three parameters is equal to tree-width. Second we fill out the details in one of the proofs to ensure its correctness. Third we define two new parameters, linear branch-width and linear maximum matching-with. These are the ”path-like” variants of branch-width and maximum matching-width respectively in the same sense that path-width is the ”path-like” variant of tree-width. We show that linear branch-width is almost identical to path-width, for any graph G we have pw(G) ≤ lbw(G) ≤ pw(G) + 1, and that when a graph has linear maximum matching-width k then its pathwidth is somewhere between k and 2k. We also explore the minimal forbidden minors of graphs with linear branch-width less than 1,2 and 3 and with linear maximum matching-width less than 1,2 and 3.en_US
dc.language.isoengeng
dc.publisherThe University of Bergenen_US
dc.titleExploring graph parameters similar to tree-width and path-widthen_US
dc.typeMaster thesis
dc.date.updated2017-07-03T22:00:11Z
dc.rights.holderCopyright the Author. All rights reserveden_US
dc.description.degreeMasteroppgave i informatikken_US
dc.description.localcodeINF399
dc.subject.nus754199eng
fs.subjectcodeINF399
fs.unitcode12-12-00


Tilhørende fil(er)

Thumbnail

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

Vis enkel innførsel