DOI

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

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

  • Компьютерные науки (все)
  • Прикладные компьютерные науки
  • Прикладная математика

ID: 49787594