Publications


The PostScript and PDF files correspond to research reports or submitted versions.

Unpublished

  1. An O(n^2) algorithm for the minimal interval completion problem, with C. Crespelle. Submitted, 2009. pdf

Journal papers

  1. Computing branchwidth via efficient triangulations and blocks, with F. Fomin and F. Mazoit. Discrete Applied Mathematics 157(12): 2726-2736, 2009.
  2. Minimal interval completion through graph exploration, with K. Suchan. Theoretical Computer Science 410(1): 35-43, 2009.
  3. Feedback vertex set on AT-free graphs, with D. Kratsch and H. Müller. Discrete Applied Mathematics 156(10): 1936-1947, 2008.
  4. Minimal proper interval completions, with I. Rapaport and K. Suchan. Information Processing Letters106(5): 195-202, 2008.
  5. Exact Algorithms for Treewidth and Minimum Fill-In, with F. Fomin, D. Kratsch and Y. Villanger. SIAM Journal on Computing 38(3): 1058-1079, 2008.
  6. On powers of graphs of bounded NLC-width (clique-width), with K. Suchan. Discrete Applied Mathematics 155 (14): 1885-1893, 2007. ps
  7. On treewidth approximations, with V. Bouchitté, D. Kratsch, H. Müller. Discrete Applied Mathematics 136 (2-3): 183-196, 2004. ps
  8. Chordal embeddings of planar graphs, with V. Bouchitté, F. Mazoit. Discrete Mathematics 273 (1-3): 85-102, 2003. ps
  9. Approximating the treewidth of AT-free graphs, with V. Bouchitté. Discrete Applied Mathematics 131 (1-5): 11-37, 2003.  ps
  10. Listing all potential maximal cliques of a graph, withV. Bouchitté.  Theoretical Computer Science 276(1-2): 17-32, 2001.  ps
  11. Treewidth and minimum fill-in: grouping the minimal separators, withV. Bouchitté.  SIAM J. on Computing 31(1): 212-323, 2001.  ps

Proceedings of international conferences

Part of these articles are premiminary versions of the journal papers above.
  1. Constructing Brambles, with M. Chapelle and F. Mazoit. Proceedings 34th International Symposium on Mathematical Foundations of Computer Science (MFCS'09), Volume 5734 of LNCS, 223-234, 2009. pdf
  2. Pathwidth is NP-Hard for Weighted Trees, with R. Mihai. Proceedings 3rd International Workshop: Frontiers in Algorithms (FAW'09), Volume 5598 of LNCS, 181-195, 2009. pdf
  3. On Dissemination Thresholds in Regular and Irregular Graph Classes, with I. Rapaport, K. Suchan, J. Verstraëte. Proceedings 8th Latin American Symposium on Theoretical Informatics (LATIN'08), Volume 4957 of LNCS, 24-35, 2008.
  4. Pathwidth of circular-arc graphs, with K. Suchan. Proceedings 33nd International Workshop on Graph-Theoretic Aspects in Computer Science (WG'07), Volume 4769 of LNCS, 258-269, 2007. pdf
  5. Characterizing minimal interval completions. Towards better understanding of profile and pathwidth, with P. Heggernes, K. Suchan and Y. Villanger. Proceedings 24th Symposium on Theoretical Aspects in Computer Science (STACS'07), Volume 4393 of LNCS, 236-247, 2007. ps
  6. Minimal initerval completions through graph exploration, with K. Suchan. Proceedings 17th International Symposium on Algorithms and Computation (ISAAC'06) , Volume 4288 of LNCS, 517-526, 2006. pdf
  7. Minimal proper interval completions, with I. Rapaport and K. Suchan. Proceedings 32nd International Workshop on Graph-Theoretic Aspects in Computer Science (WG'06) , Volume 4271 of LNCS, 217-228, 2006. pdf
  8. Minimal interval completions, with P. Heggernes, K. Suchan and Y. Villanger. Proceedings 13th European Symposium on Algorithms (ESA 2005), volume 3669 of LNCS, 403-414, 2005. ps
  9. Computing branchwidth via Efficient Triangulations and blocks, with F. Fomin and  F. Mazoit..  Proceedings 31st International Workshop on Graph-Theoretic Aspects in Computer Science (WG'05), volume 3787 of LNCS, 374-384, 2005. ps
  10. Exact (Exponential) Algorithms for Treewidth and Minimum Fill-In, with D. Kratsch and F. Fomin. Proceedings 31st International Colloquium on Automatas, Languages and Programming (ICALP 2004), volume 3142 of LNCS, 568-580, 2004. ps
  11. Feedback Vertex Set and Longest Induced Path on AT-Free Graphs, with D. Kratsch, H. Müller.  Proceedings 29th International Workshop on Graph-Theoretic Aspects in Computer Science (WG'03), volume 2880 of LNCS, 309-321, 2003. ps
  12. Coloring Powers of Graphs of Bounded Clique-Width.  Proceedings 29th International Workshop on Graph-Theoretic Aspects in Computer Science (WG'03), volume 2880 of LNCS, 370-382, 2003. ps
  13. Approximating the treewidth of AT-free graphs, with V. Bouchitté. Proceedings 26th International Workshop on Graph-Theoretic Aspects in Computer Science (WG'00), volume 1928 of LNCS, 59-70, 2000. ps
  14. Listing all potential maximal cliques of a graph, with V. Bouchitté. Proceedings 17th Symposium on Theoretical Aspects in Computer Science (STACS 2000), volume 1770 of LNCS, 503-515, 2000. ps
  15. Treewidth and Minimum Fill-in of Weakly Triangulated Graphs, with Vincent Bouchitté. Proceedings 16th Symposium on Theoretical Aspects in Computer Science (STACS'99), volume 1563 of LNCS, 197-206, 1999. ps
  16. Minimal Triangulations for Graphs with "Few" Minimal Separators, with V. Bouchitté. Proceedings 6th European Symposium on Algorithms (ESA'98), volume 1461 of LNCS, 344-355, 1998. ps

Short papers

  1. Connected search in outerplanar graphs, with F. Fomin and D. Thilikos. 7th International Colloquium on Graph Theory (ICGT 2005).  ps
  2. Treewidth of planar graphs: connections with duality, with V. Bouchitté, F. Mazoit. EuroConference on Combinatorics, Graph Theory and Applications (COMB'01). ps
  3. On treewidth approximations, with V.Bouchitté, D. Kratsch, H. Müller. Cologne-Twente Workshop on Graphs and Combinatorial Optimization (CTW'01). ps
  4. Treewidth: using the potential maximal cliques, with V. Bouchitté. Journées de l'Informatique Messine (JIM 2000). ps

Habilitation thesis

PhD thesis