Now showing items 508-527 of 586

    • Subdivisions in digraphs of large out-degree or large dichromatic number 

      Aboulker, Pierre; Cohen, Nathann; Havet, Frederic; Lochet, William; Moura, Phablo F S; Thomasse, Stephan (Journal article; Peer reviewed, 2019)
      In 1985, Mader conjectured the existence of a function f such that every digraph with minimum out-degree at least f ( k ) contains a subdivision of the transitive tournament of order k . This conjecture is still completely ...
    • Subexponential Algorithms for Partial Cover Problems 

      Fomin, Fedor; Lokshtanov, Daniel; Raman, Venkatesh; Saurabh, Saket (Conference object; Peer reviewed; Journal article, 2009)
      Partial Cover problems are optimization versions of fundamental and well studied problems like {\sc Vertex Cover} and {\sc Dominating Set}. Here one is interested in covering (or dominating) the maximum number of edges (or ...
    • Subexponential Parameterized Algorithms and Kernelization on Almost Chordal Graphs 

      Fomin, Fedor; Golovach, Petr (Journal article; Peer reviewed, 2020)
      We study algorithmic properties of the graph class Chordal-ke, that is, graphs that can be turned into a chordal graph by adding at most k edges or, equivalently, the class of graphs of fill-in at most k. We discover that ...
    • Subexponential-time parameterized algorithm for Steiner tree on planar graphs 

      Pilipczuk, Marcin; Pilipczuk, Michal Pawel; van Leeuwen, Erik Jan; Sankowski, Piotr (Conference object; Peer reviewed; Journal article, 2013)
      The well-known bidimensionality theory provides a method for designing fast, subexponential-time parameterized algorithms for a vast number of NP-hard problems on sparse graph classes such as planar graphs, bounded genus ...
    • Subgraph Complementation 

      Fomin, Fedor; Golovach, Petr; Strømme, Torstein J. F.; Thilikos, Dimitrios M. (Journal article; Peer reviewed, 2020-02)
      A subgraph complement of the graph G is a graph obtained from G by complementing all the edges in one of its induced subgraphs. We study the following algorithmic question: for a given graph G and graph class G, is there ...
    • Subquadratic Kernels for Implicit 3-Hitting Set and 3-Set Packing Problems 

      Fomin, Fedor; Le, Tien-Nam; Lokshtanov, Daniel; Saurabh, Saket; Thomasse, Stephan; Zehavi, Meirav (Peer reviewed; Journal article, 2019)
      We consider four well-studied NP-complete packing/covering problems on graphs: Feedback Vertex Set in Tournaments (FVST), Cluster Vertex Deletion (CVD), Triangle Packing in Tournaments (TPT) and Induced P3-Packing. For ...
    • Substation Location in Offshore Wind Farms - A Planar Multi-Facility Location-Routing Problem 

      Amland, Thomas (Master thesis, 2014-03-14)
      In offshore wind farms, two important parts of the design are to determine locations for substations and a cabling layout that connects every turbine to a substation. These problems are interconnected, as the cable layout ...
    • Sufficiently overdetermined random polynomial systems behave like semiregular ones 

      Tenti, Andrea (Doctoral thesis, 2019-12-18)
      Solving systems of polynomial equations over finite fields is a fundamental problem in several areas of pure and applied mathematics. Gröbner basis methods is a family of techniques to computationally solve such systems ...
    • A Survey of Linear-Programming Guided Branching Parameterized Algorithms for Vertex Cover, with Experimental Results 

      Urhaug, Tobias Sørensen (Master thesis, 2015-06-01)
      A survey of FPT algorithms for Vertex Cover, parameterized by an above guarantee parameter.
    • Sustainability in mining protocols for public blockchains 

      Nilsen, Cecilie Daae (Master thesis, 2019-05-04)
      Blockchains are a somewhat new technology with much potential and it is meeting growing public interest. However, with wider use of the technology we face the challenge of sustainability since the current mining protocols ...
    • Systematic exploration of error sources in pyrosequencing flowgram data 

      Balzer, Susanne Mignon; Malde, Ketil; Jonassen, Inge (Peer reviewed; Journal article, 2011)
      Motivation: 454 pyrosequencing, by Roche Diagnostics, has emerged as an alternative to Sanger sequencing when it comes to read lengths, performance and cost, but shows higher per-base error rates. Although there are several ...
    • TailFindR: Alignment-free poly(A) length measurement for Oxford Nanopore RNA and DNA sequencing 

      Krause, Maximilian; Niazi, Adnan Muhammad; Labun, Kornel; Torres Cleuren, Yamila Nicole; Müller, Florian S; Valen, Eivind (Peer reviewed; Journal article, 2019-07-02)
      Polyadenylation at the 3′-end is a major regulator of messenger RNA and its length is known to affect nuclear export, stability, and translation, among others. Only recently have strategies emerged that allow for genome-wide ...
    • Techniques in parameterized algorithm design 

      Sloper, Christian (Doctoral thesis, 2006-03-06)
      In this thesis we give a novel classification of techniques for designing parameterized algorithms, together with research publications applying these techniques, in particular Crown Decompositions, to various problems. ...
    • Testing with Concepts and Axioms in C++ 

      Bagge, Anya Helene; David, Valentin; Haveraaen, Magne (Reports in Informatics: 368, Research report, 2008-10)
      Modern development practices encourage extensive testing of code while it is still under development, using unit tests to check individual code units in isolation. Such tests are typically case-based, checking a likely ...
    • ThermoRawFileParser: Modular, Scalable, and Cross-Platform RAW File Conversion 

      Hulstaert, Niels; Shofstahl, Jim; Sachsenberg, Timo; Walzer, Mathias; Barsnes, Harald; Martens, Lennart; Perez-Riverol, Yasset (Journal article; Peer reviewed, 2020)
      The field of computational proteomics is approaching the big data age, driven both by a continuous growth in the number of samples analyzed per experiment as well as by the growing amount of data obtained in each analytical ...
    • Throughput and robustness of bioinformatics pipelines for genome-scale data analysis 

      Sztromwasser, Paweł (Doctoral thesis, 2014-02-19)
      The post-genomic era has been heavily influenced by the rapid development of highthroughput molecular-screening technologies, which has enabled genome-wide analysis approaches on an unprecedented scale. The constantly ...
    • 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 ...
    • TMM@: a web application for the analysis of transmembrane helix mobility 

      Skjærven, Lars; Jonassen, Inge; Reuter, Nathalie (Peer reviewed; Journal article, 2007-07-02)
      Background: To understand the mechanism by which a protein transmits a signal through the cell membrane, an understanding of the flexibility of its transmembrane (TM) region is essential. Normal Mode Analysis (NMA) has ...
    • Tools and data services registry: a community effort to document bioinformatics resources 

      Ison, Jon; Rapacki, Kristoffer; Ménager, Hervé; Kalaš, Matúš; et al., 69 authors (Peer reviewed; Journal article, 2015-11-03)
      Life sciences are yielding huge data sets that underpin scientific discoveries fundamental to improvement in human health, agriculture and the environment. In support of these discoveries, a plethora of databases and tools ...
    • Tournaments and Optimality: New Results in Parameterized Complexity 

      Pilipczuk, Michal Pawel (Doctoral thesis; Peer reviewed, 2013-11-22)