Browsing Department of Informatics by Title
Now showing items 425444 of 927

KCore Decomposition with CUDA
(Master thesis, 20201218) 
Kpacking and Kdomination on tree graphs
(Master thesis, 2004) 
Kernel(s) for Problems with No Kernel: On OutTrees with Many Leaves
(Peer reviewed; Journal article, 2009)The {\sc \(k\)Leaf OutBranching} problem is to find an outbranching, 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 ... 
Kernelization of Graph Hamiltonicity: Proper HGraphs
(Journal article; Peer reviewed, 2021)We obtain new polynomial kernels and compression algorithms for Path Cover and Cycle Cover, the wellknown generalizations of the classical Hamiltonian Path and Hamiltonian Cycle problems. Our choice of parameterization ... 
Kernelization of Vertex Cover by Structural Parameters
(Master thesis, 20150803)In the NPcomplete problem Vertex Cover, one is given a graph G and an integer k and are asked whether there exists a vertex set S ⊆ V (G) with size at most k such that every edge of the graph is incident to a vertex in ... 
Kernelization of Whitney Switches
(Journal article; Peer reviewed, 2020)A fundamental theorem of Whitney from 1933 asserts that 2connected graphs G and H are 2isomorphic, or equivalently, their cycle matroids are isomorphic, if and only if G can be transformed into H by a series of operations ... 
Kernelization of Whitney Switches
(Journal article; Peer reviewed, 2021)A fundamental theorem of Whitney from 1933 asserts that 2connected graphs $G$ and $H$ are 2isomorphic, or equivalently, their cycle matroids are isomorphic if and only if $G$ can be transformed into $H$ by a series of ... 
Kernels of digraphs with finitely many ends
(Journal article; Peer reviewed, 2019)According to Richardson’s theorem, every digraph without directed odd cycles that is either (a) locally finite or (b) rayless has a kernel (an independent subset with an incoming edge from every vertex in ). We generalize ... 
The Lagrangian, constraint qualifications and economics
(Journal article; Peer reviewed, 2022)Considering constrained choice, practitioners and theorists frequently invoke a Lagrangian to generate optimality conditions. Regular use of that vehicle requires, however, some constraint qualification. Yet many economists ... 
Largest chordal and interval subgraphs faster than 2n
(Peer reviewed; Journal article, 20150822)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) ... 
Learning Description Logic Ontologies: Five Approaches. Where Do They Stand?
(Journal article; Peer reviewed, 2020)The quest for acquiring a formal representation of the knowledge of a domain of interest has attracted researchers with various backgrounds into a diverse field called ontology learning. We highlight classical machine ... 
Learning from positive and negative examples: New proof for binary alphabets
(Journal article; Peer reviewed, 2024)One of the most fundamental problems in computational learning theory is the problem of learning a finite automaton A consistent with a finite set P of positive examples and with a finite set N of negative examples. By ... 
Learning Possibilistic Logic Theories
(Doctoral thesis, 20230315)Vi tar opp problemet med å lære tolkbare maskinlæringsmodeller fra usikker og manglende informasjon. Vi utvikler først en ny dyplæringsarkitektur, RIDDLE: Rule InDuction with Deep LEarning (regelinduksjon med dyp læring), ... 
The Legendre Symbol and the Modulo2 Operator in Symmetric Schemes over Fnp: Preimage Attack on Full Grendel
(Journal article; Peer reviewed, 2022)Motivated by modern cryptographic use cases such as multiparty computation (MPC), homomorphic encryption (HE), and zeroknowledge (ZK) protocols, several symmetric schemes that are efficient in these scenarios have recently ... 
Lex M versus MCSM
(Journal article, 2006) 
Linear dependencies between nonuniform distributions in DES
(Master thesis, 20140530)Davies and Murphy explained some nonuniform distributions of the output from pairs and triplets of Sboxes in DES, and how they are completely dependent on some key bits. There are linear dependencies between these ... 
Lineær kompleksitet til produkter av maksimalsekvenser
(Master thesis, 2000) 
Localizing Cell Towers from Crowdsourced Measurements
(Master thesis, 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 ... 
Logics of Statements in ContextCategory Independent Basics
(Journal article; Peer reviewed, 2022)Based on a formalization of open formulas as statements in context, the paper presents a freshly new and abstract view of logics and specification formalisms. Generalizing concepts like sets of generators in Group Theory, ... 
Long Cycles in Graphs: Extremal Combinatorics Meets Parameterized Algorithms
(Journal article; Peer reviewed, 2022)We discuss recent algorithmic extensions of two classic results of extremal combinatorics about long paths in graphs. First, the theorem of Dirac from 1952 asserts that a 2connected graph G with the minimum vertex degree ...