Результаты исследований: Научные публикации в периодических изданиях › статья › Рецензирование
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.
| Язык оригинала | английский |
|---|---|
| Страницы (с-по) | 569-594 |
| Число страниц | 26 |
| Журнал | Algorithmica |
| Том | 76 |
| Номер выпуска | 2 |
| DOI | |
| Состояние | Опубликовано - 1 окт 2016 |
ID: 49787594