Journal papers

Treewidth computation and extremal combinatorics
Fedor V. Fomin and Yngve Villanger
Combinatorica, to appear.

Proper interval vertex deletion
Pim van 't Hof and Yngve Villanger
Algorithmica, to appear.

Parameterized complexity of vertex deletion into perfect graph classes
Pinar Heggernes, Pim van 't Hof, Bart Jansen, Stefan Kratsch and Yngve Villanger
Theoretical Computer Science, to appear

Local search: Is brute-force avoidable?
Michael R. Fellows, Fedor V. Fomin, Daniel Lokshtanov, Frances A. Rosamond, Saket Saurabh, Yngve Villanger
J. Comput. Syst. Sci. 78(3), pages 707-719.

Faster parameterized algorithms for Minimum Fill-In
Hans Bodlaender, Pinar Heggernes, and Yngve Villanger
Algorithmica. 61-4 (2011), pages 817-838.

Interval Completion is Fixed Parameter Tractable
Yngve Villanger, Pinar Heggernes, Christophe Paul, and Jan Arne Telle
 SIAM Journal on Computing.38-5 (2009), pages 2007-2020.

Improved Algorithms for Feedback Vertex Set Problems
Jianer Chen, Fedor V. Fomin, Yang Liu, Songjian Lu, and Yngve Villanger
Journal of Computer and System Sciences, 74-7 (2008) pages 1188-1198.

Exact algorithms for treewidth and minimum fill-in
Fedor V. Fomin, Ioan Todinca, Dieter Kratsch, and Yngve Villanger
SIAM Journal on Computing.38-3 (2008), pages 1058-1079.

A vertex incremental approach for dynamically maintaining chordal graphs
Anne Berry, Pinar Heggernes, and Yngve Villanger
Discrete Mathematics. 306-3 (2006), pages 318-336. (.pdf)

Lex M versus MCS-M
Yngve Villanger
Discrete Mathematics. 306-3 (2006), pages 393-400. (.pdf)

A wide-range algorithm for minimal triangulation from an arbitrary ordering
Anne Berry, Jean-Paul Bordat, Pinar Heggernes, Genevieve Simonet, and Yngve Villanger
Journal of Algorithms. 58-1 (2006), pages 33 – 66. (.pdf)

Computing Minimal Triangulations in Time O(nα log n) = o(n2.376)
Pinar Heggernes, Jan Arne Telle, and Yngve Villanger
SIAM Journal on Discrete Mathematics. 19-4 (2005), pages 900-913.
(.pdf)


Conferences 

A Multivariate Analysis of Some DFA Problems
Henning Fernau, Pinar Heggernes and Yngve Villanger
Proceedings of LATA 2013, To appear.

Tight bounds for Parameterized Complexity of Cluster Editing
Fedor Fomin, Stefan Kratsch, Marcin Pilipczuk, Michał Pilipczuk and Yngve Villanger.
Proceedings of STACS 2013, To appear.

Searching for better fill-in
Fedor Fomin and Yngve Villanger.
Proceedings of STACS 2013, To appear.

A Polynomial kernel for Proper Interval Vertex Deletion
Fedor V. Fomin, Saket Saurabh and Yngve Villanger.
Proceedings of ESA 2012 Lecture Notes in Computer Science, 7501, pages 467-478.

FPT algorithms for domination in biclique-free graphs
Jan Arne Telle and Yngve Villanger.
Proceedings of ESA 2012 Lecture Notes in Computer Science, 7501, pages 802-812.

On the parameterized complexity of finding separators with non-hereditary properties
Pinar Heggernes, Pim Van 'T Hof, Daniel Marx, Neeldhara Misra and Yngve Villanger.
Proceedings of WG 2012 Lecture Notes in Computer Science, 7551, pages 332-343.

Maximum number of minimal feedback vertex sets in chordal graphs and cographs
Jean-François Couturier, Pinar Heggernes, Pim van 't Hof, and Yngve Villanger.
Proceedings of COCOON 2012, Lecture Notes in Computer Science, 7434, pages 133-144.

k-Gap Interval Graphs
Fedor Fomin, Serge Gaspers, Petr Golovach, Karol Suchan, Stefan Szeider, Erik Jan Van Leeuwen, Martin Vatshelle and Yngve Villanger.
Proceedings of LATIN 2012 - 10th Latin American Theoretical Informatics Symposium, April 2012,Lecture Notes in Computer Science, 7256, Pages 350-361.

