Publications

Home | Research | Publications | Teaching | Vitae		 photo
Journal papers
Conference papers
Thesis

^ Journal papers

[J23] C. Crespelle and C. Paul. Fully Dynamic Algorithm for Modular Decomposition and Recognition of Permutation Graphs. Accepted in Algorithmica.

[J22] Stephane Durocher, Christophe Paul. Kinetic maintenance of mobile k-centres on trees. In
Discrete Applied Mathematics. doi:10.1016/j.dam.2008.10.006

[J21] V. Berry, S. Guillemot, F. Nicolas and C. Paul. Linear time 3-approximation for MAST problem. To appear in ACM Transcations on Algorithms.

[J20] V. Berry, S. Guillemot, F. Nicolas and C. Paul. On the approximability results for maximum agreement subtree and maximum compatible tree problems. In Discrete Applied Mathematics. doi:10.1016/j.dam.2008.06.007

[J19] C. Paul and J.A. Telle. Edge maximal graphs of branchwidth k : the k-branches. In Discrete Mathematics.  doi:10.1016/j.disc.2008.02.030

[J18] Y. Villanger, P. Heggerness, C. Paul and J.A. Telle. Interval completion with few edges. In SIAM Journal on Computing, 38(5), 2009.  doi:10.1137/070710913

[J17] C. Paul and J.A. Telle. Branchwidth of chordal graphs. In Discrete Applied Mathematics. doi:10.1016/j.dam.2008.08.006

[J16] A. Bretscher, D. Corneil, M. Habib and C. Paul. A simple linear time LexBFS cograph recognition algorithm. SIAM Journal on Discrete Mathematics, 22(4) :1277-1296, 2008.

[J15] C. Gavoille and C. Paul, Optimal Distance Labeling for Interval and Circular-Arc Graphs. SIAM Journal on Discrete Mathematics, 22(3) :1239-1258, 2008.

[J14] S. Bérard, C. Chauve and C. Paul. A more efficient algorithm for perfect sorting by reversals.  Information Processing Letters, 106:90-95, 2008.

[J13] B.M. Bui Xuan and M. habib and C. Paul. Competitive Graph Searches. Theoretical Computer Science, 393(1-3):72-80, 2008.

[J12] M. Habib, D. Kelly, E. Lebhar and C. Paul. On poset Sandwich Problems. Discrete Mathematics, 307:2030-2041, 2007.
[ pdf file ]

[J11] A. Bergeron, S. Bérard, C. Chauve, and C. Paul. Sorting by Intervals with Common Intervals is not Always Difficult. IEEE-ACM Transaction on Computational Biology and Bioinformatics, 4(1):4-16, 2007.
[ pdf file ]

[J10] C. Crespelle and C. Paul. Fully-Dynamic Recognition Algorithm and Certificate for Directed Cographs. Discrete Applied Mathematics, 154(12):1722-1741, 2006.
[ pdf file ]

[J9] P. Fraigniaud and C. Gavoille and C. Paul. Eclecticism Shrinks Even Small Worlds. Journal of Distributed Computing, 18(4):279-291, 2006.
[ pdf file ]

[J8] M. Habib and C. Paul. A Simple Linear Time Algorithm for Cograph Recongition. Discrete Applied Mathematics, 145(2):183-197, 2005.
[ pdf file ]

[J7] C. Gavoille and C. Paul. Distance labeling and split decomposition. Discrete Mathematics, 273(1-3):115-130, 2003.
[ bib | postscript file ]

[J6] M. Habib and E. Lebhar and C. Paul. A Note on Finding All Homogeneous Set Sandwiches. Information Processing Letters, 87:147-151, 2003.
[bib]

[J5] D. Corneil, F. Dragan, M. Habib, and C. Paul. Diameter determination on restricted graph families. Discrete Applied Mathematics, 113(2-3):143-166, 2001.
[ bib | postscript file ]

[J4] G. Damiand, M. Habib, and C. Paul. A simple paradigm for graph recognition : application to cographs and distance hereditary graphs. Theoretical Computer Science, 263:99-111, 2001.
[ bib | postscript file ]

[J3] M. Habib, C. Paul, and L. Viennot. Linear time recognition of p4-indifference graphs. Discrete Mathematics and Theoretical Computer Science, 4(2):173-178, 2001. Special issue: Graph Decomposition.
[ bib | postscript file ]

[J2] M. Habib, R. McConnell, C. Paul, and L. Viennot. Lex-bfs and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing. Theoretical Computer Science, 234:59-84, 2000.
[ bib | postscript file ]

