Blar i Department of Informatics på forfatter "Telle, Jan Arne"

Viser treff 1-14 av 14

    • Classes of Intersection Digraphs with Good Algorithmic Properties 

      Jaffke, Lars; Kwon, O-joung; Telle, Jan Arne (Journal article; Peer reviewed, 2022)
      While intersection graphs play a central role in the algorithmic analysis of hard problems on undirected graphs, the role of intersection digraphs in algorithms is much less understood. We present several contributions ...

    • Classes of intersection digraphs with good algorithmic properties 

      Jaffke, Lars; Kwon, O-joung; Telle, Jan Arne (Journal article; Peer reviewed, 2023)
      While intersection graphs play a central role in the algorithmic analysis of hard problems on undirected graphs, the role of intersection digraphs in algorithms is much less understood. We present several contributions ...

    • 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 (Journal article; Peer reviewed, 2004)
      We consider the NP-complete problem of deciding whether an input graph on n vertices has k vertex-disjoint copies of a fixed graph H. For H=K 3 (the triangle) we give an O(22klog k + 1.869k n 2) algorithm, and for general ...

    • 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 (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 ...

    • Node Multiway Cut and Subset Feedback Vertex Set on Graphs of Bounded Mim-Width 

      Bergougnoux, Benjamin; Papadopoulos, Charis; Telle, Jan Arne (Journal article; Peer reviewed, 2022)
      The two weighted graph problems Node Multiway Cut (NMC) and Subset Feedback Vertex Set (SFVS) both ask for a vertex set of minimum total weight, that for NMC disconnects a given set of terminals, and for SFVS intersects ...

    • On Dasgupta’s Hierarchical Clustering Objective and Its Relation to Other Graph Parameters 

      Høgemo, Svein; Bergougnoux, Benjamin; Brandes, Ulrik; Paul, Christophe; Telle, Jan Arne (Journal article; Peer reviewed, 2021)
      The minimum height of vertex and edge partition trees are well-studied graph parameters known as, for instance, vertex and edge ranking number. While they are NP-hard to determine in general, linear-time algorithms exist ...

    • The Perfect Matching Cut Problem Revisited 

      Telle, Jan Arne; Le, Van Bang (Journal article; Peer reviewed, 2021)
      In a graph, a perfect matching cut is an edge cut that is a perfect matching. perfect matching cut (pmc) is the problem of deciding whether a given graph has a perfect matching cut, and is known to be NP -complete. We ...

    • 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 ...