List of Publications of Jan Arne Telle


Conferences
Journal Articles
Recent Manuscripts
Books
Technical Reports
Popular Science
Top of page  


Recent Manuscripts

Top of page. 


Conferences

Computational complexity of covering three-vertex multigraphs (pdf)
J.Kratochvil, J.A.Telle, M.Tesar
to appear MFCS 2014

Solving MAXSAT and #SAT on structured CNF formulas (pdf)
S.Sæther, J.A.Telle, M.Vatshelle
to appear SAT 2014

Between treewidth and clique-width (pdf)
S.Sæther, J.A.Telle
to appear WG 2014

Upper bounds on boolean-width with applications to exact algorithms (pdf)
Y.Rabinovich, J.A.Telle, M.Vatshelle
Proceedings IPEC 2013, LNCS 8246, p 308-320

The graph formulation of the union-closed sets conjecture (pdf)
Henning Bruhn, Pierre Charbit, Jan Arne Telle
Proceedings EUROCOMB 2013, CRM Series, ISBN 978-88-7642-474-8, p 73-78

Connecting Terminals and 2-Disjoint Connected Subgraphs (pdf)
J.A.Telle and Y.Villanger
Proceedings WG 2013, LNCS 8165, p 418-428

FPT algorithms for domination in biclique-free graphs (pdf)
J.A.Telle and Y.Villanger
Proceedings ESA 2012, LNCS, 7501, 802-812, 2012

Mike Fellows: Weaving the web of mathematics and adventure (pdf)
J.A.Telle
The Multivariate Algorithmic Revolution and Beyond, LNCS, Volume 7370, 74-79, 2012

Finding good decompositions for dynamic programming on dense graphs (pdf)
E.M.Hvidevold, S.Sharmin, J.A.Telle and M.Vatshelle
Proceedings IPEC 2011, LNCS 7112, 219-231, 2012

On the boolean-width of a graph: structure and applications (pdf)
I.Adler, B-M Bui-Xuan, Y.Rabinovich, G.Renault, J.A.Telle and M.Vatshelle
Proceedings WG 2010, LNCS, Volume 6410. p. 159-170

Generalized graph clustering: recognizing (p,q)-cluster graphs (pdf)
P.Heggernes, D.Lokshtanov, J.Nederlof, C.Paul, and J.A.Telle
Proceedings WG 2010, LNCS, Volume 6410. p. 171-183

Boolean-width of graphs
(see journal version for pdf)
B-M.Bui-Xuan, J.A.Telle and M.Vatshelle
Proceedings IWPEC 2009, LNCS, 5917, pp. 61-74, 2009

Feedback Vertex Set on Graphs of low Cliquewidth (pdf)
(See journal version for a faster algorithm)
B.M.Bui-Xuan, J.A.Telle, M.Vatshelle
Proceedings IWOCA 2009, LNCS, 5874, pp. 113-124, 2009

Chordal digraphs
(see journal version for pdf)
D.Meister and J.A.Telle
Proceedings WG 2009, LNCS, Volume 5911. p. 273-284

Leaf powers and their properties: using the trees (pdf)
M.Fellows, D.Meister, R.Sritharan, F.Rosamond and J.A.Telle
Proceedings ISAAC 2008, LNCS, Volume 5369. p. 402-413

On the complexity of reconstructing $H$-free graphs from their Star Systems
(see journal version for pdf)
F.Fomin, J.Kratochvil, D.Lokshtanov, F.Mancini and J.A.Telle
Proceedings LATIN 2008, LNCS, Volume 4957. p. 194-205

Characterization and recognition of graphs of bounded Kelly-width
(See journal-version: Recognizing digraphs of Kelly-width 2)
D.Meister, J.A.Telle and M.Vatshelle
Proceedings WG 2007, LNCS vol 4769, 270-279

Interval completion with few edges (ps, pdf)
P.Heggernes, C.Paul, J.A.Telle and Y.Villanger
Proceedings STOC 2007, ACM, 374-381

