Cette page utilise des feuilles de style en cascade. Si vous arrivez à lire ce message, c'est que CSS ou javascript ne sont pas activés. L'affichage de la page sera donc différent de ce qui est prévu.

List of publications


Publications in Refereed Journals


  1. On the partition of permutations into increasing or decreasing subsequences, Journal of Information and Cybernetic Processes 22 (1986), pp. 263-273 (joint work with A. Brandstädt).
  2. Finding the minimum bandwidth of an interval graph, Information & Computation 74 (1987), pp. 140-158.
  3. On domination problems for permutation and other graphs, Theoretical Computer Science 54 (1987), pp. 181-198 (joint work with A. Brandstädt).
  4. Finding minimum dominating cliques efficiently, in strongly chordal graphs and undirected path graphs, Discrete Mathematics 86 (1990), pp. 225-238.
  5. Domination on chordal bipartite and convex graphs, Information Processing Letters 36 (1990), pp. 231-236 (joint work with P. Damaschke and H. Müller).
  6. Extremal results in cochromatic and dichromatic theory, Journal of Graph Theory 15 (1991), pp. 579-585 (joint work with P. Erdös and J. Gimbel).
  7. Finding hamiltonian paths in cocomparability graphs using the bump number algorithm, Order 8 (1992), pp. 383-391 (joint work with P. Damaschke, J.S. Deogun and G. Steiner).
  8. The complexity of coloring games on perfect graphs, Theoretical Computer Science 106 (1992), pp. 309-326 (joint work with H. Bodlaender).
  9. Domination on cocomparability graphs, SIAM Journal on Discrete Mathematics 6 (1993), pp. 400-417 (joint work with L. Stewart).
  10. On cocolourings and cochromatic number of graphs, Discrete Applied Mathematics 48 (1994), pp. 111-127 (joint work with J. Gimbel and L. Stewart).
  11. On the complexity of graph reconstruction, Mathematical Systems Theory 27 (1994), pp. 257-273 (joint work with L. Hemaaspandra).
  12. Dominating cliques in chordal graphs, Discrete Mathematics 128 (1994), pp. 269-276 (joint work with P. Damaschke and A. Lubiw).
  13. A counterexample about poset reconstruction, Order 11 (1994), pp. 95-96 (joint work with J.-X. Rampon).
  14. Towards the reconstruction of posets, Order 11 (1994), pp. 317-341 (joint work with J.-X. Rampon).
  15. Computing a perfect edge without vertex elimination ordering of a chordal bipartite graph, Information Processing Letters 55 (1995), pp. 11-16 (joint work with T. Kloks).
  16. Treewidth of chordal bipartite graphs, Journal of Algorithms 19 (1995), pp. 266-281 (joint work with T. Kloks).
  17. Treewidth and pathwidth of permutation graphs, SIAM Journal on Discrete Mathematics 8 (1995), pp. 606-616 (joint work with H. Bodlaender and T. Kloks).
  18. Minimal non-neighbourhood-perfect graphs, Journal of Graph Theory 21 (1996), pp. 55-66 (joint work with A. Gyarfas, J. Lehel and F. Maffray).
  19. Toughness, hamiltonicity and split graphs, Discrete Mathematics 150 (1996), pp. 231-245 (joint work with J. Lehel and H. Müller).
  20. Width two posets are reconstructible, Discrete Mathematics 162 (1996), pp. 305-310 (joint work with J.-X. Rampon).
  21. On treewidth and minimum fill-in of asteroidal triple-free graphs, Theoretical Computer Science 175 (1997), pp. 309-335 (joint work with T. Kloks and J. Spinrad).
  22. An approximation algorithm for clustering graphs with dominating diametral path, Information Processing Letters 61 (1997), pp. 121-127 (joint work with J.S. Deogun and G. Steiner).
  23. 1-tough cocomparability graphs are hamiltonian, Discrete Mathematics 171 (1997), pp. 99-106 (joint work with J.S. Deogun and G. Steiner).
  24. Measuring the vulnerability for classes of intersection graphs, Discrete Applied Mathematics 77 (1997), pp. 259-270 (joint work with T. Kloks and H. Müller).
  25. Total domination and transformation, Information Processing Letters 63 (1997), pp. 167-170 (joint work with L. Stewart).
  26. Rankings of graphs, SIAM Journal on Discrete Mathematics 11 (1998), pp. 168-181 (joint work with H. Bodlaender, J.S. Deogun, K. Jansen, T. Kloks, H. Müller and Zs. Tuza).
  27. Listing all minimal separators of a graph, SIAM Journal on Computing 27 (1998), pp. 605-613 (joint work with T. Kloks).
  28. Treewidth and minimum fill-in on d-trapezoid graphs, Journal of Graph Algorithms and Applications 2 (1998), no. 5, pp. 1-23 (joint work with H. Bodlaender, T. Kloks and H. Müller).
  29. Minimum fill-in on circle and circular-arc graphs, Journal of Algorithms 28 (1998), pp. 272-289 (joint work with T. Kloks and C.K. Wong).
  30. Tree-visibility orders, Discrete Mathematics 190 (1998), pp. 163-175 (joint work with J.-X. Rampon).
  31. Bandwidth of chain graphs, Information Processing Letters 68 (1998), pp. 313-315 (joint work with T. Kloks and H. Müller).
  32. Independent sets in asteroidal triple-free graphs, SIAM Journal on Discrete Mathematics 12 (1999), pp. 267-287 (joint work with H.J. Broersma, T. Kloks and H. Müller).
  33. Approximating the bandwidth for AT-free graphs, Journal of Algorithms, 32 (1999), pp. 41-57 (joint work with T. Kloks and H. Müller).
  34. On the vertex ranking problem for trapezoid, circular-arc and other graphs, Discrete Applied Mathematics, 98 (1999), pp. 39-63 (joint work with J.S. Deogun, T. Kloks and H. Müller).
  35. Domination and total domination on asteroidal triple-free graphs, Discrete Applied Mathematics, 99 (2000), pp. 111-123.
  36. Chordality and 2-factors in tough graph, Discrete Applied Mathematics 99 (2000), pp. 323-330 (joint work with D. Bauer, G.Y. Katona and H.J. Veldman).
  37. Degree-preserving trees, Networks 35 (2000), pp. 26-39 (joint work with H.J. Broersma, O. Koppius, H. Tuinstra, A. Huck, T. Kloks and H. Müller).
  38. Finding and counting small induced subgraphs efficiently, Information Processing Letters 74 (2000), pp. 115-121 (joint work with T. Kloks and H. Müller).
  39. Efficent algorithms for graphs with few P4's, Discrete Mathematics 235 (2001), pp. 29-51 (joint work with L. Babel, T. Kloks, J. Kratochvil, H. Müller and S. Olariu).
  40. On the structure of graphs with bounded asteroidal number, Graphs and Combinatorics 17 (2001), pp. 295-306 (joint work with T. Kloks and H. Müller).
  41. A generalization of AT-free graphs and a generic algorithm for solving triangulation problems, Algorithmica 32 (2002), pp. 594-610 (joint work with H.J. Broersma, T. Kloks and H. Müller).
  42. Dominating pair graphs, SIAM Journal on Discrete Mathematics 15 (2002), pp. 353-366 (joint work with J.S. Deogun).
  43. Kayles and nimbers, Journal of Algorithms 42 (2002), pp. 106-119 (joint work with H. Bodlaender).
  44. On claw-free asteroidal triple-free graphs, Discrete Applied Mathematics 121 (2002), pp. 155-180 (joint work with H. Hempel).
  45. Approximating bandwidth by mixing layouts of interval graphs, SIAM Journal on Discrete Mathematics 15 (2002), pp. 435-449 (joint work with L. Stewart).
  46. Approximating minimum cocolourings, Information Processing Letters 84 (2002), pp. 285-290 (joint work with F. Fomin and J.-C. Novelli).
  47. On the domination search number, Discrete Applied Mathematics 127 (2003), pp. 565-580 (joint work with F. Fomin and H. Müller).
  48. Additive tree spanners, SIAM Journal on Discrete Mathematics 17 (2003), pp. 332-340 (joint work with E. Prisner, H.-O. Le, H. Müller and D. Wagner).
  49. Algorithms for graphs with small octopus, Discrete Applied Mathematics 134 (2004), pp. 105-128 (joint work with F. Fomin and H. Müller).
  50. On treewidth approximations,, Discrete Applied Mathematics 136 (2004), pp. 183-196 (joint work with V. Bouchitte, H. Müller and I. Todinca ).
  51. On the structure of (P5,gem)-free graphs, Discrete Applied Mathematics 145 (2005) pp. 155-166 (joint work with A. Brandstädt).
  52. Linear time algorithms for some NP-complete problems on (P5,gem)-free graphs, Theoretical Computer Science (joint work with H. Bodlaender, A. Brandstädt, M. Rao and J. Spinrad).
  53. Some new techniques in design and analysis of exact (exponential) algorithms, Bulletin of the EATCS 87 (2005) pp. 47-77. (joint work with F. Fomin and F. Grandoni).
  54. Minimal fill in O(n^2.69) time, Discrete Applied Mathematics 306 (2006) pp. 366-371 (joint work with J. Spinrad).
  55. Improved bottleneck domination algorithms, Discrete Applied Mathematics 154 (2006) pp. 1578-1592 (joint work with T. Kloks, C.M. Lee and J. Liu).
  56. Between O(nm) and O(n^{\alpha}), SIAM Journal on Computing 36 (2006) pp. 310-325. (joint work with J. Spinrad).
  57. Certifying algorithms for recognizing interval and permutation graphs, SIAM Journal on Computing 36 (2006) pp. 326-353. (joint work with R. McConnell, K. Mehlhorn and J. Spinrad).
  58. Exact algorithms for graph homomorphisms, Theory of Computing Systems 41 (2007) pp. 381-393. (joint work with F. Fomin and P. Heggernes).
  59. An exact algorithm for the minimum dominating clique problem, Theoretical Computer Science 385 (2007) pp. 226-240. (joint work with M. Liedloff).
  60. Linear-time certifying recognition algorithms and forbidden induced subgraphs, Nordic Journal on Computing 14 (2007) pp. 87-108. (joint work with P. Heggernes).
  61. Feedback vertex set on AT-free graphs, Discrete Applied Mathematics 156 (2008) pp. 1936-1947. (joint work with H. Müller and I. Todinca).
  62. A new characterization of HH-free graphs, Discrete Mathematics 308 (2008) pp. 4833-4835. (joint work with J. Spinrad and R. Sritharan).
  63. Exact algorithms for treewidth and min fill-in, SIAM Journal on Computing 38 (2008) pp. 1058-1079. (joint work with F. Fomin, I. Todinca and Y. Villanger).
  64. Connected Dominating Set faster than 2^n, Algorithmica 52 (2008) pp. 153-166. (joint work with F. Fomin and F. Grandoni).
  65. On a property of minimal triangulations, Discrete Mathematics 309 (2009) pp. 1724-1729. (joint work with H. Müller).
  66. Sort and Search: Exact algorithms for generalized domination, Information Processing Letters 109 (2009) pp. 795-798. (joint work with F.V. Fomin, P. Golovach, J. Kratochvil and M. Liedloff).
  67. A Measure and Conquer approach for the analysis of exact algorithms, Journal of the ACM 56(5): (2009), article 25. (joint work with F. Fomin and F. Grandoni).
  68. Bandwidth of bipartite permutation graphs in polynomial time, Journal on Discrete Algorithms 7 (2009) pp. 533-544. (joint work with P. Heggernes and D. Meister).
  69. Exponential time algorithms for the minimum dominating set problem on some graph classes, ACM Transactions on Algorithms 6(1) (2009), article 9. (joint work with S. Gaspers, M. Liedloff and I. Todinca).
  70. Iterative compression and exact algorithms, Theoretical Computer Science 411 (2010) pp. 1045-1053. (joint work with F. Fomin, S. Gaspers, P. Golovach and S. Saurabh).
  71. Parameterized algorithm for eternal vertex cover, Information Processing Letters 110 (2010) pp. 702-706. (joint work with F. Fomin, S. Gaspers, P. Golovach and S. Saurabh).
  72. Exact algorithms for L(2,1)-labeling of graphs, Algorithmica 59 (2011) pp. 169-194. (joint work with F. Havet, M. Klazar, J. Kratochvil and M. Liedloff).
  73. Breaking the 2^n-barrier for irredundance: two lines of attack, Journal of Discrete Algorithms 9 (2011) pp. 214-230. (joint work with D. Binkele-Raible, L. Brankovic, M. Cygan, H. Fernau, J. Kneis, A. Langer, M. Liedloff, M. Pilipczuk, P. Rossmanith, and J.O. Wojtaszczyk).
  74. Branch & Recharge: Exact algorithms for generalized domination, Algorithmica 61 (2011) pp. 252-273. (joint work with F. Fomin, P. Golovach, J. Kratochvil and M. Liedloff).
  75. A fast exact algorithm for the Maximum Leaf Spanning Tree problem, Theoretical Computer Science 412 (2011) pp. 6290-6302. (joint work with H. Fernau, J. Kneis, A. Langer, M. Liedloff, D. Raible and P. Rossmanith).
  76. Bandwidth on AT-free graphs, Theoretical Computer Science 412 (2011) pp. 7001-7008. (joint work with P. Golovach, P. Heggernes, D. Lokshtanov, D. Meister and S. Saurabh).
  77. On independent sets and bicliques, Algorithmica 62 (2012) pp. 637-658. (joint work with S. Gaspers and M. Liedloff).
  78. A note on exact algorithms for vertex ordering problems on graphs, Theory of Computing Systems 50 (2012) pp. 420-432. (joint work with H. Bodlaender, F. Fomin, A. Koster and D. Thilikos).


