Browsing Department of Informatics by Author "Telle, Jan Arne"
Now showing items 114 of 14

Classes of Intersection Digraphs with Good Algorithmic Properties
Jaffke, Lars; Kwon, Ojoung; 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, Ojoung; 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 NPcomplete problem of deciding whether an input graph on n vertices has k vertexdisjoint 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ándezOrallo, 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 ... 
MimWidth II. The Feedback Vertex Set Problem
Jaffke, Lars; Kwon, OJoung; Telle, Jan Arne (Peer reviewed; Journal article, 2020)We give a first polynomialtime algorithm for (WEIGHTED) FEEDBACK VERTEX SET on graphs of bounded maximum induced matching width (mimwidth). Explicitly, given a branch decomposition of mimwidth w, we give an nO(w)time ... 
MimWidth III. Graph powers and generalized distance domination problems
Telle, Jan Arne; Jaffke, Lars; Strømme, Torstein Jarl Fagerbakke; Kwon, OJoung (Peer reviewed; Journal article, 2019)We generalize the family of (σ,ρ) problems and locally checkable vertex partition problems to their distance versions, which naturally captures wellknown problems such as Distancer Dominating Set and Distancer Independent ... 
Node Multiway Cut and Subset Feedback Vertex Set on Graphs of Bounded MimWidth
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 wellstudied graph parameters known as, for instance, vertex and edge ranking number. While they are NPhard to determine in general, lineartime 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 ...