Home
Jan Arne Telle's picture

Jan Arne Telle

Professor
  • E-mailJan.Arne.Telle@uib.no
  • Phone+47 55 58 40 36
  • Visitor Address
    HIB - Thormøhlens gate 55
  • Postal Address
    Postboks 7803
    5020 Bergen
Academic article
  • Show author(s) (2021). Typical Sequences Revisited -- Computing Width Parameters of Graphs. Theory of Computing Systems.
  • Show author(s) (2020). Typical Sequences Revisited - Computing Width Parameters of Graphs. Leibniz International Proceedings in Informatics. 57:1-57:16.
  • Show author(s) (2020). Mim-Width II. The Feedback Vertex Set Problem. Algorithmica. 118-145.
  • Show author(s) (2020). Hierarchical clusterings of unweighted graphs. Leibniz International Proceedings in Informatics. 47:1-47:13.
  • Show author(s) (2019). The teaching size: computable teachers and learners for universal languages. Machine Learning. 1653-1675.
  • Show author(s) (2019). Mim-Width III. Graph powers and generalized distance domination problems. Theoretical Computer Science. 216-236.
  • Show author(s) (2019). Mim-Width I. Induced Path Problems. Discrete Applied Mathematics.
  • Show author(s) (2019). Linear MIM-Width of Trees. Lecture Notes in Computer Science (LNCS). 218-231.
  • Show author(s) (2018). Polynomial-time algorithms for the Longest Induced Path and Induced Disjoint Paths problems on graphs of bounded mim-width. Leibniz International Proceedings in Informatics. 1-13.
  • Show author(s) (2018). Maximum matching width: New characterizations and a fast algorithm for dominating set. Discrete Applied Mathematics. 114-124.
  • Show author(s) (2018). FPT algorithms for domination in sparse graphs and beyond. Theoretical Computer Science. 1-7.
  • Show author(s) (2018). A Unified Polynomial-Time Algorithm for Feedback Vertex Set on Graphs of Bounded Mim-Width. Leibniz International Proceedings in Informatics. 42:1-42:14.
  • Show author(s) (2017). A width parameter useful for chordal and co-comparability graphs. Theoretical Computer Science. 1-17.
  • Show author(s) (2017). A width parameter useful for chordal and co-comparability graphs. Lecture Notes in Computer Science (LNCS). 93-105.
  • Show author(s) (2016). On satisfiability problems with a linear structure. Leibniz International Proceedings in Informatics. 1-14.
  • Show author(s) (2016). Computational complexity of covering three-vertex multigraphs. Theoretical Computer Science.
  • Show author(s) (2015). Solving #SAT and MaxSAT by dynamic programming. The journal of artificial intelligence research. 59-82.
  • Show author(s) (2015). Recognizability Equals Definability for Graphs of Bounded Treewidth and Bounded Chordality. Electronic Notes in Discrete Mathematics.
  • Show author(s) (2015). Maximum matching width: New characterizations and a fast algorithm for dominating set. Leibniz International Proceedings in Informatics. 212-223.
  • Show author(s) (2015). Maximum Matching Width: New Characterizations and a Fast Algorithm for Dominating Set. Lecture Notes in Computer Science (LNCS).
  • Show author(s) (2015). Between treewidth and clique-width. Algorithmica. 36 pages.
  • Show author(s) (2014). The graph formulation of the union-closed sets conjecture. European journal of combinatorics (Print). 210-219.
  • Show author(s) (2014). Solving MAXSAT and #SAT on structured CNF formulas. Lecture Notes in Computer Science (LNCS). 16-31.
  • Show author(s) (2014). Computational complexity of covering three-vertex multigraphs. Lecture Notes in Computer Science (LNCS). 493-504.
  • Show author(s) (2014). Between treewidth and clique-width. Lecture Notes in Computer Science (LNCS). 396-407.
  • Show author(s) (2013). Upper bounds on boolean-width with applications to exact algorithms. Lecture Notes in Computer Science (LNCS). 308-320.
  • Show author(s) (2013). Feedback vertex set on graphs of low cliquewidth. European journal of combinatorics (Print). 666-679.
  • Show author(s) (2013). Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems. Theoretical Computer Science. 66-76.
  • Show author(s) (2013). Connecting Terminals and 2-Disjoint Connected Subgraphs. Lecture Notes in Computer Science (LNCS). 418-428.
  • Show author(s) (2012). Mike Fellows: Weaving the web of mathematics and adventure. Lecture Notes in Computer Science (LNCS). 74-79.
  • Show author(s) (2012). Finding good decompositions for dynamic programming on dense graphs. Lecture Notes in Computer Science (LNCS). 219-231.
  • Show author(s) (2012). FPT algorithms for domination in biclique-free graphs. Lecture Notes in Computer Science (LNCS). 802-812.
  • Show author(s) (2012). Chordal digraphs. Theoretical Computer Science. 73-83.
  • Show author(s) (2011). On the Complexity of Reconstructing H-Free Graphs from Their Star Systems. Journal of Graph Theory. 113-124.
  • Show author(s) (2011). Boolean-width of graphs. Theoretical Computer Science. 5187-5204.
  • Show author(s) (2010). Recognizing digraphs of Kelly-width 2. Discrete Applied Mathematics. 741-746.
  • Show author(s) (2010). On the boolean-width of a graph: structure and applications. Lecture Notes in Computer Science (LNCS). 159-170.
  • Show author(s) (2010). H-join decomposable graphs and algorithms with runtime single exponential in rankwidth. Discrete Applied Mathematics. 809-819.
  • Show author(s) (2010). Generalized graph clustering: recognizing (p,q)-cluster graphs. Lecture Notes in Computer Science (LNCS). 171-183.
  • Show author(s) (2009). Semi-nice tree-decompositions: The best of branchwidth, treewidth and pathwidth with one algorithm. Discrete Applied Mathematics. 2737-2746.
  • Show author(s) (2009). Interval completion is fixed parameter tractable. SIAM journal on computing (Print). 2007-2020.
  • Show author(s) (2009). Feedback Vertex Set on Graphs of low Cliquewidth. Lecture Notes in Computer Science (LNCS). 113-124.
  • Show author(s) (2009). Edge-maximal graphs of branchwidth k: The k-branches. Discrete Mathematics. 1467-1475.
  • Show author(s) (2009). Chordal digraphs. Lecture Notes in Computer Science (LNCS). 273-284.
  • Show author(s) (2009). Branchwidth of chordal graphs. Discrete Applied Mathematics. 2718-2725.
  • Show author(s) (2009). Boolean-width of graphs. Lecture Notes in Computer Science (LNCS). 61-74.
  • Show author(s) (2008). On the complexity of reconstructing H-free graphs from their Star Systems. Lecture Notes in Computer Science (LNCS). 194-205.
  • Show author(s) (2008). Locally constrained graph homomorphisms and equitable partitions. European journal of combinatorics (Print). 850-880.
  • Show author(s) (2008). Leaf Powers and Their Properties: Using the Trees. Lecture Notes in Computer Science (LNCS). 402-413.
  • Show author(s) (2008). An overview of techniques for designing parameterized algorithms. Computer journal. 122-136.
  • Show author(s) (2007). Planar decompositions and the crossing number of graphs with an excluded minor. New York journal of mathematics. 117-146.
  • Show author(s) (2007). Planar Decompositions and the Crossing Number of Graphs with an Excluded Minor. Lecture Notes in Computer Science (LNCS). 150-161.
  • Show author(s) (2007). Characterization and recognition of graphs of bounded Kelly-width. Lecture Notes in Computer Science (LNCS). 270-279.
  • Show author(s) (2006). Two birds with one stone: the best of branchwidth and treewidth with one algorithm. Lecture Notes in Computer Science (LNCS). 386-397.
  • Show author(s) (2006). Towards a taxonomy of techniques for designing parameterized algorithms. Lecture Notes in Computer Science (LNCS). 251-263.
  • Show author(s) (2006). Planar decompositions and the crossing number of graphs with an excluded minor. Lecture Notes in Computer Science (LNCS). 10 pages.
  • Show author(s) (2006). PRO: A Model for the Design and Analysis of Efficient and Scalable Parallel Algorithms. Nordic Journal of Computing. 22 pages.
  • Show author(s) (2006). Generating graphs of bounded branchwidth. Lecture Notes in Computer Science (LNCS). 10 pages.
  • Show author(s) (2006). Computing Minimal Triangulations in Time O(nα log n) = o(n2.376). SIAM Journal on Discrete Mathematics. 900-913.
  • Show author(s) (2005). Tree-decompositions of small pathwidth. Discrete Applied Mathematics. 210-218.
  • Show author(s) (2005). New tools and simpler algorithms for branchwidth. Lecture Notes in Computer Science (LNCS). 379-390.
  • Show author(s) (2005). Matrix and graph orders derived from locally constrained graph homomorphisms. Lecture Notes in Computer Science (LNCS). 340-351.
  • Show author(s) (2005). Edge-maximal graphs of branchwidth k. Electronic Notes in Discrete Mathematics. 363-368.
  • Show author(s) (2005). Algorithms for comparability of matrices in partial orders imposed by graph homomorphisms. Lecture Notes in Computer Science (LNCS). 115-126.
  • Show author(s) (2004). Space-efficient construction variants of dynamic programming. Nordic Journal of Computing. 374-385.
  • Show author(s) (2004). Iterated colorings of graphs. Discrete Mathematics. 81-108.
  • Show author(s) (2004). Graph searching, elimination trees, and a generalization of bandwidth. Algorithmica. 73-87.
  • Show author(s) (2004). Finding k disjoint triangles in an arbitrary graph. Lecture Notes in Computer Science (LNCS). 235-244.
  • Show author(s) (2004). A work-optimal coarse-grained PRAM algorithm for lexicographically first maximal independent set. Lecture Notes in Computer Science (LNCS). 125-136.
  • Show author(s) (2003). Multi-coloring Trees. Information and Computation. 113-129.
  • Show author(s) (2003). Graph coloring on a coarse grained multiprocessor. Discrete Applied Mathematics. 179-198.
  • Show author(s) (2003). Generalized H-coloring and H-covering of Trees. Nordic Journal of Computing. 206-224.
  • Show author(s) (2001). A Practical Algorithm for Making Filled Graphs Minimal. Theoretical Computer Science. 125-141.
  • Show author(s) (1999). Classes of graphs with restricted interval models. Discrete mathematics and theoretical computer science. 135-144.
  • Show author(s) (1998). Partitioning graphs into generalized dominating sets. Nordic Journal of Computing. 128-142.
  • Show author(s) (1998). Complexity of graph covering problems. Nordic Journal of Computing. 173-195.
  • Show author(s) (1997). Covering regular graphs. Journal of combinatorial theory. Series B (Print). 1-16.
  • Show author(s) (1997). Algorithms for vertex partitioning problems on partial k-trees. SIAM Journal on Discrete Mathematics. 529-550.
  • Show author(s) (1996). Parallel divide-and-conquer on meshes. IEEE Transactions on Parallel and Distributed Systems. 1049-1059.
  • Show author(s) (1996). A linear time algorithm to find a graph with prescribed degrees of adjacent vertices. TR.
  • Show author(s) (1994). Complexity of Domination-type Problems in Graphs. Computing. 157-171.
Report
  • Show author(s) (2001). PRO: a model for Parallel Resource-Optimal computation. 218. 218. .
  • Show author(s) (1997). Iterated Coloring of Graphs. 134. 134. .
  • Show author(s) (1997). Independent sets with Domination Constraints. 138. 138. .
  • Show author(s) (1996). Making an arbitrary filled graph minimal by removing fill edges. 115. 115. .
  • Show author(s) (1996). From bandwith k to pathwidth k. .
  • Show author(s) (1995). Partitioning Graphs Into Generalized Domination Sets. 107. 107. .
  • Show author(s) (1995). A simple cubic algorithm for computing minimum height elimination trees for interval graphs. 103. 103. .
Popular scientific lecture
  • Show author(s) (1994). Vertex Partitioning Problems on Partial k-Trees.
Academic lecture
  • Show author(s) (2019). Teaching Explanations by Examples .
  • Show author(s) (2003). Graph searching, elimination trees, and a generalization of bandwidth.
  • Show author(s) (2003). A work-optimal coarse-grained PRAM algorithm for Lexicographically First Maximal Independent Set.
  • Show author(s) (2002). The treewidth of Java programs.
  • Show author(s) (2002). PRO: A model for Parallel Resource-Optimal computation.
  • Show author(s) (2002). Generalized H-coloring and H-covering of Trees.
  • Show author(s) (1999). Memory requirements for table computations in partial k-tree algoritms.
  • Show author(s) (1998). Memory requirements for table computations in partial k-tree algoritms.
  • Show author(s) (1998). Linear-time rewgister allocation for a fixed number of registers.
  • Show author(s) (1998). Independent sets with domination constraints.
  • Show author(s) (1998). From bandwidth k to pathwidth k.
  • Show author(s) (1997). Memory requirements for table computations in partial k-tree algorithms.
  • Show author(s) (1997). Complexity of colored graph covers I. Colored directed multigraphs.
  • Show author(s) (1996). Making an arbitrary filled graph minimal by removing fill edges.
  • Show author(s) (1996). Faster algorithms for the nonemptiness of Streett automata and for communication protocol prunin.
  • Show author(s) (1995). Partitioning Graphs Into Generalized Domination Sets.
  • Show author(s) (1994). Complexity of Graph Covering Problems.
