DOI

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 сен 20134 сен 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/134/09/13

    Предметные области Scopus

  • Теоретические компьютерные науки
  • Компьютерные науки (все)

ID: 49788021