• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

Article

Largest Chordal and Interval Subgraphs Faster than 2^n

Algorithmica. 2016. Vol. 76. No. 2. P. 569-594.
Bliznets Ivan, Fomin F., Pilipczuk M., Villanger Y.

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 2^(𝜆𝑛) for some 𝜆<1. These are the first algorithms breaking the trivial 2^𝑛 poly(n) bound of the brute-force search for these problems.