caa a22 4500 445805293 CHVBK 20180317145154.0 cr unu---uuuuu 170323e20111201xx s 000 0 eng 10.1007/s00453-010-9421-1 doi (NATIONALLICENCE)springer-10.1007/s00453-010-9421-1 Faster Parameterized Algorithms for Minimum Fill-in [Elektronische Daten] [Hans Bodlaender, Pinar Heggernes, Yngve Villanger] We present two parameterized algorithms for the Minimum Fill-in problem, also known as Chordal Completion: given an arbitrary graph G and integer k, can we add at most k edges to G to obtain a chordal graph? Our first algorithm has running time $\mathcal {O}(k^{2}nm+3.0793^{k})$, and requires polynomial space. This improves the base of the exponential part of the best known parameterized algorithm time for this problem so far. We are able to improve this running time even further, at the cost of more space. Our second algorithm has running time $\mathcal {O}(k^{2}nm+2.35965^{k})$ and requires $\mathcal {O}^{\ast}(1.7549^{k})$ space. To achieve these results, we present a new lemma describing the edges that can safely be added to achieve a chordal completion with the minimum number of edges, regardless of k. Springer Science+Business Media, LLC, 2010 Minimum Fill-in nationallicence Parameterized algorithms nationallicence Chordal graphs nationallicence Fixed parameter tractability nationallicence Bodlaender Hans Department of Information and Computing Sciences, Utrecht University, P.O. Box 80.089, 3508 TB, Utrecht, the Netherlands aut Heggernes Pinar Department of Informatics, University of Bergen, PB 7803, 5020, Bergen, Norway aut Villanger Yngve Department of Informatics, University of Bergen, PB 7803, 5020, Bergen, Norway aut Algorithmica Springer-Verlag 61/4(2011-12-01), 817-838 0178-4617 61:4<817 2011 61 453 https://doi.org/10.1007/s00453-010-9421-1 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00453-010-9421-1 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Bodlaender Hans Department of Information and Computing Sciences, Utrecht University, P.O. Box 80.089, 3508 TB, Utrecht, the Netherlands aut NATIONALLICENCE 700 1- Heggernes Pinar Department of Informatics, University of Bergen, PB 7803, 5020, Bergen, Norway aut NATIONALLICENCE 700 1- Villanger Yngve Department of Informatics, University of Bergen, PB 7803, 5020, Bergen, Norway aut NATIONALLICENCE 773 0- Algorithmica Springer-Verlag 61/4(2011-12-01), 817-838 0178-4617 61:4<817 2011 61 453 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer