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øhlensgt. 55
  • Postal Address
    Postboks 7803
    5020 Bergen
Academic article
  • Bodlaender, Hans L.; Jaffke, Lars; Telle, Jan Arne. 2020. Typical Sequences Revisited - Computing Width Parameters of Graphs. Leibniz International Proceedings in Informatics. 57:1-57:16.
  • Jaffke, Lars; Kwon, O-Joung; Telle, Jan Arne. 2020. Mim-Width II. The Feedback Vertex Set Problem. Algorithmica. 118-145.
  • Telle, Jan Arne; Hernández-Orallo, José; Ferri, Cesar. 2019. The teaching size: computable teachers and learners for universal languages. Machine Learning. 1653-1675.
  • Jaffke, Lars; Kwon, O-Joung; Strømme, Torstein J. F.; Telle, Jan Arne. 2019. Mim-Width III. Graph powers and generalized distance domination problems. Theoretical Computer Science. 216-236.
  • Jaffke, Lars; Kwon, O-joung; Telle, Jan Arne. 2019. Mim-Width I. Induced Path Problems. Discrete Applied Mathematics.
  • Høgemo, Svein; Telle, Jan Arne; Vågset, Erlend Raa. 2019. Linear MIM-Width of Trees. Lecture Notes in Computer Science (LNCS). 218-231.
  • Jaffke, Lars; Kwon, O-Joung; Telle, Jan Arne. 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.
  • Jeong, Jisu; Sæther, Sigve Hortemo; Telle, Jan Arne. 2018. Maximum matching width: New characterizations and a fast algorithm for dominating set. Discrete Applied Mathematics. 114-124.
  • Telle, Jan Arne; Villanger, Yngve. 2018. FPT algorithms for domination in sparse graphs and beyond. Theoretical Computer Science. 1-7.
  • Jaffke, Lars; Kwon, O-Joung; Telle, Jan Arne. 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.
  • Kang, Dong Yeap; Kwon, O-Joung; Strømme, Torstein J.; Telle, Jan Arne. 2017. A width parameter useful for chordal and co-comparability graphs. Lecture Notes in Computer Science (LNCS). 93-105.
  • Kang, Dong Yeap; Kwon, O-Joung; Strømme, Torstein J.; Telle, Jan Arne. 2017. A width parameter useful for chordal and co-comparability graphs. Theoretical Computer Science. 1-17.
  • Gaspers, Serge; Papadimitriou, C.; Sæther, Sigve Hortemo; Telle, Jan Arne. 2016. On satisfiability problems with a linear structure. Leibniz International Proceedings in Informatics. 1-14.
  • Telle, Jan Arne; Kratochvil, Jan; tesar, marek. 2016. Computational complexity of covering three-vertex multigraphs. Theoretical Computer Science.
  • Sæther, Sigve Hortemo; Telle, Jan Arne; Vatshelle, Martin. 2015. Solving #SAT and MaxSAT by dynamic programming. The journal of artificial intelligence research. 59-82.
  • Bodlaender, Hans; Heggernes, Pinar; Telle, Jan Arne. 2015. Recognizability Equals Definability for Graphs of Bounded Treewidth and Bounded Chordality. Electronic Notes in Discrete Mathematics.
  • Jeong, Jisu; Sæther, Sigve Hortemo; Telle, Jan Arne. 2015. Maximum matching width: New characterizations and a fast algorithm for dominating set. Leibniz International Proceedings in Informatics. 212-223.
  • Telle, Jan Arne; Sæther, Sigve Hortemo; jeong, jisu. 2015. Maximum Matching Width: New Characterizations and a Fast Algorithm for Dominating Set. Lecture Notes in Computer Science (LNCS).
  • Sæther, Sigve Hortemo; Telle, Jan Arne. 2015. Between treewidth and clique-width. Algorithmica. 36 pages.
  • Bruhn, Henning; Charbit, Pierre; Schaudt, Oliver; Telle, Jan Arne. 2014. The graph formulation of the union-closed sets conjecture. European journal of combinatorics (Print). 210-219.
  • Telle, Jan Arne; Vatshelle, Martin; Sæther, Sigve Hortemo. 2014. Solving MAXSAT and #SAT on structured CNF formulas. Lecture Notes in Computer Science (LNCS). 16-31.
  • Kratochvil, Jan; Telle, Jan Arne; Tesař, Marek. 2014. Computational complexity of covering three-vertex multigraphs. Lecture Notes in Computer Science (LNCS). 493-504.
  • Telle, Jan Arne; Sæther, Sigve Hortemo. 2014. Between treewidth and clique-width. Lecture Notes in Computer Science (LNCS). 396-407.
  • Rabinovich, Yuri; Telle, Jan Arne; Vatshelle, Martin. 2013. Upper bounds on boolean-width with applications to exact algorithms. Lecture Notes in Computer Science (LNCS). 308-320.
  • Telle, Jan Arne; Suchy, Ondra; Bui-Xuan, Binh-Minh; Vatshelle, Martin. 2013. Feedback vertex set on graphs of low cliquewidth. European journal of combinatorics (Print). 666-679.
  • Bui-Xuan, Binh-Minh; Telle, Jan Arne; Vatshelle, Martin. 2013. Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems. Theoretical Computer Science. 66-76.
  • Telle, Jan Arne; Villanger, Yngve. 2013. Connecting Terminals and 2-Disjoint Connected Subgraphs. Lecture Notes in Computer Science (LNCS). 418-428.
  • Telle, Jan Arne. 2012. Mike Fellows: Weaving the web of mathematics and adventure. Lecture Notes in Computer Science (LNCS). 74-79.
  • Telle, Jan Arne; Vatshelle, Martin; Hvidevold, Eivind; Sharmin, Sadia. 2012. Finding good decompositions for dynamic programming on dense graphs. Lecture Notes in Computer Science (LNCS). 219-231.
  • Telle, Jan Arne; Villanger, Yngve. 2012. FPT algorithms for domination in biclique-free graphs. Lecture Notes in Computer Science (LNCS). 802-812.
  • Meister, Daniel; Telle, Jan Arne. 2012. Chordal digraphs. Theoretical Computer Science. 73-83.
  • Fomin, Fedor; Kratochvil, Jan; Lokshtanov, Daniel; Mancini, Federico; Telle, Jan Arne. 2011. On the Complexity of Reconstructing H-Free Graphs from Their Star Systems. Journal of Graph Theory. 113-124.
  • Bui-Xuan, Binh-Minh; Telle, Jan Arne; Vatshelle, Martin. 2011. Boolean-width of graphs. Theoretical Computer Science. 5187-5204.
  • Meister, Daniel; Telle, Jan Arne; Vatshelle, Martin. 2010. Recognizing digraphs of Kelly-width 2. Discrete Applied Mathematics. 741-746.
  • Adler, Isolde Marianne; Bui-Xuan, Binh-Minh; Telle, Jan Arne; Rabinovich, Yuri; Renault, Gabriel; Vatshelle, Martin. 2010. On the boolean-width of a graph: structure and applications. Lecture Notes in Computer Science (LNCS). 159-170.
  • Bui-Xuan, Binh-Minh; Telle, Jan Arne; Vatshelle, Martin. 2010. H-join decomposable graphs and algorithms with runtime single exponential in rankwidth. Discrete Applied Mathematics. 809-819.
  • Heggernes, Pinar; Lokshtanov, Daniel; Nederlof, Jesper; Paul, Christophe; Telle, Jan Arne. 2010. Generalized graph clustering: recognizing (p,q)-cluster graphs. Lecture Notes in Computer Science (LNCS). 171-183.
  • Dorn, Frederic ; Telle, Jan Arne. 2009. Semi-nice tree-decompositions: The best of branchwidth, treewidth and pathwidth with one algorithm. Discrete Applied Mathematics. 2737-2746.
  • Villanger, Yngve; Heggernes, Pinar; Paul, Christophe; Telle, Jan Arne. 2009. Interval completion is fixed parameter tractable. SIAM journal on computing (Print). 2007-2020.
  • Telle, Jan Arne; Bui-Xuan, Binh-Minh; Vatshelle, Martin. 2009. Feedback Vertex Set on Graphs of low Cliquewidth. Lecture Notes in Computer Science (LNCS). 113-124.
  • Paul, Christophe; Telle, Jan Arne. 2009. Edge-maximal graphs of branchwidth k: The k-branches. Discrete Mathematics. 1467-1475.
  • Meister, Daniel; Telle, Jan Arne. 2009. Chordal digraphs. Lecture Notes in Computer Science (LNCS). 273-284.
  • Paul, Christophe; Telle, Jan Arne. 2009. Branchwidth of chordal graphs. Discrete Applied Mathematics. 2718-2725.
  • Bui-Xuan, Binh-Minh; Telle, Jan Arne; Vatshelle, Martin. 2009. Boolean-width of graphs. Lecture Notes in Computer Science (LNCS). 61-74.
  • Fomin, Fedor; Kratochvil, Jan; Lokshtanov, Daniel; Mancini, Federico; Telle, Jan Arne. 2008. On the complexity of reconstructing H-free graphs from their Star Systems. Lecture Notes in Computer Science (LNCS). 194-205.
  • Fiala, Jiří; Paulusma, Daniel; Telle, Jan Arne. 2008. Locally constrained graph homomorphisms and equitable partitions. European journal of combinatorics (Print). 850-880.
  • Fellows, Michael R.; Meister, Daniel; Rosamond, Frances A.; Sritharan, R.; Telle, Jan Arne. 2008. Leaf Powers and Their Properties: Using the Trees. Lecture Notes in Computer Science (LNCS). 402-413.
  • Sloper, Christian; Telle, Jan Arne. 2008. An overview of techniques for designing parameterized algorithms. Computer journal. 122-136.
  • Telle, Jan Arne; Wood, David. 2007. Planar decompositions and the crossing number of graphs with an excluded minor. New York journal of mathematics. 117-146.
  • Wood, David; Telle, Jan Arne. 2007. Planar Decompositions and the Crossing Number of Graphs with an Excluded Minor. Lecture Notes in Computer Science (LNCS). 150-161.
  • Telle, Jan Arne; Meister, Daniel; Vatshelle, Martin. 2007. Characterization and recognition of graphs of bounded Kelly-width. Lecture Notes in Computer Science (LNCS). 270-279.
  • Dorn, Frederic Bernard; Telle, Jan Arne. 2006. Two birds with one stone: the best of branchwidth and treewidth with one algorithm. Lecture Notes in Computer Science (LNCS). 386-397.
  • Sloper, Christian; Telle, Jan Arne. 2006. Towards a taxonomy of techniques for designing parameterized algorithms. Lecture Notes in Computer Science (LNCS). 251-263.
  • Wood, David; Telle, Jan Arne. 2006. Planar decompositions and the crossing number of graphs with an excluded minor. Lecture Notes in Computer Science (LNCS). 10 pages.
  • Gebremedhin, Assefaw Hadish Hadish; Gustedt, Jens; Essaïdi, Mohamed; Lassous, Isabelle Guérin; Telle, Jan Arne. 2006. PRO: A Model for the Design and Analysis of Efficient and Scalable Parallel Algorithms. Nordic Journal of Computing. 22 pages.
  • Telle, Jan Arne; Proskurowski, Andrzej; Paul, Christophe. 2006. Generating graphs of bounded branchwidth. Lecture Notes in Computer Science (LNCS). 10 pages.
  • Heggernes, Pinar; Telle, Jan Arne; Villanger, Yngve. 2006. Computing Minimal Triangulations in Time O(nα log n) = o(n2.376). SIAM Journal on Discrete Mathematics. 900-913.
  • Telle, Jan Arne. 2005. Tree-decompositions of small pathwidth. Discrete Applied Mathematics. 210-218.
  • Paul, Christophe; Telle, Jan Arne. 2005. New tools and simpler algorithms for branchwidth. Lecture Notes in Computer Science (LNCS). 379-390.
  • Telle, Jan Arne; Fiala, Jiri; Paulusma, Daniel. 2005. Matrix and graph orders derived from locally constrained graph homomorphisms. Lecture Notes in Computer Science (LNCS). 340-351.
  • Telle, Jan Arne; Paul, Christophe. 2005. Edge-maximal graphs of branchwidth k. Electronic Notes in Discrete Mathematics. 363-368.
  • Fiala, Jiri; Paulusma, Daniel; Telle, Jan Arne. 2005. Algorithms for comparability of matrices in partial orders imposed by graph homomorphisms. Lecture Notes in Computer Science (LNCS). 115-126.
  • Bodlaender, Hans; Telle, Jan Arne. 2004. Space-efficient construction variants of dynamic programming. Nordic Journal of Computing. 374-385.
  • Hedetniemi, Sandra M.; Hedetniemi, Stephen T.; McRae, Alice A.; Parks, Dee; Telle, Jan Arne. 2004. Iterated colorings of graphs. Discrete Mathematics. 81-108.
  • Fomin, Fedor; Heggernes, Pinar; Telle, Jan Arne. 2004. Graph searching, elimination trees, and a generalization of bandwidth. Algorithmica. 73-87.
  • Fellows, Michael; Heggernes, Pinar; Rosamond, Frances; Sloper, Christian; Telle, Jan Arne. 2004. Finding k disjoint triangles in an arbitrary graph. Lecture Notes in Computer Science (LNCS). 235-244.
  • Gustedt, J; Telle, Jan Arne. 2004. A work-optimal coarse-grained PRAM algorithm for lexicographically first maximal independent set. Lecture Notes in Computer Science (LNCS). 125-136.
  • Halldorsson, M; Korsatz, G; Proskurowski, A; Salman, R; Shachnai, H; Telle, Jan Arne. 2003. Multi-coloring Trees. Information and Computation. 113-129.
  • Gebremedhin, Assefaw Hadish; Guerrin-Lassous, Isabelle; Gustedt, Jens; Telle, Jan Arne. 2003. Graph coloring on a coarse grained multiprocessor. Discrete Applied Mathematics. 179-198.
  • Fiala, Jiri; Heggernes, Pinar; Kristiansen, Petter; Telle, Jan Arne. 2003. Generalized H-coloring and H-covering of Trees. Nordic Journal of Computing. 206-224.
  • Blair, Jean; Heggernes, Pinar; Telle, Jan Arne. 2001. A Practical Algorithm for Making Filled Graphs Minimal. Theoretical Computer Science. 125-141.
  • Telle, Jan Arne; Proskurowski, A. 1999. Classes of graphs with restricted interval models. Discrete mathematics and theoretical computer science. 135-144.
  • Heggernes, Pinar; Telle, Jan Arne. 1998. Partitioning graphs into generalized dominating sets. Nordic Journal of Computing. 128-142.
  • Kratochvil, J.; Proskurowski, Andrzej; Telle, Jan Arne. 1998. Complexity of graph covering problems. Nordic Journal of Computing. 173-195.
  • Kratochvil, J.; Proskurowski, Andrzej; Telle, Jan Arne. 1997. Covering regular graphs. Journal of combinatorial theory. Series B (Print). 1-16.
  • Telle, Jan Arne; Proskurowski, Andrzej. 1997. Algorithms for vertex partitioning problems on partial k-trees. SIAM Journal on Discrete Mathematics. 529-550.
  • Telle, Jan Arne; Lo, V.; Zhong, X. 1996. Parallel divide-and-conquer on meshes. IEEE Transactions on Parallel and Distributed Systems. 1049-1059.
  • Telle, Jan Arne. 1996. A linear time algorithm to find a graph with prescribed degrees of adjacent vertices. TR.
  • Telle, Jan Arne. 1994. Complexity of Domination-type Problems in Graphs. Computing. 157-171.