Planar decompositions and the crossing number of graphs with an excluded minor
(see journal version for pdf)
Wood and J.A.Telle
Proceedings Graph Drawing 2006, LNCS vol 4372

Towards a taxonomy of techniques for designing parameterized algorithms (ps, pdf)
C.Sloper and J.A.Telle
Proceedings IWPEC'06, LNCS vol 4169

Generating graphs of bounded branchwidth (ps, pdf)
C.Paul, A.Proskurowski and J.A.Telle
Proceedings WG'06, LNCS vol 4271

Two birds with one stone: the best of branchwidth and treewidth with one algorithm (ps, pdf)
F.Dorn and J.A.Telle
Proceedings LATIN'06, LNCS vol 3887

New tools and simpler algorithms for branchwidth (ps, pdf)
C.Paul and J.A.Telle
Proceedings ESA'05, 13th Annual European Symposium on ALgorithms, LNCS, vol 3669, 379-390.

Edge-maximal graphs of branchwidth k
C.Paul and J.A.Telle
Proceedings ICGT'05, 7th International Colloquium on Graph Theory, Electronic Notes in Discrete Mathematics, vol 22, 363-368

Matrix and graph orders derived from locally constrained graph homomorphisms (ps, pdf)
J.Fiala, D.Paulusma and J.A.Telle
Proceedings MFCS'05, 30th International Symposium on Mathematical Foundations of Computer Science, LNCS vol 3618, 340-351

Algorithms for comparability of matrices in partial orders imposed by graph homomorphisms (ps, pdf)
J.Fiala, D.Paulusma and J.A.Telle
Proceedings WG'05, 31st Workshop on Graph Theoretic Concepts in Computer Science, LNCS vol 3787, 115-226

Computing Minimal Fill in $O(n^{\alpha} \log n)=o(n^{2.376}) $ Time (ps, pdf)
P.Heggernes, J.A.Telle and Y.Villanger
Proceedings SODA 2005 - 16th ACM-SIAM Symposium on Discrete Algorithms.

Finding k disjoint triangles in a graph (ps, pdf)
M. Fellows, P. Heggernes, F. Rosamond, C. Sloper, and J. A. Telle
Proceedings WG'04 - 30th Workshop on Graph Theoretic Concepts in Computer Science (WG 2004), Bad Honnef, Germany,June 2004, Springer Verlag, Lecture Notes in Computer Science vol 3353, 235-244

A work-optimal coarse-grained PRAM algorithm for Lexicographically First Maximal Independent Set (ps, pdf)
J.Gustedt and J.A.Telle
Proceedings ICTCS'03 - 10th Italian Conference on Theoretical Computer Science, Bologna, Italy, October 2003, Springer Verlag, Lecture Notes in Computer Science vol 2841, pp 125-136

A linear-time algorithm for recognition of catval graphs (ps, pdf)
M.Habib, C.Paul and J.A.Telle
EUROCOMB 2003, September, Prague.

Graph searching, elimination trees, and a generalization of bandwidth (ps, pdf)
Fedor Fomin, Pinar Heggernes, Jan Arne Telle
Proceedings FCT 2003 - 14th International Symposium on Fundamentals of Computation Theory, August 12-15, 2003, Malm/o, Sweden, Springer Verlag, Lecture Notes in Computer Science vol 2751, pp 73-85.

Generalized H-coloring and H-covering of Trees (ps, pdf)
Jiri Fiala, Pinar Heggernes, Petter Kristiansen, Jan Arne Telle
Proceedings WG'02 - 28th International Workshop on Graph-Theoretic Concepts in Computer Science, Cesky Krumlov, Czech Republic, June 13-15 2002, Springer Verlag, Lecture Notes in Computer Science vol 2573, pp 198-210