[J1] M. Habib, C. Paul, and L. Viennot. Partition refinement : an interested algorithmic tool kit. International Journal of Foundation of Computer Science, 10(2):147-170, 1999.
[ bib | postscript file ]

^ Conference papers

[C29] S. Bérard, A. Chateau, C. Chauve, C. Paul and E. Tannier. Perfect DCJ rearrangement. In Annual RECOMB Satellite Workshop on Comparative Genomic - RCG. Number 5267 in Lecture Notes in Bioinformatics, pages 156-167, 2008.

[C28] D. Bremner, J. Lenchner, G. Liotta, C. Paul, M. Pouget, S. Stolpner, S. Wismath. A note on α-drawable k-trees. In Canadian Conference on Computational Geometry - CCCG. 2008.

[C27] M. Tedder, D. Corneil, M. Habib and C. Paul. Simple, linear-time modular decomposition. In International Colloquium on Automata, Languages and Programming - ICALP. Number 5125 in Lecture Notes in Computer Science, pages 634-645, 2008.

[C26] E. Gioan and C. Paul. Dynamic distance hereditary graphs using split decomposition. In International Symposium on Algorithms and Computation - ISAAC, number 4835 in Lecture Notes in Computer Science, pages 41-51, 2007.
[ pdf file ]

[C25] S. Durocher and C. Paul. Kinetic maintenance of mobile k-centre in trees. In International Symposium on Algorithms and Computation - ISAAC, number 4825 in Lecture Notes in Computer Science, pages 341-352, 2007.
[ pdf file ]

[C24] P. Heggerness, C. Paul,  J.A. Telle and Y. Villanger. Interval completion with few edges. In 39th ACM Symposium on Theory of Computing - STOC, pages 347-381, 2007.
[ pdf file ]

[C23] C. Paul, A. Proskurowski and J.A. Telle. Algorithmic generation of graphs of branchwidth <= k. In 32nd International Workshop on Graph Theoretical Concepts in Computer Science - WG, number 4271 in Lecture Notes in Computer Science, pages 206-216, 2006.
[ pdf file ]

[C22] B.M. Bui Xuan, M. Habib and C. Paul. Revisiting Uno and Yagiura's Algorithm. In  International Symposium on Algorithms and Computation - ISAAC, number 3827 in Lecture Notes in Computer Science, pages 146--155, 2005.
[ pdf file ]

[C21] C. Paul and J.A. Telle. New Tools and Simpler Algorithms for Branchwidth. In European Symposium on Algorithms - ESA, number 3669 in Lecture Notes in Computer Science, pages 379-390, 2005.
[ pdf file ]

[C20] A. Bergeron, S. Bérard, C. Chauve and C. Paul. Sorting by Intervals with Common Intervals is not Always Difficult. In International Workshop on Algorithm in Bioinformatics - WABI, number 3692 in Lecture Notes in Computer Science, pages 228-238, 2005.
[ pdf file ]

[C19] C. Paul and J.A. Telle. Edge-maximal Graphs of Branchwidth $k$ and Graphs with Branchwidth Greater than Treewidth. In International Conference on Graph Theory - ICGT, number 23 in Electronic Notes in Discrete Mathematics, pages 363-368, 2005.
[ pdf file ]

[C18] V. Berry, S. Guillemot, F. Nicolas and C. Paul. On the Approximation of Computing Evolutionary Trees. In 11th International Computing and Combinatorics Conference - COCOON, number 3595 in Lecture Notes in Computer Science, pages 115--125, 2005.
[ pdf file ]

[C17] C. Crespelle and C. Paul. Fully Dynamic Algorithm for Modular Decomposition and Recognition of Permutation Graphs. In 31st International Workshop on Graph Theoretical Concepts in Computer Science - WG, number 3787 in Lecture Notes in Computer Science, pages 38--48, 2005.
[ pdf file ]

[C16] M. Habib, F. de Montgolfier and C. Paul. A simple linear-time modular decomposition algorithm. 9th Scandinavian Workshop on Algorithm Theory - SWAT, number 3111 in Lecture Notes in Computer Science, pages 187-198, 2004.
[ pdf file ]

[C15] M. Habib, C. Paul and M. Raffinot. Common connected Components of Interval Graphs. 15th Annual Combinatorial Pattern Matching Symposium - CPM, number 3109 in Lecture Notes in Computer Science, pages 347-358, 2004.
[ pdf file ]

