• K-Core Decomposition with CUDA 

      Morken, Ole Magnus Mæland (Master thesis, 2020-12-18)
    • K-packing and K-domination on tree graphs 

      Mjelde, Morten (Master thesis, 2004)
    • Kernel(s) for Problems with No Kernel: On Out-Trees with Many Leaves 

      Fernau, Henning; Fomin, Fedor; Lokshtanov, Daniel; Raible, Daniel; Saurabh, Saket; Villanger, Yngve (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 of Graph Hamiltonicity: Proper H-Graphs 

      Chaplick, Steven; Fomin, Fedor; Golovach, Petr; Knop, Dusan; Zeman, Peter (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 

      Strømme, Torstein Jarl Fagerbakke (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 

      Fomin, Fedor; Golovach, Petr (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 

      Fomin, Fedor; Golovach, Petr (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 ...
    • Kernels of digraphs with finitely many ends 

      Walicki, Michal (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 

      Rückmann, Jan-Joachim; Flåm, Sjur Didrik (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 

      Bliznets, Ivan; Fomin, Fedor; Pilipczuk, Michal Pawel; Villanger, Yngve (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) ...
    • Learning Description Logic Ontologies: Five Approaches. Where Do They Stand? 

      Ozaki, Ana (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 Possibilistic Logic Theories 

      Persia, Cosimo Damiano (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), ...
    • The Legendre Symbol and the Modulo-2 Operator in Symmetric Schemes over Fnp: Preimage Attack on Full Grendel 

      Grassi, Lorenzo; Khovratovich, Dmitry; Rønjom, Sondre; Schofnegger, Markus (Journal article; Peer reviewed, 2022)
      Motivated by modern cryptographic use cases such as multi-party computation (MPC), homomorphic encryption (HE), and zero-knowledge (ZK) protocols, several symmetric schemes that are efficient in these scenarios have recently ...
    • Lex M versus MCS-M 

      Villanger, Yngve (Journal article, 2006)
    • Linear dependencies between non-uniform distributions in DES 

      Fauskanger, Stian (Master thesis, 2014-05-30)
      Davies and Murphy explained some non-uniform distributions of the output from pairs and triplets of S-boxes 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 

      Ovnerud, Torbjørn (Master thesis, 2000)
    • Localizing Cell Towers from Crowdsourced Measurements 

      Rusvik, Johan Alexander Nordstrand (Master thesis, 2015-06-01)
      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 Context-Category Independent Basics 

      Wolter, Uwe Egbert (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 

      Fomin, Fedor; Golovach, Petr; Sagunov, Danil; Simonov, Kirill (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 2-connected graph G with the minimum vertex degree ...
    • Long-read single-molecule RNA structure sequencing using nanopore 

      Tilahun Bizuayehu, Teshome; Labun, Kornel; Jakubec, Martin; Jefimov, Kirill; Niazi, Adnan Muhammad; Valen, Eivind Dale (Journal article; Peer reviewed, 2022)
      RNA molecules can form secondary and tertiary structures that can regulate their localization and function. Using enzymatic or chemical probing together with high-throughput sequencing, secondary structure can be mapped ...