Browsing Bergen Open Research Archive by Author "Heggernes, Pinar"
Now showing items 1-8 of 8
-
Computing minimal triangulation in Time o(n^2.376)
Heggernes, Pinar; Telle, Jan Arne; Villanger, Yngve (Journal article, 2005) -
Enumerating minimal connected dominating sets in graphs of bounded chordality
Golovach, Petr; Heggernes, Pinar; Kratsch, Dieter (Peer reviewed; Journal article, 2015)Listing, generating or enumerating objects of specified type is one of the principal tasks in algorithmics. In graph algorithms one often enumerates vertex subsets satisfying a certain property. We study the enumeration ... -
Finding k Disjoint Triangles in an Arbitrary Graph
Fellows, Mike; Heggernes, Pinar; Rosamond, Frances; Sloper, Christian; Telle, Jan Arne (Journal article; Peer reviewed, 2004)We consider the NP-complete problem of deciding whether an input graph on n vertices has k vertex-disjoint copies of a fixed graph H. For H=K 3 (the triangle) we give an O(22klog k + 1.869k n 2) algorithm, and for general ... -
Generation of random chordal graphs using subtrees of a tree
Seker, Oylum; Heggernes, Pinar; Ekim, Tinaz; Taskin, Z. Caner (Journal article; Peer reviewed, 2022)Chordal graphs form one of the most studied graph classes. Several graph problems that are NP-hard in general become solvable in polynomial time on chordal graphs, whereas many others remain NP-hard. For a large group of ... -
Minimizing Fill-in Size and Elimination Tree Height in Parallel Cholesky Factorization
Heggernes, Pinar (Master thesis, 1992) -
Partitioning a graph into degenerate subgraphs
Abu-Khzam, Faisal; Feghali, Carl; Heggernes, Pinar (Journal article; Peer reviewed, 2020-01)Let G = (V, E) be a connected graph with maximum degree k ≥ 3 distinct from Kk+1. Given integers s ≥ 2 and p1, . . . , ps ≥ 0, G is said to be (p1, . . . , ps)-partitionable if there exists a partition of V into sets ... -
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)