Report
  • Gebremedhin, Assefaw Hadish; Guerin Lassous, Isabelle; Gustedt, Jens; Telle, Jan Arne. 2001. PRO: a model for Parallel Resource-Optimal computation. 218. 218. .
  • Hedetniemi, Sandra; Hedetniemi, Stephen; Mcrae, Alice; Parks, Dee; Telle, Jan Arne. 1997. Iterated Coloring of Graphs. 134. 134. .
  • Halldórsson, Magnús M.; Kratochvil, Jan; Telle, Jan Arne. 1997. Independent sets with Domination Constraints. 138. 138. .
  • Blair, Jean R. S.; Heggernes, Pinar; Telle, Jan Arne. 1996. Making an arbitrary filled graph minimal by removing fill edges. 115. 115. .
  • Proskurowski, Andrzej; Telle, Jan Arne. 1996. From bandwith k to pathwidth k. .
  • Heggernes, Pinar; Telle, Jan Arne. 1995. Partitioning Graphs Into Generalized Domination Sets. 107. 107. .
  • Heggernes, Pinar; Aspvall, Bengt; Telle, Jan Arne. 1995. A simple cubic algorithm for computing minimum height elimination trees for interval graphs. 103. 103. .
Popular scientific lecture
  • Telle, Jan Arne. 1994. Vertex Partitioning Problems on Partial k-Trees.
