Publications

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

Papers submitted to Journals

[S6] G. Joret, C. Paul, I. Sau, S. Saurabh and S. Thomassé. Hitting and harvesting pumpkins. arXiv:1105.2704

[S5] N. Bousquet, G. Mertzios, C. Paul, I. Sau and S. Thomassé. Parameterized domination in circle graphs.  arXiv:1205.3728

[S4] C. Paul, A. Perez and S. Thomassé. Conflict Packing yields linear vertex-kernels for Rooted Triplet Inconsistency and other problems. arXiv:1101.4491

[S3] P. Heggernes, P. van 't Hof, D. Lokshtanov and C. Paul. Obtaining a Bipartite Graph by Contracting Few Edges. arXiv:1102.5441

[S2] E. Gioan, C. Paul, M. Tedder and D. Corneil.  Circle Graph Recognition in Time O(n+m).\alpha(n+m). arXiv:1104.3284

[S1] E. Gioan, C. Paul, M. Tedder and D. Corneil. Practical and Efficient Split Decomposition via Graph-Labelled Trees.  arXiv:1104.3283

^ Journal papers

[J31] P. Gambette, V. Berry and C. Paul. Quartet and unrooted phylogenetic networks. In Journal of Bioinformatics and Computational Biology, 10(4):23 pages, 2012.

[J30] S. Guillemot, F. Havet, C. Paul and A. Perez. On the (non-)existence of polynomial kernels for Pl-free edge modification problems. In Algorithmica (Online First).

[J29] Pinar Heggernes P. van 't Hof, B. Lévêque, D. Lokshtanov and C. Paul. Contracting Graphs to Paths and Trees. In Algorithmica (Online first). See also arXiv:1104.3677

[J28] E. Gioan and C. Paul. Split decomposition and graph-labelled trees: characterizations and fully-dynamic algorithms for totally decomposable graphs. In Discrete Applied Mathematics, 160(6):708-733, 2011. See also arXiv:0810.1823

[J27] S. Bessy, F. Fomin, S. Gaspers, C. Paul, A. Perez, S. Saurabh and S. Thomassé. Kernels for feedback arc set in tournaments. In Journal of Computer and System Science, 77(6):1071-1078, 2011.

[J26] S. Bessy and C. Paul and A. Perez. Polynomial kernels for 3-leaf power graph modification problems. In Discrete Applied Mathematics, 158(16) :1732-1744, 2010.
[ pdf file ]

[J25] C. Crespelle and C. Paul. Fully Dynamic Algorithm for Modular Decomposition and Recognition of Permutation Graphs. In Algorithmica, 58(2) :405-432, 2010.
[ pdf file ]

[J24] M. Habib and C. Paul. A survey on algorithmic aspects of modular decomposition. In Computer Science Review, 4(1):41-59, 2010.
[ pdf file ]

[J23] S. Bérard, A. Chateau, C. Chauve, C. Paul and E. Tannier. Computation of perfect  DCJ rearrangement with linear and circular chromosomes. In Journal of Computational Biology,  16(10):1287-1309, 2009.
[ pdf file ]

[J21] V. Berry, S. Guillemot, F. Nicolas and C. Paul. Linear time 3-approximation for MAST problem. To appear in ACM Transcations on Algorithms,  5(2):1-18, 2009.
[ pdf file ]

[J21] C. Paul and J.A. Telle. Branchwidth of chordal graphs. In Discrete Applied Mathematics, 157(12):2718-2725, 2009. doi:10.1016/j.dam.2008.08.006

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

[J19] 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

[J18] C. Paul and J.A. Telle. Edge maximal graphs of branchwidth k : the k-branches. In Discrete Mathematics, 309(6):1467-1475, 2009.  doi:10.1016/j.disc.2008.02.030

[J17] Stephane Durocher, Christophe Paul. Kinetic maintenance of mobile k-centres on trees. In Discrete Applied Mathematics, 157(7):1432-1446, 2009. doi:10.1016/j.dam.2008.10.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.
 [ pdf file ]

