Browsing Bergen Open Research Archive by Author "Telle, Jan Arne"
Now showing items 111 of 11

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