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 |