Largest chordal and interval subgraphs faster than 2n

dc.rights.license	Copyright The Author(s) 2015	en_US
dc.contributor.author	Bliznets, Ivan
dc.contributor.author	Fomin, Fedor
dc.contributor.author	Pilipczuk, Michal Pawel
dc.contributor.author	Villanger, Yngve
dc.date.accessioned	2016-03-30T12:58:27Z
dc.date.available	2016-03-30T12:58:27Z
dc.date.issued	2015-08-22
dc.Published	Algorithmica 2015, Published ahead of print	eng
dc.identifier.issn	1432-0541	en_US
dc.identifier.uri	https://hdl.handle.net/1956/11779
dc.description.abstract	We prove that in a graph with n vertices, induced chordal and interval subgraphs with the maximum number of vertices can be found in time O(2λn) for some λ< 1. These are the first algorithms breaking the trivial 2nnO(1) bound of the brute-force search for these problems.	en_US
dc.language.iso	eng	eng
dc.publisher	Springer	en_US
dc.rights	Attribution CC BY 4.0	eng
dc.rights.uri	http://creativecommons.org/licenses/by/4.0	eng
dc.subject	Exact exponential algorithms	eng
dc.subject	Chordal graphs	eng
dc.subject	Interval graphs	eng
dc.subject	Maximum induced Π-subgraph	eng
dc.title	Largest chordal and interval subgraphs faster than 2n	en_US
dc.type	Peer reviewed
dc.type	Journal article
dc.date.updated	2015-11-10T08:57:57Z
dc.description.version	publishedVersion	en_US
dc.rights.holder	Copyright The Author(s) 2015	en_US
dc.identifier.doi	https://doi.org/10.1007/s00453-015-0054-2
dc.identifier.cristin	1283900
dc.subject.nsi	VDP::Matematikk og Naturvitenskap: 400	en_US

Except where otherwise noted, this item's license is described as Copyright The Author(s) 2015