PRO: A model for Parallel Resource-Optimal computation (ps, pdf)
A.Gebremedhin, I.Guerrin, J.Gustedt and J.A.Telle
Proceedings HPCS'2002 - The 16th Annual International Symposium on High Performance Computing Systems and Applications, IEEE, Moncton, NB, Canada, June 17-19, 2002.

The treewidth of Java programs (ps, pdf)
J.Gustedt, O.Mæhle and J.A.Telle
Proceedings ALENEX'02- 4th Workshop on Algorithm Engineering and Experiments, San Francisco, January 4-5, 2002, Springer Verlag, Lecture Notes in Computer Science vol 2409.

Tree-decompositions of small pathwidth
(see journal version)
J.A.Telle
EUROCOMB 2001, September, Barcelona

Generalized H-coloring of graphs (ps, pdf)
P.Kristiansen and J.A.Telle
Proceedings ISAAC'00 - 7th Annual International Symposium on Algorithms And Computation, Taipei, Taiwan, December 18-20 2000, Springer Verlag, Lecture Notes in Computer Science, vol 1969, pp ?-?

Graph coloring on a coarse grained multiprocessor (see journal version)
A.Gebremedhin, I.Guerrin, J.Gustedt and J.A.Telle
Proceedings WG'00 - 26th International Workshop on Graph-Theoretic Concepts in Computer Science, Konstanz, Germany, June 15-17 2000, Springer Verlag, Lecture Notes in Computer Science, vol 1928, pp 184-195

Mod-2 independence and domination in graphs (see journal version)
M.Halldorsson, J.Kratochvil and J.A.Telle
Proceedings WG'99 - 25th International Workshop on Graph-Theoretic Concepts in Computer Science, Ascona, Switzerland, June 17-19, 1999, Springer Verlag, Lecture Notes in Computer Science vol 1665, pp 101-109.

Multi-coloring Trees (see journal version)
M.Halldorsson, G.Korsatz, A.Proskurowski, R.Salman, H.Shachnai and J.A.Telle
Proceedings COCOON'99 - Fifth Annual International Computing and Combinatorics Conference, July 26-28 1999, Tokyo, Japan, Springer Verlag, Lecture Notes in Computer Science vol 1627, pp. 271-280.

From bandwidth k to pathwidth k
A.Proskurowski and J.A.Telle
Proceedings ICTCS'98 - 5th Italian Conference on Theoretical Computer Science, Prato, Italy, November 9-11 1998, World Scientific Publishing, pp. 90-101.

Memory requirements for table computations in partial k-tree algorithms (see journal version)
B.Aspvall, A.Proskurowski and J.A.Telle
Proceedings SWAT'98 - 6th Scandinavian Workshop on Algorithm Theory, Stockholm, Sweden, July 1998, Springer Verlag, Lecture Notes in Computer Science vol. 1432, pp. 222-233.

Independent sets with domination constraints (see journal version)
M.Halldorsson, J.Kratochvil and J.A Telle
Proceedings ICALP'98 - 25th International Colloquium on Automata, Languages and Programming, Aalborg, Denmark, July 13-17 1998, Springer Verlag, Lecture Notes in Computer Science vol. 1443, pp. 176-187

Linear-time register allocation for a fixed number of registers (ps, pdf)
H.Bodlaender, J.Gustedt and J.A.Telle
Proceedings SODA'98, pp. 574-583, Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, San Francisco January 25-27 1998.

Complexity of colored graph covers I. Colored directed multigraphs (ps, pdf)
J.Kratochvil, A.Proskurowski and J.A.Telle
Proceedings WG'97 - 23rd International Workshop on Graph-Theoretic Concepts in Computer Science, Berlin June 18-20, Springer Verlag, Lecture Notes in Computer Science Vol. 1335, pp. 242-257.

Faster algorithms for the nonemptiness of Streett automata and for communication protocol pruning (ps, pdf)
M.R.Henzinger and J.A.Telle
Proceedings SWAT'96 - Fifth Scandinavian Workshop on Algorithm Theory, Springer Verlag, Lecture Notes in Computer Science vol.1097 (1996) 16-27.