Monographs and Chapters in Books


  1. Algorithms, (Chapter 8), in: Domination in Graphs: Advanced Topics, T. Haynes, S. Hedetniemi, P. Slater, (eds.), Marcel Dekker, 1998, pp. 191-231.
  2. Exact Exponential Algorithms, Texts in Theoretical Computer Science, Springer, 2010 (joint work with F. Fomin).


Publications in Proceedings and Refereed Books


not (yet) published in a refereed journal

  1. On the restriction of some NP-complete graph problems to permutation graphs, Proceedings of FCT'85, L. Budach, (ed.), Springer-Verlag, Berlin, 1985, Lecture Notes in Computer Science 199, pp. 53-62 (joint work with A. Brandstädt).
  2. Ratios of domination parameters, in: Advances in Graph Theory, V. Kulli, (ed.), Vishwa International Publications, India, 1991, pp. 173-182 (joint work with O. Favaron).
  3. Computing treewidth and minimum fill-in: all you need are all minimal separators, Proceedings of ESA'93, T. Lengauer, (ed.), Springer-Verlag, 1993, Berlin, Lecture Notes in Computer Science 726, pp. 260-271 (joint work with H. Bodlaender, T. Kloks and H. Müller).
  4. Dominoes, Proceedings of WG'94, E.W. Mayr, G. Schmidt, G. Tinhofer, (eds.), Springer-Verlag, 1995, Berlin, Lecture Notes in Computer Science 903, pp. 106-120 (joint work with T. Kloks and H. Müller).
  5. Diametral path graphs, Proceedings of WG'95, M. Nagl, (ed.), Springer-Verlag, 1995, Berlin, Lecture Notes in Computer Science 1017, pp. 344-357 (joint work with J.S. Deogun).
  6. Asteroidal sets in graphs, Proceedings of WG'97, Springer-Verlag, 1997, Berlin, Lecture Notes in Computer Science 1335, pp. 229-241 (joint work with T. Kloks and H. Müller).
  7. Bandwidth of split and circular permutation graphs, Proceedings of WG'2000, Springer-Verlag, 2000, Berlin, Lecture Notes in Computer Science 1928, pp. 243-254 (joint work with T. Kloks, Y. Le Borgne and H. Müller).
  8. Exact (exponential) algorithms for the dominating set problem, Proceedings of WG 2004, Springer-Verlag, 2004, Berlin, Lecture Notes in Computer Science 3353, pp. 245-256. (joint work with F. Fomin and G. Woeginger).
  9. On the recognition of probe graphs of some self-complementary classes of perfect graphs, Proceedings of COCOON 2005, Springer-Verlag, 2005, Berlin, Lecture Notes in Computer Science 3595, pp. 808-817. (joint work with M.S. Chang, T. Kloks, J. Liu and S.L. Peng).
  10. Optimal linear arrangement of interval graphs, Proceedings of MFCS 2006, Springer-Verlag, 2006, Berlin, Lecture Notes in Computer Science 4162, pp. 267-279 (joint work with Johanne Cohen, F. Fomin, P. Heggernes and G. Kucherov).
  11. Exact algorithms for treewidth, Proceedings of ESA 2006, Springer-Verlag, 2006, Berlin, Lecture Notes in Computer Science 4168, pp. 672-683 (joint work with H. Bodlaender, F. Fomin, A. Koster and D. Thilikos).
  12. Fast Steiner tree computation in polynomial space, Proceedings of ESA 2008, Springer-Verlag, 2008, Berlin, Lecture Notes in Computer Science 5193, pp. 430-441. (joint work with F. Fomin and F. Grandoni).
  13. Convex Recoloring Revisited: Complexity and Exact Algorithms, Proceedings of COCOON 2009, Springer-Verlag, 2009, Berlin, Lecture Notes in Computer Science 5609, pp. 388-397. (joint work with I. Kanj).
  14. Fully decomposable split graphs, Proceedings of IWOCA 2009, Springer-Verlag, 2009, Berlin, Lecture Notes in Computer Science 5874, pp. 105-112. (joint work with H. Broersma and G. Woeginger).
  15. Fixed-parameter algorithms for Cochromatic Number and Disjoint Rectangle Stabbing, Proceedings of SWAT 2010, Springer-Verlag, 2010, Berlin, Lecture Notes in Computer Science 6139, pp. 334-345. (joint work with P. Heggernes, D. Lokshtanov, V. Raman and S. Saurabh).
  16. Colorings with few colors: counting, enumeration and combinatorial bounds, Proceedings of WG 2010, Springer-Verlag, 2010, Berlin, Lecture Notes in Computer Science 6410, pp. 39-50. (joint work with P. Golovach and J.-F. Couturier).
  17. Enumerating minimal subset feedback vertex sets, Proceedings of WADS 2011, Springer-Verlag, 2011, Berlin, Lecture Notes in Computer Science 6844, pp. 399-410. (joint work with F. Fomin, P. Heggernes, C. Papadopoulos and Y. Villanger).
  18. Exact algorithms for Kayles, Proceedings of WG 2011, Springer-Verlag, 2011, Berlin, Lecture Notes in Computer Science 6968, pp. 59-70. (joint work with H. Bodlaender).
  19. List coloring in the absence of a linear forest, Proceedings of WG 2011, Springer-Verlag, 2011, Berlin, Lecture Notes in Computer Science 6968, pp. 119-130. (joint work with P. Golovach and D. Paulusma).
  20. Minimal dominating sets in graph classes: combinatorial bounds and enumeration, Proceedings of SOFSEM 2012, Springer-Verlag, 2012, Berlin, Lecture Notes in Computer Science 7147, pp. 202-213. (joint work with J.-F. Couturier, P. Heggernes and P. van 't Hof).