Browsing Department of Informatics by Title
Now showing items 569-588 of 1199
-
K-Core Decomposition with CUDA
(Master thesis, 2020-12-18) -
K-packing and K-domination on tree graphs
(Master thesis, 2004) -
Kernel(s) for Problems with No Kernel: On Out-Trees with Many Leaves
(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 ... -
Kernelization for Balanced Graph Clustering
(Master thesis, 2020-10-03)The problems of Balanced Graph Clustering ask whether it is possible to modify a graph such that it becomes a cluster graph where no cluster has a size larger than a given multiplicative factor or absolute difference ... -
Kernelization for Spreading Points
(Journal article; Peer reviewed, 2023)We consider the following problem about dispersing points. Given a set of points in the plane, the task is to identify whether by moving a small number of points by small distance, we can obtain an arrangement of points ... -
Kernelization of Graph Hamiltonicity: Proper H-Graphs
(Journal article; Peer reviewed, 2021)We obtain new polynomial kernels and compression algorithms for Path Cover and Cycle Cover, the well-known generalizations of the classical Hamiltonian Path and Hamiltonian Cycle problems. Our choice of parameterization ... -
Kernelization of Vertex Cover by Structural Parameters
(Master thesis, 2015-08-03)In the NP-complete 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 2-connected graphs G and H are 2-isomorphic, 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 2-connected graphs $G$ and $H$ are 2-isomorphic, or equivalently, their cycle matroids are isomorphic if and only if $G$ can be transformed into $H$ by a series of ... -
Kernelizing Temporal Exploration Problems
(Journal article; Peer reviewed, 2023)We study the kernelization of exploration problems on temporal graphs. A temporal graph consists of a finite sequence of snapshot graphs 𝒢 = (G₁, G₂, … , G_L) that share a common vertex set but might have different edge ... -
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, 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) ... -
Lattice Sieving With G6K
(Master thesis, 2023-06-01)Recent advances in quantum computing threaten the cryptography we use today. This has led to a need for new cryptographic algorithms that are safe against quantum computers. The American standardization organization NIST ... -
Learning Acquisition Functions for Cost-aware Bayesian Optimization
(Master thesis, 2023-08-01) -
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 Horn envelopes via queries from language models
(Journal article; Peer reviewed, 2024)We present an approach for systematically probing a trained neural network to extract a symbolic abstraction of it, represented as a Boolean formula. We formulate this task within Angluin's exact learning framework, where ... -
Learning Possibilistic Logic Theories
(Doctoral thesis, 2023-03-15)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), ... -
Least Surprising Dataflows in Constraint Based Graphical User Interfaces
(Master thesis, 2024-06-10)There are many approaches for implementing Graphical User Interfaces (GUI) since programming GUIs is a difficult and complex task. This thesis focuses on a prticular GUI development approach, one based on multi-way dataflow ...