Independent Set on P5-free graphs, an empirical study

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