[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.
 [ pdf file ]

[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.
[ pdf file ]

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

[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 ]

^ Books

[B1] C. Paul and M. Habib. International Workshop on Theoretic Concepts in Computer Science - WG, number 5911 of Lecture Notes in Computer Science, 2010.

^ Conference papers


[C41] N. Bousquet, G. Mertzios, C. Paul, I. Sau and S. Thomasse ́. Parameterized domination in circle graphs. In Graph Theoretical Concepts in Computer Science - WG. Number ? ? ? in Lecture Notes in Computer Science, pages ? ? ?- ? ? ?, 2012.

[C40] E.J. Kim, C. Paul and G. Philip. Parameterized K4-cover in single exponential time. In Scandinavian Workshop On Algorithmic Theory - SWAT. Number 7357 in Lecture Notes in Computer Science, pages 119-130, 2012.

[C39] P. Heggernes, P. van’t Hof, B. Lévêque, D. Lokshtanov and C. Paul. Contracting graphs to paths and trees In International Symposium on Parameterized and exact Computation - IPEC. Number 7112 in Lecture Notes in Computer Science, pages 55-66, 2011.

[C38] G. Joret, C. Paul, I. Sau, S. Saurabh and S. Thomasse ́. Hitting and harvesting pumpkins. In European Symposium on Algorithms - ESA. Number 6942 in Lecture Notes in Computer Science, pages 394-407, 2011.

[C37] C. Paul, A. Perez and S. Thomasse ́. Conflict packing yields linear vertex-kernels for k- fast, k-dense rti and a related problem. In Mathematical Foundations of Computer Science - MFCS. Number 6907 in Lecture Notes in Computer Science, pages 497-507, 2011.

[C36] P. Heggernes, P. van't Hof, B. Lévêque and C. Paul. Contracting chordal graphs and bipartite graphs to paths and trees. Latin-American Algorithms, Graphs and Optimization Symposium - LAGOS. Number ??? in Electronic Notes in Discrete Mathematics, pages ???, 2011.

[C35] S. Guillemot, C. Paul and A. Perez. On the (non-)existence of polynomial kernels for Pl -free edge modification problems. In International Symposium on Parameterized and Exact Computation - IPEC. Number 6478 in Lecture Notes in Computer Science, pages 147-157, 2010.

[C34] M. Fellows, P. Giannopoulos, C. Knauer, C. Paul, F. Rosamond, S. Whitesides and  N. Yu. Milling a graph with turn costs : a parameterized complexity perspective. In Graph Theoretical Concepts in Computer Science - WG. Number 6410 in Lecture Notes in Computer Science, pages 123-134, 2010.

[C33] P. Heggernes, D. Lokshtanov, J. Nederlof, C. Paul and J.A. Telle. Generalized graph clustering : recognizing (p,q)-cluster. In Graph Theoretical Concepts in Computer Science - WG. Number 6410 in Lecture Notes in Computer Science, pages 171-183, 2010.

[C32] S. Bessy and F. Fomin, S. Gaspers, C. Paul, A. Perez, S. Saurabh and S. Thomassé. Kernels for Feedback Arc Set In Tournaments. In International Workshop On Combinatorial Algorithms - FSTTCS. Number 4 in Leibnitz International Proceedings in Informatics, pages 37-47, 2009.

[C31] S. Bessy and C. Paul and A. Perez. Polynomial kernels for 3-leaf power graph modification problems. In International Workshop On Combinatorial Algorithms - IWOCA. Number 5874 in Lecture Notes in Computer Science, pages 72-80, 2009.

[C30] P. Gambette, V. Berry and C. Paul. The structure of level-k phylogenetic networks. In Annual Symposium on Combinatorial Pattern Matching - CPM. Number 5577 in Lecture Notes in Computer Science, pages 289-300, 2009.

[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.
[ pdf file ]

[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 ]