dc.contributor.author | Daae, Petter | |
dc.date.accessioned | 2022-07-01T23:49:26Z | |
dc.date.available | 2022-07-01T23:49:26Z | |
dc.date.issued | 2022-05-31 | |
dc.date.submitted | 2022-06-30T22:01:03Z | |
dc.identifier.uri | https://hdl.handle.net/11250/3002309 | |
dc.description.abstract | While, for undirected graphs, locally checkable vertex subset and partitioning problems have been studied extensively, the equivalent directed problems have not received nearly as much attention yet. We take a closer look at the relationship between undirected and directed problems considering hardness. We extend some properties that have already been shown for undirected graphs to directed graphs. Furthermore, we explore some of the trivialities in directed problem definitions that do not appear in undirected ones. And finally, we construct and visualize digraph coverings to achieve a deeper understanding of their structure. | |
dc.language.iso | eng | |
dc.publisher | The University of Bergen | |
dc.rights | Copyright the Author. All rights reserved | |
dc.subject | digraph | |
dc.subject | vertex subset | |
dc.subject | locally checkable vertex partitioning | |
dc.subject | vertex partitioning | |
dc.title | Properties of locally checkable vertex partitioning problems in digraphs | |
dc.type | Master thesis | |
dc.date.updated | 2022-06-30T22:01:03Z | |
dc.rights.holder | Copyright the Author. All rights reserved | |
dc.description.degree | Masteroppgave i informatikk | |
dc.description.localcode | INF399K | |
dc.description.localcode | MAMN-INF | |
dc.subject.nus | 754115 | |
fs.subjectcode | INF399K | |
fs.unitcode | 12-12-0 | |