Academic lecture
  • Telle, Jan Arne; Ferri, Cesar; Hernández-Orallo, José. 2019. Teaching Explanations by Examples .
  • Fomin, Fedor; Heggernes, Pinar; Telle, Jan Arne. 2003. Graph searching, elimination trees, and a generalization of bandwidth.
  • Gustedt, Jens; Telle, Jan Arne. 2003. A work-optimal coarse-grained PRAM algorithm for Lexicographically First Maximal Independent Set.
  • Telle, Jan Arne; Mæhle, Ole Aleksander; Gustedt, Jens. 2002. The treewidth of Java programs.
  • Telle, Jan Arne; Gebremedhin, Assefaw Hadish; Gustedt, Jens. 2002. PRO: A model for Parallel Resource-Optimal computation.
  • Fiala, Jiri; Heggernes, Pinar; Kristiansen, Petter; Telle, Jan Arne. 2002. Generalized H-coloring and H-covering of Trees.
  • Aspwall, Bengt; Proskurowski, Andrzej; Telle, Jan Arne. 1999. Memory requirements for table computations in partial k-tree algoritms.
  • Aspwall, Bengt; Proskurowski, Andrzej; Telle, Jan Arne. 1998. Memory requirements for table computations in partial k-tree algoritms.
  • Bodlaender, H.; Gustedt, J.; Telle, Jan Arne. 1998. Linear-time rewgister allocation for a fixed number of registers.
  • Halldórsson, Mágnus; Kratochvil, Jan; Telle, Jan Arne. 1998. Independent sets with domination constraints.
  • Proskurowski, Andrzej; Telle, Jan Arne. 1998. From bandwidth k to pathwidth k.
  • Aspvall, Bengt; Proskurowski, Andrzej; Telle, Jan Arne. 1997. Memory requirements for table computations in partial k-tree algorithms.
  • Kratochvil, Jan; Proskurowski, Andrzej; Telle, Jan Arne. 1997. Complexity of colored graph covers I. Colored directed multigraphs.
  • Blair, Jean; Heggernes, Pinar; Telle, Jan Arne. 1996. Making an arbitrary filled graph minimal by removing fill edges.
  • Henzinger, M. R.; Telle, Jan Arne. 1996. Faster algorithms for the nonemptiness of Streett automata and for communication protocol prunin.
  • Heggernes, Pinar; Telle, Jan Arne. 1995. Partitioning Graphs Into Generalized Domination Sets.
  • Kratochvil, J.; Proskurowski, A.; Telle, Jan Arne. 1994. Complexity of Graph Covering Problems.
