skip to main content

Subexponential Parameterized Algorithm for I nterval C ompletion

Bliznets, Ivan ; Fomin, Fedor V. ; Pilipczuk, Marcin ; Pilipczuk, Michał

ACM Transactions on Algorithms, 07/16/2018, Vol.14(3), pp.1-62 [Periódico revisado por pares]

Texto completo disponível

Citações Citado por
  • Título:
    Subexponential Parameterized Algorithm for I nterval C ompletion
  • Autor: Bliznets, Ivan ; Fomin, Fedor V. ; Pilipczuk, Marcin ; Pilipczuk, Michał
  • Assuntos: Subexponential Algorithms ; Completion Problems ; Graph Modification Problems ; Interval Graphs ; Computer Science
  • É parte de: ACM Transactions on Algorithms, 07/16/2018, Vol.14(3), pp.1-62
  • Descrição: In the Interval Completion problem we are given an n-vertex graph G and an integer k, and the task is to transform G by making use of at most k edge additions into an interval graph. This is a fundamental graph modification problem with applications in sparse matrix multiplication and molecular biology. The question about fixed-parameter tractability of Interval Completion was asked by Kaplan et al. [FOCS 1994; SIAM J. Comput. 1999] and was answered affirmatively more than a decade later by Villanger et al. [STOC 2007; SIAM J. Comput. 2009], who presented an algorithm with running time O(k2kn3m). We give the first subexponential parameterized algorithm solving Interval Completion in time kO( k)nO(1). This adds Interval Completion to a very small list of parameterized graph modification problems solvable in subexponential time.
  • Idioma: Inglês

Buscando em bases de dados remotas. Favor aguardar.