Now showing items 86-105 of 345

    • Enumerating minimal connected dominating sets in graphs of bounded chordality 

      Golovach, Petr; Heggernes, Pinar; Kratsch, Dieter (Dagstuhl Publishing, 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 ...
      Conference object
    • Error Detection and Correction for Symmetric and Asymmetric Channels 

      Naydenova, Irina Petkova (The University of Bergen, 2007-08-27)
      When a message is sent over a channel errors can occur due to noise during the transmission. So it is very important to know the error correction and detection capability of the code, which is used to encode the ...
      Doctoral thesis
    • Exact algorithms for MAX-2SAT and MAX-3SAT via multidimensional matrix multiplication 

      Petkevich, Yevgheni (The University of Bergen, 2015-06-01)
      In this thesis it is showed how an $O(n^{4-\epsilon})$ algorithm for the cube multiplication problem (that is defined in the thesis) would imply a faster than naive $O^{*}(2^{n(1-\frac{\epsilon}{4})})$ algorithm for the ...
      Master thesis
    • Exact algorithms for treewidth and minimum fill-in 

      Fomin, Fedor V.; Todinca, Ioan; Kratsch, Dieter; Villanger, Yngve (SIAM Journals, 2006)
      Journal article
    • Exact methods for solving the small scale single vehicle pickup and delivery problem with time windows 

      Lakel, Yacine Mohamed (The University of Bergen, 2016-08-15)
      The single vehicle pickup and delivery problem with time windows (1-PDPTW) is a wellknown problem in transportation and combinatorics. In practice, these routes are relatively small with less then 30 stops. In this ...
      Master thesis
    • Exploring Subexponential Parameterized Complexity of Completion Problems 

      Drange, Pål Grønås; Fomin, Fedor V.; Pilipczuk, Michal Pawel; Villanger, Yngve (Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 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 ...
      Journal article
    • Exploring the evolution of protein function in Archaea 

      Goncearenco, Alexander; Berezovsky, Igor N. (BioMed Central, 2012-05-30)
      Background: Despite recent progress in studies of the evolution of protein function, the questions what were the first functional protein domains and what were their basic building blocks remain unresolved. Previously, we ...
      Journal article
    • Exponential time algorithms: Structures, measures, and bounds 

      Gaspers, Serge (The University of Bergen, 2008-12-05)
      This thesis studies exponential time algorithms, more precisely, algorithms exactly solving problems for which no polynomial time algorithm is known and likely to exist. Interested in worst–case upper bounds on the running ...
      Doctoral thesis
    • Expressive Visualization and Rapid Interpretation of Seismic Volumes 

      Patel, Daniel (The University of Bergen, 2009-10-27)
      One of the most important resources in the world today is energy. Oil and gas provide two thirds of the world energy consumption, making the world completely dependent on it. Locating and recovering the remaining oil and ...
      Doctoral thesis
    • Fast biclustering by dual parameterization 

      Drange, Pål Grønås; Reidl, Felix; Villaamil, Fernando Sánchez; Sikdar, Somnath (Dagstuhl Publishing, 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 ...
      Conference object
    • Fast Method for Maximum-Flow Problem with Minimum-Lot Sizes 

      Ganeshan, Vithya (The University of Bergen, 2015-03-03)
      In transportation networks, such as pipeline networks for transporting natural gas, it is often impractical to send across amounts of flow below a certain threshold. Such lower threshold is referred as the minimum-lot size. ...
      Master thesis
    • Fast methods to solve the pooling problem 

      Kejriwal, Anisha (The University of Bergen, 2014-05-31)
      In pipeline transportation of natural gas, simple network flow problems are replaced by hard ones when bounds on the flow quality are imposed. The sources, typically represented by gas wells, provide flow of unequal ...
      Master thesis
    • Faster enumeration of minimal connected dominating sets in split graphs 

      Skjørten, Ida Bredal (The University of Bergen, 2017-06-20)
      Graphs are mathematical objects that can be used to model many real world problems. An example is a roadmap, where the nodes in the graph represent cities and the edges of the graph represent roads. An interesting and ...
      Master thesis
    • Feasible Algorithms for Semantics — Employing Automata and Inference Systems 

      Hovland, Dag (The University of Bergen, 2010-12-16)
      Doctoral thesis
    • Filtering duplicate reads from 454 pyrosequencing data 

      Balzer, Susanne Mignon; Malde, Ketil; Grohme, Markus A.; Jonassen, Inge (Oxford University Press, 2013)
      Motivation: Throughout the recent years, 454 pyrosequencing has emerged as an efficient alternative to traditional Sanger sequencing and is widely used in both de novo whole-genome sequencing and metagenomics. Especially ...
      Peer reviewedJournal article
    • Filtering of FTLE for Visualizing Spatial Separation in Unsteady 3D Flow 

      Pobitzer, Armin; Peikert, Ronald; Fuchs, Raphael; Theisel, Holger; Hauser, Helwig (Springer, 2012)
      In many cases, feature detection for flow visualization is structured in two phases: first candidate identification, and then filtering. With this paper, we propose to use the directional information contained in the ...
      Peer reviewedJournal article
    • Finding even subgraphs even faster 

      Goyal, Prachi; Misra, Pranabendu; Panolan, Fahad; Philip, Geevarghese; Saurabh, Saket (Dagstuhl Publishing, 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 ...
      Conference object
    • Finding Induced Subgraphs via Minimal Triangulations 

      Fomin, Fedor; Villanger, Yngve (Dagstuhl Publishing, 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 ...
      Conference object
    • Finding k Disjoint Triangles in an Arbitrary Graph 

      Fellows, Mike; Heggernes, Pinar; Rosamond, Frances; Sloper, Christian; Telle, Jan Arne (Springer Verlag, 2004)
      Conference object
    • Finding Resource Bounds in the Presence of Explicit Deallocation 

      Truong, Anh Hoang; Bezem, Marcus A. (Springer Berlin Heidelberg, 2005-10-17)
      A software program requesting a resource that is not available usually raises an out-of-resource exception. Component software is software that has been assembled from standardized, reusable components which, in turn, may ...
      Journal article