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
Books
  • Owe, Olaf; Steffen, Martin; Telle, Jan Arne. 2011. Fundamentals of Computation Theory - 18th International Symposium, FCT 2011, Oslo, Norway, August 22-25, 2011. Springer. 371 pages. ISBN: 978-3-642-22953-4.
Journal articles
  • 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. 10167 LNCS: 93-105. doi: 10.1007/978-3-319-53925-6_8
  • Gaspers, Serge; Papadimitriou, C.; Sæther, Sigve Hortemo; Telle, Jan Arne. 2016. On satisfiability problems with a linear structure. Leibniz International Proceedings in Informatics. 63: 1-14. doi: 10.4230/LIPIcs.IPEC.2016.14
  • Telle, Jan Arne; Kratochvil, Jan; tesar, marek. 2016. Computational complexity of covering three-vertex multigraphs. Theoretical Computer Science.
  • 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. 43: 212-223. doi: 10.4230/LIPIcs.IPEC.2015.212
  • Nesetril, Jaroslav; Serra, Oriol; Telle, Jan Arne. 2015. Preface. Electronic Notes in Discrete Mathematics. 49: 1-2. doi: 10.1016/j.endm.2015.06.001
  • Sæther, Sigve Hortemo; Telle, Jan Arne. 2015. Between treewidth and clique-width. Algorithmica. Published ahead of print. 36 pages. doi: 10.1007/s00453-015-0033-7
  • Sæther, Sigve Hortemo; Telle, Jan Arne; Vatshelle, Martin. 2015. Solving #SAT and MaxSAT by dynamic programming. The journal of artificial intelligence research. 54: 59-82.
  • 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.
  • Bruhn, Henning; Charbit, Pierre; Schaudt, Oliver; Telle, Jan Arne. 2014. The graph formulation of the union-closed sets conjecture. European journal of combinatorics (Print). 43: 210-219. doi: 10.1016/j.ejc.2014.08.030
  • Kratochvil, Jan; Telle, Jan Arne; Tesař, Marek. 2014. Computational complexity of covering three-vertex multigraphs. Lecture Notes in Computer Science. 8635 LNCS: 493-504. doi: 10.1007/978-3-662-44465-8_42
  • Telle, Jan Arne; Sæther, Sigve Hortemo. 2014. Between treewidth and clique-width. Lecture Notes in Computer Science. 8747: 396-407.
  • Telle, Jan Arne; Vatshelle, Martin; Sæther, Sigve Hortemo. 2014. Solving MAXSAT and #SAT on structured CNF formulas. Lecture Notes in Computer Science. 8561 LNCS: 16-31. doi: 10.1007/978-3-319-09284-3_3
  • 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. 511: 66-76. doi: 10.1016/j.tcs.2013.01.009
  • Owe, Olaf; Steffen, Martin; Telle, Jan Arne. 2013. The 18th International Symposium on Fundamentals of Computation Theory. Information and Computation. 231: 1-2. doi: 10.1016/j.ic.2013.08.001
  • Rabinovich, Yuri; Telle, Jan Arne; Vatshelle, Martin. 2013. Upper bounds on boolean-width with applications to exact algorithms. Lecture Notes in Computer Science. 8246: 308-320. doi: 10.1007/978-3-319-03898-8_26
  • 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). 34: 666-679. doi: 10.1016/j.ejc.2012.07.023
  • Telle, Jan Arne; Villanger, Yngve. 2013. Connecting Terminals and 2-Disjoint Connected Subgraphs. Lecture Notes in Computer Science. 8165: 418-428. doi: 10.1007/978-3-642-45043-3_36
  • Meister, Daniel; Telle, Jan Arne. 2012. Chordal digraphs. Theoretical Computer Science. 463: 73-83. doi: 10.1016/j.tcs.2012.06.019
  • Telle, Jan Arne. 2012. Jakten på absolutt visshet. Bergens Tidende. doi: 23.08.2012
  • Telle, Jan Arne. 2012. Nå kan robotene snakke sammen. Bergens Tidende. doi: 04.11.2012
  • Telle, Jan Arne. 2012. Mike Fellows: Weaving the web of mathematics and adventure. Lecture Notes in Computer Science. 7370: 74-79.
  • Telle, Jan Arne; Drange, Pål Grønås. 2012. Er du venn med en robot? Morgenbladet. doi: 22.06.2012
  • Telle, Jan Arne; Drange, Pål Grønås. 2012. Sådde frøene til datarevolusjonen. Bergens Tidende. doi: 22.06.2012
  • Telle, Jan Arne; Vatshelle, Martin; Hvidevold, Eivind; Sharmin, Sadia. 2012. Finding good decompositions for dynamic programming on dense graphs. Lecture Notes in Computer Science. 7112: 219-231. doi: 10.1007/978-3-642-28050-4_18
  • Telle, Jan Arne; Villanger, Yngve. 2012. FPT algorithms for domination in biclique-free graphs. Lecture Notes in Computer Science. 7501: 802-812.
  • Bui-Xuan, Binh-Minh; Telle, Jan Arne; Vatshelle, Martin. 2011. Boolean-width of graphs. Theoretical Computer Science. 412: 5187-5204. doi: 10.1016/j.tcs.2011.05.022
  • 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. 68: 113-124. doi: 10.1002/jgt.20544
  • 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. 6410: 159-170. doi: 10.1007/978-3-642-16926-7_16
  • 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. 158: 809-819. doi: 10.1016/j.dam.2009.09.009
  • 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. 6410: 171-183.
  • Meister, Daniel; Telle, Jan Arne; Vatshelle, Martin. 2010. Recognizing digraphs of Kelly-width 2. Discrete Applied Mathematics. 158: 741-746. doi: 10.1016/j.dam.2009.09.018
  • Bui-Xuan, Binh-Minh; Telle, Jan Arne; Vatshelle, Martin. 2009. Boolean-width of graphs. Lecture Notes in Computer Science. 5917: 61-74. doi: 10.1007/978-3-642-11269-0_5
  • Dorn, Frederic; Telle, Jan Arne. 2009. Semi-nice tree-decompositions: The best of branchwidth, treewidth and pathwidth with one algorithm. Discrete Applied Mathematics. 157: 2737-2746. doi: 10.1016/j.dam.2008.08.023
  • Meister, Daniel; Telle, Jan Arne. 2009. Chordal digraphs. Lecture Notes in Computer Science. 5911: 273-284.
  • Paul, Christophe; Telle, Jan Arne. 2009. Edge-maximal graphs of branchwidth k: The k-branches. Discrete Mathematics. 309: 1467-1475. doi: 10.1016/j.disc.2008.02.030
  • Paul, Christophe; Telle, Jan Arne. 2009. Branchwidth of chordal graphs. Discrete Applied Mathematics. 157: 2718-2725. doi: 10.1016/j.dam.2008.08.006
  • Telle, Jan Arne; Bui-Xuan, Binh-Minh; Vatshelle, Martin. 2009. Feedback Vertex Set on Graphs of low Cliquewidth. Lecture Notes in Computer Science. 5874: 113-124. doi: 10.1007/978-3-642-10217-2_14
  • Villanger, Yngve; Heggernes, Pinar; Paul, Christophe; Telle, Jan Arne. 2009. Interval completion is fixed parameter tractable. SIAM journal on computing (Print). 38: 2007-2020. doi: 10.1137/070710913
  • 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. 5369: 402-413.
  • Fiala, Jiří; Paulusma, Daniel; Telle, Jan Arne. 2008. Locally constrained graph homomorphisms and equitable partitions. European journal of combinatorics (Print). 29: 850-880. doi: 10.1016/j.ejc.2007.11.006
  • 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. 4957: 194-205.
  • Sloper, Christian; Telle, Jan Arne. 2008. An overview of techniques for designing parameterized algorithms. Computer journal. 51: 122-136. doi: 10.1093/comjnl/bxm038
  • Telle, Jan Arne. 2007. Om Elster-saken: Bløffmakeri? Morgenbladet. Published 2007-01-26.
  • Telle, Jan Arne; Meister, Daniel; Vatshelle, Martin. 2007. Characterization and recognition of graphs of bounded Kelly-width. Lecture Notes in Computer Science. 4769: 270-279.
  • Telle, Jan Arne; Wood, David. 2007. Planar decompositions and the crossing number of graphs with an excluded minor. New York journal of mathematics. 13: 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. 4372: 150-161.
  • 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. 3887: 386-397. doi: 10.1007/11682462_37
  • 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. 13. 22 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. 19: 900-913.
  • Sloper, Christian; Telle, Jan Arne. 2006. Towards a taxonomy of techniques for designing parameterized algorithms. Lecture Notes in Computer Science. 4169: 251-263.
  • Telle, Jan Arne; Proskurowski, Andrzej; Paul, Christophe. 2006. Generating graphs of bounded branchwidth. Lecture Notes in Computer Science. 4271. 10 pages.
  • Wood, David; Telle, Jan Arne. 2006. Planar decompositions and the crossing number of graphs with an excluded minor. Lecture Notes in Computer Science. 4372. 10 pages.
  • 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. 3787: 115-126.
  • Paul, Christophe; Telle, Jan Arne. 2005. New tools and simpler algorithms for branchwidth. Lecture Notes in Computer Science. 3669: 379-390.
  • Telle, Jan Arne. 2005. Tree-decompositions of small pathwidth. Discrete Applied Mathematics. 145: 210-218.
  • Telle, Jan Arne; Fiala, Jiri; Paulusma, Daniel. 2005. Matrix and graph orders derived from locally constrained graph homomorphisms. Lecture Notes in Computer Science. 3618: 340-351.
  • Telle, Jan Arne; Paul, Christophe. 2005. Edge-maximal graphs of branchwidth k. Electronic Notes in Discrete Mathematics. 22: 363-368.
  • Bodlaender, Hans; Telle, Jan Arne. 2004. Space-efficient construction variants of dynamic programming. Nordic Journal of Computing. 11: 374-385.
  • 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. 3353: 235-244.
  • Fomin, Fedor; Heggernes, Pinar; Telle, Jan Arne. 2004. Graph searching, elimination trees, and a generalization of bandwidth. Algorithmica. 41: 73-87. doi: 10.1007/s00453-004-1117-y
  • Gustedt, J; Telle, Jan Arne. 2004. A work-optimal coarse-grained PRAM algorithm for lexicographically first maximal independent set. Lecture Notes in Computer Science. 2841: 125-136.
  • Hedetniemi, Sandra M.; Hedetniemi, Stephen T.; McRae, Alice A.; Parks, Dee; Telle, Jan Arne. 2004. Iterated colorings of graphs. Discrete Mathematics. 278: 81-108.
  • Fiala, Jiri; Heggernes, Pinar; Kristiansen, Petter; Telle, Jan Arne. 2003. Generalized H-coloring and H-covering of Trees. Nordic Journal of Computing. 10: 206-224.
  • Gebremedhin, Assefaw Hadish; Guerrin-Lassous, Isabelle; Gustedt, Jens; Telle, Jan Arne. 2003. Graph coloring on a coarse grained multiprocessor. Discrete Applied Mathematics. 131: 179-198.
  • Halldorsson, M; Korsatz, G; Proskurowski, A; Salman, R; Shachnai, H; Telle, Jan Arne. 2003. Multi-coloring Trees. Information and Computation. 180: 113-129.
  • Blair, Jean; Heggernes, Pinar; Telle, Jan Arne. 2001. A Practical Algorithm for Making Filled Graphs Minimal. Theoretical Computer Science. 250: 125-141.
  • Telle, Jan Arne; Proskurowski, A. 1999. Classes of graphs with restricted interval models. Discrete mathematics and theoretical computer science (Online). 4: 135-144.
  • Heggernes, Pinar; Telle, Jan Arne. 1998. Partitioning graphs into generalized dominating sets. Nordic Journal of Computing. 5: 128-142.
  • Kratochvil, J.; Proskurowski, Andrzej; Telle, Jan Arne. 1998. Complexity of graph covering problems. Nordic Journal of Computing. 5: 173-195.
  • Kratochvil, J.; Proskurowski, Andrzej; Telle, Jan Arne. 1997. Covering regular graphs. Journal of combinatorial theory. Series B (Print). 71: 1-16.
  • Telle, Jan Arne; Proskurowski, Andrzej. 1997. Algorithms for vertex partitioning problems on partial k-trees. SIAM Journal on Discrete Mathematics. 10: 529-550.
  • Telle, Jan Arne. 1996. A linear time algorithm to find a graph with prescribed degrees of adjacent vertices. TR. 129.
  • Telle, Jan Arne; Lo, V.; Zhong, X. 1996. Parallel divide-and-conquer on meshes. IEEE Transactions on Parallel and Distributed Systems. 7: 1049-1059.
  • Telle, Jan Arne. 1994. Complexity of Domination-type Problems in Graphs. Computing. 1: 157-171.