Subexponential Parameterized Algorithm for Minimum Fill-in
Fedor V. Fomin and Yngve Villanger.
Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms SODA 2012,Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, Pages 1737-1746.

Minimum Fill-in of Sparse Graphs: Kernelization and Approximation
Fedor V. Fomin, Geevarghese Philip and Yngve Villanger.
IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2011, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Pages 164-175

Exact algorithm for the maximum induced planar subgraph problem
Fedor V. Fomin, Ioan Todinca and Yngve Villanger.
19th European Symposium on Algorithms, ESA 2011, Saarbrücken, Germany, Springer Verlag, Lecture Notes in Computer Science, 6942, Pages 287-298.

Parameterized Complexity of Vertex Deletion into Perfect Graph Classes
Pinar Heggernes, Pim Van 'T Hof, Bart Jansen, Stefan Kratsch and Yngve Villanger
18th International Symposium on Fundamentals of Computation Theory, FCT 2011, Oslo, Norway, Springer Verlag, Lecture Notes in Computer Science, 6914, Pages 240-251.

Enumerating Minimal Subset Feedback Vertex Sets
Fedor V. Fomin, Pinar Heggernes, Dieter Kratsch, Charis Papadopoulos and Yngve Villanger
12th Algorithms and Data Structures Symposium, WADS 2011, Brooklyn, USA, Springer Verlag, Lecture Notes in Computer Science, 6844, Pages 399-410.

Proper Interval Vertex Deletion
Yngve Villanger
Parameterized and Exact Computation 5th International Symposium, IPEC 2010, Chennai, India, Springer Verlag, Lecture Notes in Computer Science 6478, Pages 228-238.

Induced Subgraph Isomorphism on Interval and Proper Interval Graphs
Pinar Heggernes, Daniel Meister, and Yngve Villanger
Algorithms and Computation - 21st International Symposium, ISAAC 2010, Jeju Island, Korea, Springer Verlag, Lecture Notes in Computer Science 6507, Pages 399-409. During a revision of the paper it was discovered that the algorithm verifying if an interval graph G have an induced subgraph isomorphic to a connected proper interval graph H contains a bug. Thus, the complexity for this problem remains open.

A Quartic Kernel for Pathwidth-One Vertex Deletion
Geevarghese Philip, Venkatesh Raman and Yngve Villanger
36th International Workshop on Graph Theoretic Concepts in Computer Science, Crete, Greece 2010, Springer Verlag, Lecture Notes in Computer Science 6410, Pages 196-207.

Solving Capacitated Dominating Set by using Covering by Subsets and Maximum Matching
Mathieu Liedloff, Ioan Todinca and Yngve Villanger
36th International Workshop on Graph Theoretic Concepts in Computer Science, Crete, Greece 2010, Springer Verlag, Lecture Notes in Computer Science 6410, Pages 88-99.

A parameterized algorithm for Chordal Sandwich
Pinar Heggernes, Federico Mancini, Jesper Nederlof, and Yngve Villanger
7th International Conference on Algorithms and Complexity, Rome, Italy 2010, Springer Verlag, Lecture Notes in Computer Science 6078, Pages 120-130.

Finding Induced Subgraphs via Minimal Triangulations
Fedor V. Fomin and Yngve Villanger
27th International Symposium on Theoretical Aspects of Computer Science, STACS 2010, March 4-6, 2010, Nancy, France. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik 2010, Pages 383-394.

Computing Pathwidth Faster Than 2^n
Karol Suchan and Yngve Villanger
Parameterized and Exact Computation, 4th International Workshop, IWPEC 2009,Copenhagen, Denmark, Springer Verlag, Lecture Notes in Computer Science 5917, Pages 324-335.

Local Search: Is brute-force avoidable?
Michael R. Fellows, Fedor V. Fomin, Daniel Lokshtanov, Frances A. Rosamond, Saket Saurabh, and Yngve Villanger 
Twenty-first International Joint Conference on Artificial Intelligence (IJCAI-09), Pasadena, USA 2009, pages 486-491.

Kernel(s) for Problems With no Kernel: On Out-Trees With Many Leaves
Henning Fernau, Fedor Fomin, Daniel Lokshtanov, Daniel Raible, Saket Saurabh and Yngve Villanger
The 26th International Symposium on Theoretical Aspects of Computer Science(STACS), Freiburg, German, February 2009. Dagstuhl Seminar Proceedings 09001, Pages 421-432.

 Faster parameterized algorithms for Minimum Fill-In
