dc.contributor.author | Haug, Håvard Karim | |
dc.date.accessioned | 2016-01-13T15:31:21Z | |
dc.date.available | 2016-01-13T15:31:21Z | |
dc.date.issued | 2015-11-20 | |
dc.date.submitted | 2015-11-20 | eng |
dc.identifier.uri | https://hdl.handle.net/1956/10946 | |
dc.description.abstract | We implement the recent polynomial time algorithm for the independent set problem on P5-free graphs, and study the performance of this algorithm on graphs of size up to 50. Our empirical results show that the algorithm is probably much faster than its theoretical running-time upperbound. | en_US |
dc.format.extent | 1001615 bytes | eng |
dc.format.mimetype | application/pdf | eng |
dc.language.iso | eng | eng |
dc.publisher | The University of Bergen | en_US |
dc.subject | Indendent Set | eng |
dc.subject | Graph classes | eng |
dc.subject | Algorithms | eng |
dc.subject | Polynomial time | eng |
dc.subject | Grafalgoritmer | nb |
dc.title | Independent Set on P5-free graphs, an empirical study | en_US |
dc.type | Master thesis | |
dc.rights.holder | Copyright the Author. All rights reserved | en_US |
dc.description.degree | Master i Informatikk | en_US |
dc.description.localcode | MAMN-INF | |
dc.description.localcode | INF399 | |
dc.subject.realfagstermer | https://data.ub.uio.no/realfagstermer/c004774 | |
dc.subject.nus | 754199 | eng |
fs.subjectcode | INF399 | |