Browsing Department of Informatics by Subject "VDP::Matematikk og Naturvitenskap: 400"

Now showing items 1-20 of 28

    • Additive Schwarz preconditioner for the finite volume element discretization of symmetric elliptic problems 

      Marcinkowski, Leszek; Rahman, Talal; Loneland, Atle; Valdman, Jan (Peer reviewed; Journal article, 2015-09-25)
      A symmetric and a nonsymmetric variant of the additive Schwarz preconditioner are proposed for the solution of a class of finite volume element discretization of the symmetric elliptic problem in two dimensions, with large ...

    • Aligning a Splice Graph to a Genomic Sequence 

      Ølberg, Øyvind (Master thesis, 2005-06-01)

    • B-chromatic number: Beyond NP-hardness 

      Panolan, Fahad; Philip, Geevarghese; Saurabh, Saket (Peer reviewed; Journal article, 2015)
      The b-chromatic number of a graph G, chi_b(G), is the largest integer k such that G has a k-vertex coloring with the property that each color class has a vertex which is adjacent to at least one vertex in each of the other ...

    • Chromatin and epigenetic features of long-range gene regulation 

      Harmston, Nathan; Lenhard, Boris (Peer reviewed; Journal article, 2013-06-13)
      The precise regulation of gene transcription during metazoan development is controlled by a complex system of interactions between transcription factors, histone modifications and modifying enzymes and chromatin conformation. ...

    • Connecting Vertices by Independent Trees 

      Basavaraju, Manu; Fomin, Fedor; Golovach, Petr; Saurabh, Saket (Journal article; Peer reviewed, 2014)
      We study the paramereteized complexity of the following connectivity problem. For a vertex subset U of a graph G, trees T1, . . . , Ts of G are completely independent spanning trees of U if each of them contains U , and ...

    • Editing to Eulerian Graphs 

      Dabrowski, Konrad K.; Golovach, Petr; van' t Hof, Pim; Paulusma, Daniël (Journal article; Peer reviewed, 2014)
      We investigate the problem of modifying a graph into a connected graph in which the degree of each vertex satisfies a prescribed parity constraint. Let ea, ed and vd denote the operations edge addition, edge deletion and ...

    • The EMBRACE web service collection 

      Pettifer, Steve; Ison, Jon; Kalaš, Matúš; Thorne, David; McDermott, Philip; Jonassen, Inge; Ali, Liaquat; Fernandez, Jose M; Rodriguez, Jose M; Pisano, David G; Blanchet, Christophe; Uludag, Mahmut; Rice, Peter; Bartaseviciute, Edita; Rapacki, Kristoffer; Hekkelman, Maarten; Sand, Olivier; Stockinger, Heinz; Clegg, Andrew B; Bongcam-Rudloff, Eric; Salzemann, Jean; Breton, Vincent; Attwood, Teresa K; Cameron, Graham; Vriend, Gert (Peer reviewed; Journal article, 2010-05-10)
      The EMBRACE (European Model for Bioinformatics Research and Community Education) web service collection is the culmination of a 5-year project that set out to investigate issues involved in developing and deploying web ...

    • 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 ...

    • Fast biclustering by dual parameterization 

      Drange, Pål Grønås; Reidl, Felix; Villaamil, Fernando Sánchez; Sikdar, Somnath (Peer reviewed; Journal article, 2015)
      We study two clustering problems, Starforest Editing, the problem of adding and deleting edges to obtain a disjoint union of stars, and the generalization Bicluster Editing. We show that, in addition to being NP-hard, none ...

    • Finding even subgraphs even faster 

      Goyal, Prachi; Misra, Pranabendu; Panolan, Fahad; Philip, Geevarghese; Saurabh, Saket (Peer reviewed; Journal article, 2015)
      Problems of the following kind have been the focus of much recent research in the realm of parameterized complexity: Given an input graph (digraph) on n vertices and a positive integer parameter k, find if there exist k ...

    • Finding Induced Subgraphs via Minimal Triangulations 

      Fomin, Fedor; Villanger, Yngve (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 ...

    • The Genomic HyperBrowser: an analysis web server for genome-scale data 

      Sandve, Geir Kjetil; Gundersen, Sveinung; Johansen, Morten; Glad, Ingrid Kristine; Gunathasan, Krishanthi; Holden, Lars; Holden, Marit; Liestøl, Knut; Nygård, Ståle; Nygaard, Vegard; Paulsen, Jonas; Rydbeck, Halfdan; Trengereid, Kai; Clancy, Trevor; Drabløs, Finn; Ferkingstad, Egil; Kalaš, Matúš; Lien, Tonje Gulbrandsen; Rye, Morten Beck; Frigessi, Arnoldo; Hovig, Johannes Eivind (Peer reviewed; Journal article, 2013-04-30)
      The immense increase in availability of genomic scale datasets, such as those provided by the ENCODE and Roadmap Epigenomics projects, presents unprecedented opportunities for individual researchers to pose novel falsifiable ...

    • Investigating Streamless Sets 

      Parmann, Erik (Journal article; Peer reviewed, 2015)
      In this paper we look at streamless sets, recently investigated by Coquand and Spiwack. A set is streamless if every stream over that set contain a duplicate. It is an open question in constructive mathematics whether the ...

    • 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 (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) ...

    • Maximum matching width: New characterizations and a fast algorithm for dominating set 

      Jeong, Jisu; Sæther, Sigve Hortemo; Telle, Jan Arne (Peer reviewed; Journal article, 2015)
      We give alternative definitions for maximum matching width, e.g., a graph G has mmw(G) <= k if and only if it is a subgraph of a chordal graph H and for every maximal clique X of H there exists A,B,C \subseteq X with A ...

    • Minimizing Fill-in Size and Elimination Tree Height in Parallel Cholesky Factorization 

      Heggernes, Pinar (Master thesis, 1992)

    • Model Checking Healthcare Workflows Using Alloy 

      Wang, Xiaoliang; Rutle, Adrian (Journal article; Peer reviewed, 2014)
      Workflows are used to organize business processes, and workflow management tools are used to guide users in which order these processes should be performed. These tools increase organizational efficiency and enable users ...

    • New Results on Minimal Triangulations 

      Villanger, Yngve (Doctoral thesis, 2006-04-25)

    • Non-Constructivity in Kan Simplicial Sets 

      Bezem, Marc; Coquand, Thierry; Parmann, Erik (Journal article; Peer reviewed, 2015)
      We give an analysis of the non-constructivity of the following basic result: if X and Y are simplicial sets and Y has the Kan extension property, then Y X also has the Kan extension property. By means of Kripke countermodels ...