Editorial
  • Nesetril, Jaroslav; Serra, Oriol; Telle, Jan Arne. 2015. Preface. Electronic Notes in Discrete Mathematics. 1-2.
  • Owe, Olaf; Steffen, Martin; Telle, Jan Arne. 2013. The 18th International Symposium on Fundamentals of Computation Theory. Information and Computation. 1-2.
Reader opinion piece
  • Telle, Jan Arne. 2007. Om Elster-saken: Bløffmakeri? Morgenbladet.
Academic anthology/Conference proceedings
  • Owe, Olaf; Steffen, Martin; Telle, Jan Arne. 2011. Fundamentals of Computation Theory - 18th International Symposium, FCT 2011, Oslo, Norway, August 22-25, 2011. Springer.
Feature article
  • Telle, Jan Arne; Drange, Pål Grønås. 2012. Sådde frøene til datarevolusjonen. Bergens Tidende.
  • Telle, Jan Arne. 2012. Nå kan robotene snakke sammen. Bergens Tidende.
  • Telle, Jan Arne. 2012. Jakten på absolutt visshet. Bergens Tidende.
  • Telle, Jan Arne; Drange, Pål Grønås. 2012. Er du venn med en robot? Morgenbladet.
Doctoral dissertation
  • Sæther, Sigve Hortemo. 2015. Choice of parameter for DP-based FPT algorithms: four case studies.
  • Telle, Jan Arne. 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
  • Heggernes, Pinar; Paul, Christophe; Telle, Jan Arne; Villanger, Yngve. 2007. Interval completion with few edges. 8 pages.
  • Heggernes, Pinar; Telle, Jan Arne; Villanger, Yngve. 2005. Computing Minimal Triangulations in Time O(nα log n) = o(n2.376). 10 pages.
Foreword
  • Owe, Olaf; Telle, Jan Arne; Steffen, Martin. 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)