• Computing minimal triangulation in Time o(n^2.376) 

      Heggernes, Pinar; Telle, Jan Arne; Villanger, Yngve (Journal article, 2005)
    • Finding k Disjoint Triangles in an Arbitrary Graph 

      Fellows, Mike; Heggernes, Pinar; Rosamond, Frances; Sloper, Christian; Telle, Jan Arne (Conference object, 2004)
    • Finite and Confident Teaching in Expectation: Sampling from Infinite Concept Classes 

      Hernández-Orallo, José; Telle, Jan Arne (Frontiers in Artificial Intelligence and Applications;325, Chapter, 2020)
      We investigate the teaching of infinite concept classes through the effect of the learning prior (which is used by the learner to derive posteriors giving preference of some concepts over others and by the teacher to devise ...
    • Hierarchical clusterings of unweighted graphs 

      Høgemo, Svein; Paul, Christophe; Telle, Jan Arne (Journal article; Peer reviewed, 2020)
      We study the complexity of finding an optimal hierarchical clustering of an unweighted similarity graph under the recently introduced Dasgupta objective function. We introduce a proof technique, called the normalization ...
    • Maximum matching width: New characterizations and a fast algorithm for dominating set 

      Jeong, Jisu; Sæther, Sigve Hortemo; Telle, Jan Arne (Conference object; Peer reviewed; Journal article, 2015)
      We give alternative definitions for maximum matching width, e.g., a graph G has mmw(G) <= k if and only if it is a subgraph of a chordal graph H and for every maximal clique X of H there exists A,B,C \subseteq X with A ...
    • Mim-Width II. The Feedback Vertex Set Problem 

      Jaffke, Lars; Kwon, O-Joung; Telle, Jan Arne (Peer reviewed; Journal article, 2020)
      We give a first polynomial-time algorithm for (WEIGHTED) FEEDBACK VERTEX SET on graphs of bounded maximum induced matching width (mim-width). Explicitly, given a branch decomposition of mim-width w, we give an nO(w)-time ...
    • Mim-Width III. Graph powers and generalized distance domination problems 

      Telle, Jan Arne; Jaffke, Lars; Strømme, Torstein Jarl Fagerbakke; Kwon, O-Joung (Peer reviewed; Journal article, 2019)
      We generalize the family of (σ,ρ) problems and locally checkable vertex partition problems to their distance versions, which naturally captures well-known problems such as Distance-r Dominating Set and Distance-r Independent ...
    • Typical Sequences Revisited - Computing Width Parameters of Graphs 

      Bodlaender, Hans L.; Jaffke, Lars; Telle, Jan Arne (Journal article; Peer reviewed, 2021)
      In this work, we give a structural lemma on merges of typical sequences, a notion that was introduced in 1991 [Lagergren and Arnborg, Bodlaender and Kloks, both ICALP 1991] to obtain constructive linear time parameterized ...
    • Typical Sequences Revisited – Computing Width Parameters of Graphs 

      Bodlaender, Hans L.; Jaffke, Lars; Telle, Jan Arne (Journal article; Peer reviewed, 2020)
      In this work, we give a structural lemma on merges of typical sequences, a notion that was introduced in 1991 [Lagergren and Arnborg, Bodlaender and Kloks, both ICALP 1991] to obtain constructive linear time parameterized ...