Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › научная › Рецензирование
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.
| Язык оригинала | английский |
|---|---|
| Название основной публикации | Algorithms, ESA 2013 - 21st Annual European Symposium, Proceedings |
| Страницы | 193-204 |
| Число страниц | 12 |
| DOI | |
| Состояние | Опубликовано - 24 сен 2013 |
| Событие | 21st Annual European Symposium on Algorithms, ESA 2013 - Sophia Antipolis, Франция Продолжительность: 2 сен 2013 → 4 сен 2013 |
| Название | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
|---|---|
| Том | 8125 LNCS |
| ISSN (печатное издание) | 0302-9743 |
| ISSN (электронное издание) | 1611-3349 |
| конференция | 21st Annual European Symposium on Algorithms, ESA 2013 |
|---|---|
| Страна/Tерритория | Франция |
| Город | Sophia Antipolis |
| Период | 2/09/13 → 4/09/13 |
ID: 49788021