Hans L. Bodlaender, Pinar Heggernes and Yngve Villanger
 The 19th International Symposium on Algorithms and Computation ISAAC 2008, Gold Coast, Australia, December 2008.
Springer Verlag, Lecture Notes in Computer Science 5369, Pages 282-293.

Parameterized complexity for domination problems on degenerate graphs
Petr Golovach and Yngve Villanger
The 34th International Workshop on Graph-Theoretic Concepts in Computer Science WG 2008, July 2008 Durham - U.K.
Springer Verlag, Lecture Notes in Computer Science 5344, Pages 195-205.

Treewidth computation and extremal combinatorics
Fedor V. Fomin and Yngve Villanger
35th International Colloquium on Automata, Languages and Programming, ICALP 2008, July 2008 Reykjavik - Iceland.
Springer Verlag, Lecture Notes in Computer Science 5125, Pages 210-221. (.pdf)

Capacitated Domination and Covering: A Parameterized Perspective
Michael Dom, Daniel Lokshtanov, Saket Saurabh, and Yngve Villanger Parameterized and Exact Computation, Third International Workshop, IWPEC 2008, May 2008 Victoria - Canada.
Springer Verlag, Lecture Notes in Computer Science 5018, Pages 78-90.

Improved Algorithms for the Feedback Vertex Set Problems
Jianer Chen, Fedor V. Fomin, Yang Liu, Songjian Lu, and Yngve Villanger
10th International Workshop, WADS 2007, August 2007 Halifax, Canada.
Springer Verlag, Lecture Notes in Computer Science 4619, Pages 422 - 433. (.pdf)

Interval Completion is Fixed Parameter Tractable
Pinar Heggernes, Christophe Paul, Jan Arne Telle, and Yngve Villanger
Proceedings STOC 2007 - 39th ACM Symposium on Theory of Computing, June 2007, San Diego, USA. ACM 2007, pages 374-381. (.pdf)

Characterizing minimal interval completions: Towards better understanding of profile and pathwidth
Pinar Heggernes, Karol Suchan, Ioan Todinca, and Yngve Villanger
Proceedings STACS 2007 - 24th International Symposium on Theoretical Aspects of Computer Science, February 2007, Achen, Germany.
Springer Verlag, Lecture Notes in Computer Science 4393, Pages 236 - 247. (.pdf)

Improved exponential-time algorithms for treewidth and minimum fill-in
Yngve Villanger
Proceedings of LATIN 2006 - 7th Latin American Theoretical Informatics Symposium, March 2006, Valdivia, Chile.
Springer Verlag, Lecture Notes in Computer Science 3887, Pages 800 - 811. (.pdf)

Minimal interval completions
Pinar Heggernes, Karol Suchan, Ioan Todinca, and Yngve Villanger
Proceedings of ESA 2005 - 13th Annual European Symposium on Algorithms, October 2005, Eivissa, Spain.
Springer Verlag, Lecture Notes in Computer Science 3669, Pages 403 - 414. (.pdf)

Computing Minimal Triangulations in O(nα log n) Time
Pinar Heggernes, Jan Arne Telle, and Yngve Villanger
Proceedings SODA 2005 - 16th Annual ACM-SIAM Symposium on Discrete Algorithms,
Vancouver, Canada, January 2005, pages 907 - 916.


(See Journal version)

Modifying a given elimination ordering to reduce fill
Pinar Heggernes, and Yngve Villanger
Proceedings PARA 2004 - Workshop on State-of-the-Art in Scientific Computing, Lyngby, Denmark, June 2004.
Springer Verlag, Lecture Notes in Computer Science 3732, pages 788 - 797. (.pdf)

A vertex incremental approach for dynamically maintaining chordal graphs
Anne Berry, Pinar Heggernes, and Yngve Villanger
Proceedings ISAAC 2003 - 14th International Symposium on Algorithms and Computation, Kyoto, Japan, December 2003.
Springer Verlag, Lecture Notes in Computer Science 2906, pages 47 - 57. (See Journal version)

Efficient Implementation of a Minimal Triangulation Algorithm
Pinar Heggernes and Yngve Villanger
Proceedings ESA 2002 - 10th European Symposium on Algorithms,
Rome, Italy, September 2002. Springer Verlag, Lecture Notes in Computer Science 2461, pages 550-561. (.pdf)