Reports and theses
  • Gebremedhin, Assefaw Hadish; Guerin Lassous, Isabelle; Gustedt, Jens; Telle, Jan Arne. 2001. PRO: a model for Parallel Resource-Optimal computation. Reports in Informatics. 218. Department of Informatics, University of Bergen, Bergen, Norway. 12 pages.
  • Halldórsson, Magnús M.; Kratochvil, Jan; Telle, Jan Arne. 1997. Independent sets with Domination Constraints. Reports in Informatics. 138. Institutt for Informatikk.
  • Hedetniemi, Sandra; Hedetniemi, Stephen; Mcrae, Alice; Parks, Dee; Telle, Jan Arne. 1997. Iterated Coloring of Graphs. Reports in Informatics. 134. Institutt for Informatikk.
  • Blair, Jean R. S.; Heggernes, Pinar; Telle, Jan Arne. 1996. Making an arbitrary filled graph minimal by removing fill edges. Reports in Informatics. 115. Institutt for Informatikk, UiB. 14 pages.
  • Proskurowski, Andrzej; Telle, Jan Arne. 1996. From bandwith k to pathwidth k. Reports in Informatics. 124. Institutt for Informatikk, UiB.
  • Heggernes, Pinar; Aspvall, Bengt; Telle, Jan Arne. 1995. A simple cubic algorithm for computing minimum height elimination trees for interval graphs. Reports in Informatics. 103. Institutt for informatikk, UiB-MatNat. 10 pages.
  • Heggernes, Pinar; Telle, Jan Arne. 1995. Partitioning Graphs Into Generalized Domination Sets. Reports in Informatics. 107. Institutt for informatikk, UiB-MatNat. 20 pages.
  • 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. [Mangler utgivernavn].
