Department of Informatics
Browse by
Recent Submissions

Choice of parameter for DPbased FPT algorithms: four case studies
(The University of Bergen, 20150907)This thesis studies dynamic programming algorithms and structural parameters used when solving computationally hard problems. In particular, we look at algorithms that make use of structural decompositions to overcome ... 
Exact algorithms for MAX2SAT and MAX3SAT via multidimensional matrix multiplication
(The University of Bergen, 20150601)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 ... 
Localizing Cell Towers from Crowdsourced Measurements
(The University of Bergen, 20150601)Today, several internet sites exist that aim to provide the locations and number of cellular network antennas worldwide. For example [1],[2] and [3]. What makes this task difficult to accomplish is the lack of information ... 
A Model of Type Theory in Cubical Sets
(Schloss Dagstuhl  LeibnizZentrum für Informatik, 2014)We present a model of type theory with dependent product, sum, and identity, in cubical sets. We describe a universe and explain how to transform an equivalence between two types into an equality. We also explain how to ... 
Maximum number of edges in graph classes under degree and matching constraints
(The University of Bergen, 20150512)In extremal graph theory, we ask how large or small a property of a graph can be, when the graph has to satisfy certain constraints. In this thesis, we ask how many edges a graph can have with restrictions on its degree ... 
Community Detection in Social Networks
(The University of Bergen, 20150501)Social networks usually display a hierarchy of communities and it is the task of community detection algorithms to detect these communities and preferably also their hierarchical relationships. One common class of ... 
Fast Method for MaximumFlow Problem with MinimumLot Sizes
(The University of Bergen, 20150303)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 minimumlot size. ... 
Molecular mechanisms of adaptation emerging from the physics and evolution of nucleic acids and proteins
(Oxford University Press, 2014)DNA, RNA and proteins are major biological macromolecules that coevolve and adapt to environments as components of one highly interconnected system. We explore here sequence/structure determinants of mechanisms of adaptation ... 
Combining AspectOriented and Strategic Programming
(Elsevier, 200601)Properties such as logging, persistence, debugging, tracing, distribution, performance monitoring and exception handling occur in most programming paradigms and are normally very difficult or even impossible to modularizewith ... 
Interfacing concepts: Why declaration style shouldn't matter
(Elsevier, 20100917)A concept (or signature) describes the interface of a set of abstract types by listing the operations that should be supported for those types. When implementing a generic operation, such as sorting, we may then specify ... 
Hybrid visibility compositing and masking for illustrative rendering
(Elsevier, 201008)In this paper, we introduce a novel framework for the compositing of interactively rendered 3D layers tailored to the needs of scientific illustration. Currently, traditional scientific illustrations are produced in a ... 
AxiomBased Transformations: Optimisation and Testing
(Elsevier, 20091010)Programmers typically have knowledge about properties of their programs that aren't explicitly expressed in the code properties that may be very useful for, e.g., compiler optimisation and automated testing. Although ... 
Current Trends for 4D SpaceTime Topology for Semantic Flow Segmentation
(Elsevier, 2011) 
A Diagrammatic Logic for ObjectOriented Visual Modeling
(Elsevier, 20081121)Formal generalized sketches is a graphbased specification format that borrows its main ideas from categorical and ordinary firstorder logic, and adapts them to software engineering needs. In the engineering jargon, it ... 
Fusing a Transformation Language with an Open Compiler
(Elsevier, 20080401)Program transformation systems provide powerful analysis and transformation frameworks as well as concise languages for language processing, but instantiating them for every subject language is an arduous task, most often ... 
The Second Rewrite Engines Competition
(Elsevier, 20090629)The Second Rewrite Engines Competition (REC) was celebrated as part of the 7th Workshop on Rewriting Logic and its Applications (WRLA 2008). In this edition of the competition participated five systems, namely ASF+SDF, ... 
DomainSpecific Languages for Composable Editor Plugins
(Elsevier, 20100917)Modern IDEs increase developer productivity by incorporating many different kinds of editor services. These can be purely syntactic, such as syntax highlighting, code folding, and an outline for navigation; or they can be ... 
Exploring Subexponential Parameterized Complexity of Completion Problems
(Schloss Dagstuhl  LeibnizZentrum fuer Informatik, 20140219)Let F be a family of graphs. In the FCompletion problem, we are given an nvertex 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 ... 
On cutwidth parameterized by vertex cover
(Springer, 201404)We study the CUTWIDTH problem, where the input is a graph G, and the objective is find a linear layout of the vertices that minimizes the maximum number of edges intersected by any vertical line inserted between two ... 
Parameterized complexity of Eulerian deletion problems
(Springer, 201401)We study a family of problems where the goal is to make a graph Eulerian, i.e., connected and with all the vertices having even degrees, by a minimum number of deletions. We completely classify the parameterized complexity ...