PublicationsHome | Research | Publications | Teaching | Vitae |
 |
Journal papers
Conference papers
Thesis
^ Journal papers
[J25] C. Crespelle and C. Paul. Fully Dynamic Algorithm for Modular Decomposition and Recognition of Permutation Graphs. Accepted in Algorithmica.
[J24] M. Habib and C. Paul. A survey on algorithmic aspects of modular decomposition. In Computer Science Review, 4(1):41-59, 2010.[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.
[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.
[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.
[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 ]
^ 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
[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 ??? in Lecture Notes in Computer Science, pages ???-???, 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.
[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.
[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.
[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
]