• 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)
    • Approximating Acyclicity Parameters of Sparse Hypergraphs 

      Fomin, Fedor; Golovach, Petr; Thilikos, Dimitrios (Conference object; Peer reviewed; Journal article, 2009)
      The notions of hypertree width and generalized hypertree width were introduced by Gottlob, Leone, and Scarcello (PODS'99, PODS'01) in order to extend the concept of hypergraph acyclicity. These notions were further generalized ...
    • B-chromatic number: Beyond NP-hardness 

      Panolan, Fahad; Philip, Geevarghese; Saurabh, Saket (Conference object; 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. ...
    • Computing cutwidth and pathwidth of semi-complete digraphs via degree orderings 

      Pilipczuk, Michal Pawel (Conference object; Peer reviewed; Journal article, 2013)
      The notions of cutwidth and pathwidth of digraphs play a central role in the containment theory for tournaments, or more generally semi-complete digraphs, developed in a recent series of papers by Chudnovsky, Fradkin, Kim, ...
    • Connecting Vertices by Independent Trees 

      Basavaraju, Manu; Fomin, Fedor; Golovach, Petr; Saurabh, Saket (Conference object, 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 (Conference object, 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 (Conference object; 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 (Conference object; 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 (Conference object; 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 (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 ...
    • 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 (Conference object; 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 (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) ...
    • Maximum matching width: New characterizations and a fast algorithm for dominating set 

      Jeong, Jisu; Sæther, Sigve Hortemo; Telle, Jan Arne (Conference object; 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 ...
    • Model Checking Healthcare Workflows Using Alloy 

      Wang, Xiaoliang; Rutle, Adrian (Conference object; 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 ...