Now showing items 1-12 of 12

    • Computing minimal triangulation in Time o(n^2.376) 

      Heggernes, Pinar; Telle, Jan Arne; Villanger, Yngve (SIAM Journals, 2005)
      Journal article
    • Exact algorithms for treewidth and minimum fill-in 

      Fomin, Fedor; Todinca, Ioan; Kratsch, Dieter; Villanger, Yngve (SIAM Journals, 2006)
      Journal article
    • Exploring Subexponential Parameterized Complexity of Completion Problems 

      Drange, Pål Grønås; Fomin, Fedor; Pilipczuk, Michal Pawel; Villanger, Yngve (Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2014-02-19)
      Let F be a family of graphs. In the F-Completion problem, we are given an n-vertex graph G and an integer k as input, and asked whether at most k edges can be added to G so that the resulting graph does not contain a ...
      Journal article
    • Finding Induced Subgraphs via Minimal Triangulations 

      Fomin, Fedor; Villanger, Yngve (Dagstuhl Publishing, 2010)
      Potential maximal cliques and minimal separators are combinatorial objects which were introduced and studied in the realm of minimal triangulation problems in- cluding Minimum Fill-in and Treewidth. We discover unexpected ...
      Conference object
    • Kernel(s) for Problems with No Kernel: On Out-Trees with Many Leaves 

      Fernau, Henning; Fomin, Fedor; Lokshtanov, Daniel; Raible, Daniel; Saurabh, Saket; Villanger, Yngve (Dagstuhl Publishing, 2009)
      The {\sc $k$-Leaf Out-Branching} problem is to find an out-branching, that is a rooted oriented spanning tree, with at least $k$ leaves in a given digraph. The problem has recently received much attention from the viewpoint ...
      Conference object
    • Largest chordal and interval subgraphs faster than 2n 

      Bliznets, Ivan; Fomin, Fedor; Pilipczuk, Michal Pawel; Villanger, Yngve (Springer, 2015-08-22)
      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 2nnO(1) ...
      Journal article
    • Lex M versus MCS-M 

      Villanger, Yngve (Elsevier, 2006)
      Journal article
    • Minimum Fill-in of Sparse Graphs: Kernelization and Approximation 

      Fomin, Fedor; Geevarghese, Philip; Villanger, Yngve (Dagstuhl Publishing, 2011)
      The Minimum Fill-in problem is to decide if a graph can be triangulated by adding at most k edges. The problem has important applications in numerical algebra, in particular in sparse matrix computations. We develop ...
      Conference object
    • New Results on Minimal Triangulations 

      Villanger, Yngve (The University of Bergen, 2006-04-25)
      Doctoral thesis
    • Tight bounds for parameterized complexity of Cluster Editing 

      Fomin, Fedor; Kratsch, Stefan; Pilipczuk, Marcin; Pilipczuk, Michal Pawel; Villanger, Yngve (Dagstuhl Publishing, 2013)
      In the Correlation Clustering problem, also known as Cluster Editing, we are given an undirected graph G and a positive integer k; the task is to decide whether G can be transformed into a cluster graph, i.e., a disjoint ...
      Conference object
    • A Vertex Incremental Approach for Maintening Chordiality 

      Berry, Anne; Heggernes, Pinar; Villanger, Yngve (Elsevier, 2006)
      Journal article
    • A wide-range algorithm for minimal triangulation from an arbitrary ordering 

      Berry, Anne; Bordat, Jean-Paul; Heggernes, Pinar; Simonet, Genevieve; Villanger, Yngve (Elsevier, 2006)
      Journal article