Research output: Contribution to journal › Article › peer-review
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 2 nnO(1) bound of the brute-force search for these problems.
| Original language | English |
|---|---|
| Pages (from-to) | 569-594 |
| Number of pages | 26 |
| Journal | Algorithmica |
| Volume | 76 |
| Issue number | 2 |
| DOIs | |
| State | Published - 1 Oct 2016 |
ID: 49787594