Largest chordal and interval subgraphs faster than 2n
Peer reviewed, Journal article
Published version
View/
Date
2015-08-22Metadata
Show full item recordCollections
Original version
https://doi.org/10.1007/s00453-015-0054-2Abstract
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.
Publisher
SpringerCopyright
Copyright The Author(s) 2015
Except where otherwise noted, this item's license is described as Copyright The Author(s) 2015