Making an arbitrary filled graph minimal by removing fill edges
J.Blair, P.Heggernes and J.A.Telle
Proceedings SWAT'96 - Fifth Scandinavian Workshop on Algorithm Theory, Springer Verlag, Lecture Notes in Computer Science vol.1097 (1996) 173-184.

Partitioning Graphs into Generalized Dominating Sets (see journal version)
P.Heggernes and J.A.Telle
Proceedings SCCC'95 - XV International Conference of the Chilean Computer Society, 1995, pp 241-252.

Complexity of Graph Covering Problems (see journal version)
J.Kratochvil, A.Proskurowski and J.A.Telle
Proceedings WG'94 - 20th International Workshop on Graph-Theoretical Concepts in Computer Science, Springer-Verlag, Lecture Notes in Computer Science vol.903, 1995, pp 93-105.

Practical algorithms on partial $k$-trees with an application to domination-like problems (see Ch.6.1 of my PhD Thesis)
J.A.Telle and A.Proskurowski
Proceedings WADS'93 - Third Workshop on Algorithms and Data Structures, Springer Verlag, Lecture Notes in Computer Science vol.709 (1993) 610-621.

Characterization of domination-type parameters in graphs (see Ch.2 of my PhD Thesis)
J.A.Telle
Proceedings SCCGC'93 - 24th Southeastern International Conference on Combinatorics, Graph Theory and Computing -Congressus Numerantium Vol.94 (1993) 9-16.

OREGAMI: Software tools for mapping parallel algorithms to parallel architectures (see journal version)
V.Lo, S.Rajopadhye, S.Gupta, D.Keldsen, M.Mohamed, B.Nitzberg, J.A.Telle and X.Zhong
Proceedings ICPP'90 - IEEE 1990 International Conference on Parallel Processing, II:88-92, August 1990.

Mapping divide-and-conquer algorithms to parallel architectures
V.Lo, S.Rajopadhye, S.Gupta, D.Keldsen, M.Mohamed and J.A.Telle
Proceedings ICPP'90 - IEEE 1990 International Conference on Parallel Processing, III:128-135, August 1990.

Top of page  


Journal Articles

Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems (pdf)
B-M.Bui-Xuan, J.A.Telle and M.Vatshelle
Theoretical Computer Science, 511: 66-76 (2013)

Feedback Vertex Set on Graphs of low Cliquewidth (pdf)
B.M.Bui-Xuan, O. Suchy, J.A.Telle, M.Vatshelle
European Journal of Combinatorics. 34(3): 666-679 (2013)

Chordal digraphs (pdf)
D.Meister and J.A.Telle
Theoretical Computer Science, 463: 73-83 (2012)

Boolean-width of graphs (pdf)
B-M.Bui-Xuan, J.A.Telle and M.Vatshelle
Theoretical Computer Science 412(39): 5187-5204 (2011)

On the complexity of reconstructing $H$-free graphs from their Star Systems (pdf)
F.Fomin, J.Kratochvil, D.Lokshtanov, F.Mancini and J.A.Telle
Journal of Graph Theory 68(2): 113-124 (2011)

H-join decomposable graphs and algorithms with runtime single exponential in rankwidth (ps, pdf)
B-M.Bui-Xuan, J.A.Telle and M.Vatshelle
Discrete Applied Mathematics 2010 ;Volume 158.(7) p. 809-819

Recognizing digraphs of Kelly-width 2 (ps)
D.Meister, J.A.Telle and M.Vatshelle
Discrete Applied Mathematics 2010 ;Volume 158.(7) p. 741-746

Interval Completion is Fixed Parameter Tractable (pdf)
Y.Villanger, P.Heggernes, C.Paul and J.A.Telle
SIAM Journal on Computing. Volume 38.(5) p. 2007-2020. 2009