[C14] C. Crespelle and C. Paul. Fully-Dynamic Recognition Algorithm and Certificate for Directed Cographs. In 30th International Workshop on Graph Theoretical Concepts in Computer Science - WG, number 3353 in Lecture Notes in Computer Science, pages 93--104, 2004.
[ pdf file ]

[C13] P. Fraigniaud, C. Gavoille and C. Paul. Eclecticism Shrinks Even Small World. In 23rd Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing - PODC, pages 168--178, 2004.
[ pdf file ]

[C12] C. Gavoille and C. Paul. Optimal Distance Labeling Scheme for Interval and Circular-arc Graphs. In G. Di Battista and U. Zwich, editor, Algorithms - ESA number 2832 in Lecture Notes in Computer Science, pages 254--265. 11th Annual European Symposium on Algorithms, 2003.
[ bib | postscript file ]

[C11] M. Habib and D. Kelly and E. Lebhar and C. Paul. On poset Sandwich Problems. In European Conference on Combinatorics, Graphs Theory and Applications, Pragues, EuroComb 2003. 

[C10] M. Habib and C. Paul and J.A. Telle. A linear-time algorithm for recognition of catval graphs. In European Conference on Combinatorics, Graphs Theory and Applications, Pragues, EuroComb 2003. 
[ bib | postscript file ]

[C9] A. Bretscher and D.G. Corneil and M. Habib and C. Paul. A Simple Linear Time LexBFS Cograph Recognition Algorithm. In H. Bodlaender, editor, Graph-Theoretic Concepts in Computer Science - WG, number 2880 in Lecture Notes in Computer Science, pages 119-130, 2003.

[C8] M. Bouklit and D. Coudert and J.-F. Lalande and C. Paul and H. Rivano. Approximate multicommodity flow for WDM networks design. SIROCCO 10, number 17 of Proceedings in Informatics, Carleton Scientific, pages 43--56. June 2003.
[ bib | pdf file ]

[C7] Gavoille, M. Katz, N. Katz, C. Paul, and D. Peleg. Approximate distance labeling scheme. In Meyer auf der Heide, editor, Algorithms - ESA 2001, number 2161 in Lecture Notes in Computer Science, pages 476-487. 9th Annual European Symposium on Algorithms, 2001.
[ bib | postscript file ]

[C6] C. Gavoille and C. Paul. Split decomposition and distance labelling: An optimal scheme for distance hereditary graph. In Euroconference on Combinatorics, Graph Theory and Applications, COMB'01, volume 10 of Electronique Notes on Discrete Mathematics, 2001.
[ bib | postscript file ]

[C5] C. Gavoille and C. Paul. Approximate distance labeling scheme. In 6th International Conference on Graph Theory, IGCT, volume 5 of Electronique Notes on Discrete Mathematics, 2000.
[ bib | postscript file ]

[C4] D. Corneil, F. Dragan, M. Habib, and C. Paul. Diameter determination on restricted graph families. In Graph-Theoretic Concepts in Computer Science, WG'98, volume 1517 of Lecture Notes in Computer Science. 24st Internationnal Workshop WG'98, 1998.
[ bib | postscript file ]

[C3] M. Habib, C. Paul, and L. Viennot. A synthesis on partition refinement: a useful routine for strings, graphs, boolean matrices and automata. In STACS 98, number 1373 in LNCS, pages 25-38. 15th Symposium on Theoretical Aspect of Computer Science, 1998.
[ bib | postscript file ]

[C2] P. Galinier, M. Habib, and C. Paul. Chordal graphs and their clique graph. In M. Nagl (Ed.), editor, Graph-Theoretic Concepts in Computer Science, WG'95, volume 1017 of Lecture Notes in Computer Science, pages 358-371, Aachen, Germany, June 1995. 21st Internationnal Workshop WG'95, Springer.
[ bib | postscript file ]

[C1] P. Galinier, M. Habib, and C. Paul. Maximal intersection search: a new algorithm for chordal graph recognition. Technical Report 95044, LIRM Montpellier, October 1995.
[ bib | postscript file ]

^ Dissertations

[D2] C. Paul. Aspects algorithmiques de la décomposition modulaire.  Habilitation à diriger des recherches, Université de Montpellier 2, France, 2006.
[ pdf file ]

[D1] C. Paul. Parcours en largeur lexicographique : un algorithme de partitionnement, application aux graphes et généralisation. PhD thesis, LIRMM, Université de Montpellier II, 1998.
[ bib | postscript file ]