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.

Original languageEnglish
Pages (from-to)569-594
Number of pages26
JournalAlgorithmica
Volume76
Issue number2
DOIs
StatePublished - 1 Oct 2016

    Research areas

  • Chordal graphs, Exact exponential algorithms, Interval graphs, Maximum induced Π-subgraph

    Scopus subject areas

  • Computer Science(all)
  • Computer Science Applications
  • Applied Mathematics

ID: 49787594