Browsing Department of Informatics by Author "Villanger, Yngve"
Now showing items 112 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 fillin
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  LeibnizZentrum fuer Informatik, 20140219)Let F be a family of graphs. In the FCompletion problem, we are given an nvertex 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 Fillin and Treewidth. We discover unexpected ...Conference object 
Kernel(s) for Problems with No Kernel: On OutTrees with Many Leaves
Fernau, Henning; Fomin, Fedor; Lokshtanov, Daniel; Raible, Daniel; Saurabh, Saket; Villanger, Yngve (Dagstuhl Publishing, 2009)The {\sc $k$Leaf OutBranching} problem is to find an outbranching, 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, 20150822)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 

Minimum Fillin of Sparse Graphs: Kernelization and Approximation
Fomin, Fedor; Geevarghese, Philip; Villanger, Yngve (Dagstuhl Publishing, 2011)The Minimum Fillin 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, 20060425)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 widerange algorithm for minimal triangulation from an arbitrary ordering
Berry, Anne; Bordat, JeanPaul; Heggernes, Pinar; Simonet, Genevieve; Villanger, Yngve (Elsevier, 2006)Journal article