Browsing Bergen Open Research Archive by Author "Villanger, Yngve"
Now showing items 1-12 of 12
-
Computing minimal triangulation in Time o(n^2.376)
Heggernes, Pinar; Telle, Jan Arne; Villanger, Yngve (Journal article, 2005) -
Exact algorithms for treewidth and minimum fill-in
Fomin, Fedor; Todinca, Ioan; Kratsch, Dieter; Villanger, Yngve (Journal article, 2006) -
Exploring Subexponential Parameterized Complexity of Completion Problems
Drange, Pål Grønås; Fomin, Fedor; Pilipczuk, Michal Pawel; Villanger, Yngve (Peer reviewed; Journal article, 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 graph ... -
Finding Induced Subgraphs via Minimal Triangulations
Fomin, Fedor; Villanger, Yngve (Conference object; Peer reviewed; Journal article, 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 ... -
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 (Conference object; Peer reviewed; Journal article, 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 ... -
Largest chordal and interval subgraphs faster than 2n
Bliznets, Ivan; Fomin, Fedor; Pilipczuk, Michal Pawel; Villanger, Yngve (Peer reviewed; Journal article, 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) ... -
Lex M versus MCS-M
Villanger, Yngve (Journal article, 2006) -
Minimum Fill-in of Sparse Graphs: Kernelization and Approximation
Fomin, Fedor; Geevarghese, Philip; Villanger, Yngve (Conference object; Peer reviewed; Journal article, 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 ... -
New Results on Minimal Triangulations
Villanger, Yngve (Doctoral thesis, 2006-04-25) -
Tight bounds for parameterized complexity of Cluster Editing
Fomin, Fedor; Kratsch, Stefan; Pilipczuk, Marcin; Pilipczuk, Michal Pawel; Villanger, Yngve (Conference object; Peer reviewed; Journal article, 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 ... -
A Vertex Incremental Approach for Maintening Chordiality
Berry, Anne; Heggernes, Pinar; Villanger, Yngve (Journal article, 2006) -
A wide-range algorithm for minimal triangulation from an arbitrary ordering
Berry, Anne; Bordat, Jean-Paul; Heggernes, Pinar; Simonet, Genevieve; Villanger, Yngve (Journal article, 2006)