Editorial
  • Show author(s) (2015). Preface. Electronic Notes in Discrete Mathematics. 1-2.
  • Show author(s) (2013). The 18th International Symposium on Fundamentals of Computation Theory. Information and Computation. 1-2.
Reader opinion piece
  • Show author(s) (2007). Om Elster-saken: Bløffmakeri? Morgenbladet.
Academic anthology/Conference proceedings
  • Show author(s) (2011). Fundamentals of Computation Theory - 18th International Symposium, FCT 2011, Oslo, Norway, August 22-25, 2011. Springer.
Feature article
  • Show author(s) (2012). Sådde frøene til datarevolusjonen. Bergens Tidende.
  • Show author(s) (2012). Nå kan robotene snakke sammen. Bergens Tidende.
  • Show author(s) (2012). Jakten på absolutt visshet. Bergens Tidende.
  • Show author(s) (2012). Er du venn med en robot? Morgenbladet.
Doctoral dissertation
  • Show author(s) (2015). Choice of parameter for DP-based FPT algorithms: four case studies.
  • Show author(s) (1994). Vertex Partitioning Problems: Characterization, Complexity and Algorithms on Partial K-trees. Dr.Scient. avhandling. University of Oregon, CIS-TR-18-94.
Academic chapter/article/Conference paper
  • Show author(s) (2020). Node Multiway Cut and Subset Feedback Vertex Set on Graphs of Bounded Mim-width.
  • Show author(s) (2020). Finite and Confident Teaching in Expectation: Sampling from Infinite Concept Classes. 8 pages.
  • Show author(s) (2007). Interval completion with few edges. 8 pages.
  • Show author(s) (2005). Computing Minimal Triangulations in Time O(nα log n) = o(n2.376). 10 pages.
Foreword
  • Show author(s) (2011). Preface to the Proceedings of the 18th International Symposium in Fundamentals of Computation Theory FCT 2011.

More information in national current research information system (CRIStin)