Hjem
Jan Arne Telles bilde

Jan Arne Telle

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

Se fullstendig oversikt over publikasjoner i CRIStin.