Edge-maximal graphs of branchwidth k: the k-branches (ps, pdf)
C.Paul and J.A.Telle
Discrete Mathematics. Volume 309.(6) p. 1467-1475. 2009

Branchwidth of chordal graphs (pdf)
C.Paul and J.A.Telle
Discrete Applied Mathematics. Volume 157.(12) p. 2718-2725. 2009

Seminice tree-decompositions: the best of branchwidth, treewidth and pathwidth with one algorithm (ps)
F.Dorn and J.A.Telle
Discrete Applied Mathematics. Volume 157.(12) p. 2737-2746. 2009

Locally constrained graph homomorphisms and equitable partitions (ps, pdf)
J.Fiala, D.Paulusma and J.A.Telle
European Journal of Combinatorics. Volume 29.(4) p. 850-880

An overview of techniques for designing parameterized algorithms (ps, pdf)
C.Sloper and J.A.Telle
The Computer Journal 2008, vol.51, nr 1, 102-121

Planar decompositions and the crossing number of graphs with an excluded minor (ps, pdf)
D.Wood and J.A.Telle
New York Journal of Mathematics, Vol.13, 2007, 117-146

PRO: A Model for the Design and Analysis of Efficient and Scalable Parallel Algorithms (ps, pdf)
A.Gebremedhin, M.Essaidi, I.Guerrin, J.Gustedt and J.A.Telle
Nordic Journal of Computing vol 13-4, 2006

Computing Minimal Triangulations in $O(n^{\alpha} \log n)=o(n^{2.376}) $ Time (ps)
P.Heggernes, J.A.Telle and Y.Villanger
SIAM J. Discrete Math. 19-4:900-913, 2005

Tree-decompositions of small pathwidth (ps, pdf)
J.A.Telle
Discrete Applied Mathematics, vol 145(2), 210-218, 2005

Space-efficient construction variants of dynamic programming (ps, pdf)
H.Bodlaender, J.A.Telle
Nordic Journal of Computing 11, 374-385, 2004

Graph searching, elimination trees, and a generalization of bandwidth (ps, pdf)
F.Fomin, P.Heggernes, J.A.Telle
Algorithmica 41-2, 73-87, 2004

Iterated coloring (ps, pdf)
S.M.Hedetniemi, S.T.Hedetniemi, A.McRae, D.Parks and J.A.Telle
Discrete Mathematics, Volume 278, Issues 1-3, 6 March 2004, Pages 81-108

Generalized H-coloring and H-covering of Trees
Jiri Fiala, Pinar Heggernes, Petter Kristiansen, Jan Arne Telle
Nordic Journal of Computing 2003 10 (3) 206-224

Multi-coloring Trees (ps, pdf)
M.Halldorsson, G.Korsatz, A.Proskurowski, R.Salman, H.Shachnai and J.A.Telle
Information and Computation 180 (2003), 113-129, 2003.

Graph coloring on a coarse grained multiprocessor (ps, pdf)
A.Gebremedhin, I.Guerrin, J.Gustedt and J.A.Telle
Discrete Applied Mathematics Vol 131/1, pp 179-198, 2003.

A Practical Algorithm for Making Filled Graphs Minimal (ps, pdf)
J.Blair, P.Heggernes, and J.A.Telle
Theoretical Computer Science 250-1/2 (2001), pages 125-141.

Mod-2 independence and domination in graphs (ps, pdf)
M.Halldorsson, J.Kratochvil and J.A.Telle
International Journal of Foundations of Computer Science Vol. 11, No. 3, 2000

Memory requirements for table computations in partial k-tree algorithms (ps, pdf)
B.Aspvall, A.Proskurowski and J.A.Telle
Algorithmica Vol. 27, Number 3, 2000, 382-394.

Independent sets with domination constraints (ps, pdf)
M.Halldorsson, J.Kratochvil and J.A Telle
Discrete Applied Mathematics 99 (1-3) 39-54, 1999

