Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › научная › Рецензирование
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