Book sections
  • Owe, Olaf; Telle, Jan Arne; Steffen, Martin. 2011. Preface to the Proceedings of the 18th International Symposium in Fundamentals of Computation Theory FCT 2011. Preface. In:
    • Owe, Olaf; Steffen, Martin; Telle, Jan Arne. 2011. Fundamentals of Computation Theory - 18th International Symposium, FCT 2011, Oslo, Norway, August 22-25, 2011. Springer. 371 pages. ISBN: 978-3-642-22953-4.
  • Heggernes, Pinar; Paul, Christophe; Telle, Jan Arne; Villanger, Yngve. 2007. Interval completion with few edges. 8B, pages 374-381. In:
    • Johnson, David; Feige, Uriel. 2007. STOC: Annual ACM Symposium on Theory of Computing. Association for Computing Machinery (ACM). 735 pages. ISBN: 978-1-59593-631-8.
  • Heggernes, Pinar; Telle, Jan Arne; Villanger, Yngve. 2005. Computing Minimal Triangulations in Time O(nα log n) = o(n2.376). Session 9C, pages 907-916. In:
    • Buchsbaum, Adam. 2005. Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2005. Society for Industrial and Applied Mathematics. 1185 pages. ISBN: 0-89871-585-7.

More information in national current research information system (CRIStin)