Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review
We prove that in an n-vertex graph, 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 2n nO(1) bound of the brute-force search for these problems.
| Original language | English |
|---|---|
| Title of host publication | Algorithms, ESA 2013 - 21st Annual European Symposium, Proceedings |
| Pages | 193-204 |
| Number of pages | 12 |
| DOIs | |
| State | Published - 24 Sep 2013 |
| Event | 21st Annual European Symposium on Algorithms, ESA 2013 - Sophia Antipolis, France Duration: 2 Sep 2013 → 4 Sep 2013 |
| Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
|---|---|
| Volume | 8125 LNCS |
| ISSN (Print) | 0302-9743 |
| ISSN (Electronic) | 1611-3349 |
| Conference | 21st Annual European Symposium on Algorithms, ESA 2013 |
|---|---|
| Country/Territory | France |
| City | Sophia Antipolis |
| Period | 2/09/13 → 4/09/13 |
ID: 49788021