Classes of graphs with restricted interval models (ps, pdf)
A.Proskurowski and J.A.Telle
Discrete Mathematics and Theoretical Computer Science 4 (1999), 135-144

Complexity of graph covering problems (ps, pdf)
J.Kratochvil, A.Proskurowski and J.A.Telle
Nordic Journal of Computing 5 (1998), 173-195

Partitioning Graphs Into Generalized Dominating Sets (ps, pdf)
Pinar Heggernes and Jan Arne Telle
Nordic Journal of Computing 5-2 (1998), pages 128-142.

Algorithms for Vertex Partitioning Problems on Partial k-Trees (ps, pdf)
J.A.Telle and A.Proskurowski
SIAM Journal on Discrete Mathematics Vol. 10, No. 4, pp. 529-550, November 1997

Covering regular graphs (ps, pdf)
J.Kratochvil, A.Proskurowski and J.A.Telle
Journal of Combinatorial Theory - Series B vol.71, No.1 (1997) 1-16.

Parallel divide-and-conquer on meshes (ps, pdf)
V.Lo, S.Rajopadhye, J.A.Telle and X.Zhong
IEEE Transactions on Parallel and Distributed Systems vol.7, No. 10, October 1996, 1049-1059.

Complexity of domination-type problems in graphs (see Ch.3 of my PhD Thesis)
J.A.Telle
Nordic Journal of Computing 1 (1994) 157-171.

Efficient sets in partial $k$-trees
J.A.Telle and A.Proskurowski
Discrete Applied Mathematics 44 (1993) 109-117.

OREGAMI: Tools for mapping parallel computations to parallel architectures
(ps, pdf)
V.Lo, S.Rajopadhye, S.Gupta, D.Keldsen, M.Mohamed, B.Nitzberg, J.A.Telle and X.Zhong
International Journal of Parallel Programming, Vol.20, No. 3, June 1991, 237-270.

Top of page. 


Books

Fundamentals of Computation Theory
Olaf Owe, Martin Steffen, Jan Arne Telle (editors)
Proceedings 18th International Symposium, FCT 2011, Oslo, Norway, August 22-25, 2011. Lecture Notes in Computer Science 6914, Springer 2011

Top of page. 


Technical Reports (with contents not among those papers listed above)

A linear-time algorithm to find a graph with prescribed degrees of adjacent vertices
J.A.Telle
TR 129, December 1996, University of Bergen.

A simple cubic algorithm for minimum height elimination trees of interval graphs (ps, pdf)
B.Aspvall, P.Heggernes and J.A.Telle
TR 103, January 1995, University of Bergen

Vertex Partitioning Problems: Characterization, Complexity and Algorithms on Partial k-Trees, (ps, pdf)
J.A.Telle
Ph.D. Thesis, Computer and Information Sciences Department, University of Oregon, CIS-TR-18-94.

LARCS: A language for describing parallel computations for the purpose of mapping (ps, pdf)
V.Lo, S.Rajopadhye, M.Mohamed, B.Nitzberg, J.A.Telle and X.Zhong
CIS-TR-90-16 (originally accepted to IEEE TPDS but withdrawn due to delays)

Top of page. 


Popular science

Nå kan robotene snakke sammen (pdf)
J.A.Telle
Bergens Tidende 4.november 2012

Jakten på absolutt visshet (pdf)
J.A.Telle
Bergens Tidende 23.august 2012

Er du venn med en robot? (pdf)
P.G.Drange and J.A.Telle
Morgenbladet 22.juni 2012

Sådde frøene til datarevolusjonen (pdf)
P.G.Drange and J.A.Telle
Bergens Tidende 22.juni 2012

Hva er datamaskinens fundamentale begrensninger? (ps, pdf)
J.A.Telle
QED 2-97 student newspaper, U.Bergen.

Top of page.