Menu Close

Journal papers

[J65] L. Magne, C. Paul, A. SharmaD.M. Thilikos. Edge-treewidth: Algorithmic and combinatorial properties. Discrete Applied Mathematics, 341:40-54, 2023.
[J64] G. Mescoff, C. Paul, D.M. Thilikos. The mixed search game against an agile and visible fugitive is monotone. Discrete Mathematics, 346(4):113345, 2023.
[J63] C. Paul, M. BlĂ€ser. Preface of STACS 2020 Special Issue. Theory of Computing Systems, 67(1):1-3, 2023. 
[J62] G. Mescoff, C. Paul, D.M. Thilikos. A polynomial time algorithm to compute the connected treewidth of a series-parallel graph. Discrete Applied Mathematics, 312:72-85, 2022. 
[J61] M.M. KantĂ©, C. Paul, D.M. Thilikos. A Linear Fixed Parameter Tractable Algorithm for Connected Pathwidth. SIAM Journal on Discrete Mathematics, 36(1):411-435, 2022.
[J60] I. Adler, C. Paul, D.M. Thilikos. Connected search for a lazy robber. Journal of Graph Theory, 97(4):510-552, 2021.
[J59] R. Niedermeier, C. Paul. Preface of STACS 2019 Special Issue. Theory of Computing Systems, 65(4):635-637, 2021. 
[J58] C. Paul, M. Pilipczuk. Special Issue Dedicated to the 13th International Symposium on Parameterized and Exact Computation. Algorithmica, 82(8): 2133-2134, 2020. 
[J57] S. Bessy, M. Bougeret, S. Chaplick, D. Gonçalves, C. Paul. On independent set in B1-EPG graphs. Discrete Applied Mathematics, 278:62-72, 2020. 
[J56] J. Baste, D. GözĂŒpek, C. Paul, I. Sau, M. Shalom, D.M. Thilikos. Parameterized complexity of finding a spanning tree with minimum reload cost diameter. Networks, 75(3):259-277, 2020. 
[J55] S. Limnios, C. Paul, J. Perret and D.M. Thilikos. Edge degeneracy: algorithmic and structural results. Theoretical Computer Science, 839:164-175, 2020. 
[J54]  V. Garnero, C. Paul, I. Sau and D.M. Thilikos. Explicit linear kernels for packing problems. Algorithmica, 81(4):1615-1656, 2019. 
[J53] F. Barbero, C. Paul and M. Pilipczuk. Strong immersion is a well-quasi-ordering for semi-complete digraphs. Journal of Graph Theory, 90(4):484-496, 2019. 
[J52] E.J. Kim, S.I. Oum, C. Paul, I. Sau and D.M. Thilikos. An FPT 2-Approximation for Tree-Cut Decomposition. Algorithmica, 80(1):116,135, 2018. [DOI
[J51] D.G. CorneilS.-I. Oum, C. Paul. Preface: Seventh  Workshop on Graph Classes, Optimization, and Width Parameters, Aussois, France, October 2015. Discrete Applied Mathematics, 248: 1-2, 2018. 
[J50] F. Barbero, C. Paul and M. Pilipczuk. Exploring the complexity of layout parameters in tournaments and semi-complete digraphs. ACM Transactions on Algorithmics, 14(3):38:1-38-31, 2018. 
[J49] J. Baste, C. Paul, I. Sau and C. Scornavacca. Efficient FPT algorithms for (strict) compatibility of unrooted phylogenetic treesBulletin of Mathematical Biology79:920–938, 2017.
[J48] M.M. KantĂ©, E.J. Kim, O. Kwon and C. Paul. An FPT algorithm and a polynomial kernel for linear rankwidth-1 vertex deletion. Algorithmica, 79(1):66-95, 2017. [DOI
[J47] E.J. Kim, C. Paul, I. Sau and D.M. Thilikos. Parameterized algorithms for min-max multiway cut and list digraph homomorphism. Journal of Computer and System Science, 86:191-206, 2017. [DOI
[J46] N. Cohen, D. Gonçalves, E.J. Kim, C. Paul, I. Sau, D.M. Thilikos and M. Weller. A polynomial-time algorithm for outerplanar diameter improvement. Journal of Computer and System Science, 89:315-327, 2017. [DOI
[J45] D. GözĂŒpek, S. Özkan, C. Paul, I. Sau, M. Shalom. Parameterized complexity of the MINCCA problem on graphs of bounded decomposability. Theoretical Computer Science, 690:91-103, 2017. [DOI
[J44] Mark Jones, Christophe Paul, CĂ©line Scornavacca. On the consistency of orthology relationships. BMC Bioinformatics, 17(S-14):251-262, 2016. 
[J43] C. Paul, A. Perez and S. ThomassĂ©. Linear kernel for rooted triplet inconsistency and other problems based on conflict packing technique. Journal of Computer and System Science, 82(2):366-379, 2016. [DOI
[J42] E.J. Kim, A. Langer, C. Paul, F. Reidl, P. Rossmanith, I. Sau, and S. Sikdar. Linear kernels and single-exponential algorithms via protrusion decompositions. ACM Transactions on Algorithms, 12(2):21, 2016. [DOI
[J41] E.J. Kim, C. Paul and G. Philip. A single-exponential FPT algorithm for the K4-minor cover problem. Journal of Computer and System Science, 81(1) :186-207, 2015. 
[J40] P. Golovach, P. Heggernes, P. van’t Hof and C. Paul. Hadwiger number of graphs with small chordality. SIAM Journal on Discrete Applied Mathematics, 29(3) :1427-1451, 2015. 
[J39] V. Garnero, C. Paul, I. Sau and D. Thilikos. Explicit linear kernels via dynamic programming. SIAM Journal on Discrete Mathematics, 29(4) :1864-1894, 2015. 
[J38] G. Joret, C. Paul, I. Sau, S. Saurabh and S. ThomassĂ©. Hitting and harvesting pumpkins. SIAM Journal on Discrete Mathematics, 28(3) :1363-1390, 2014. See also arXiv:1105.2704
[J37] E. Gioan, C. Paul, M. Tedder and D.G. Corneil. Circle Graph Recognition in Time O(n+m).\alpha(n+m). Algorithmica, 69(4):759-788, 2014. See also arXiv:1104.3284
[J36] E. Gioan, C. Paul, M. Tedder and D.G. Corneil. Practical and Efficient Split Decomposition via Graph-Labelled Trees. Algorithmica, 69(4):789-843, 2014. See also arXiv:1104.3283 
[J35] P. Heggernes, P. van’t Hof, B. LĂ©vĂȘque and C. Paul. Contracting chordal graphs and bipartite graphs to paths and trees. Discrete Applied Mathematics, 164(2):444-449, 2014. 
[J34] N. Bousquet, G. Mertzios, C. Paul, I. Sau and S. ThomassĂ©. Parameterized domination in circle graphsTheory of Computing Systems, 54(1):45-72, 2014. [DOI]. See also arXiv:1205.3728 
[J33] P. Heggernes P. van ‘t Hof, B. LĂ©vĂȘque, D. Lokshtanov and C. Paul. Contracting graphs to paths and trees. Algorithmica, 68(1):109-132, 2014. See also arXiv:1104.3677  
[J32] S. Guillemot, F. Havet, C. Paul and A. Perez. On the (non-)existence of polynomial kernels for Pl-free edge modification problems. Algorithmica, 65(4):900-926, 2013. 
[J31] P. Heggernes, P. van ‘t Hof, D. Lokshtanov and C. Paul. Obtaining a bipartite graph by contracting few edges. SIAM Journal on Discrete Mathematics, 27(4):2143-2156, 2013. See also arXiv:1102.5441
[J30] E. Gioan and C. Paul. Split decomposition and graph-labelled trees: characterizations and fully-dynamic algorithms for totally decomposable graphs. Discrete Applied Mathematics, 160(6):708-733, 2012. See also arXiv:0810.1823
[J29] P. Gambette, V. Berry and C. Paul. Quartet and unrooted phylogenetic networks. Journal of Bioinformatics and Computational Biology, 10(4):23 pages, 2012. 
[J28] S. Bessy, F. Fomin, S. Gaspers, C. Paul, A. Perez, S. Saurabh and S. ThomassĂ©. Kernels for feedback arc set in tournaments. Journal of Computer and System Science, 77(6):1071-1078, 2011. 
[J27] C. Crespelle and C. Paul. Fully Dynamic Algorithm for Modular Decomposition and Recognition of Permutation Graphs. Algorithmica, 58(2):405-432, 2010.
[J26] M. Habib and C. Paul. A survey on algorithmic aspects of modular decomposition. Computer Science Review, 4(1):41-59, 2010. 
[J25] S. Bessy and C. Paul and A. Perez. Polynomial kernels for 3-leaf power graph modification problems. Discrete Applied Mathematics, 158(16):1732-1744, 2010. 
[J24] D.H. Huson, R. RuppV. Berry, P. Gambette, C. Paul. Computing galled networks from real data. Bioinformatics, 25(12), 2009. 
[J23] S. Durocher, C. Paul. Kinetic maintenance of mobile k-centres on trees. Discrete Applied Mathematics, 157(7):1432-1446, 2009. 
[J22] S. Guillemot, F. Nicolas, V. Berry and C. Paul. On the approximability results for maximum agreement subtree and maximum compatible tree problems. Discrete Applied Mathematics, 157(7):1555-1570, 2009. 
[J21] C. Paul and J.A. Telle. Branchwidth of chordal graphs. Discrete Applied Mathematics, 157(12):2718-2725, 2009. 
[J20] C. Paul and J.A. Telle. Edge maximal graphs of branchwidth k : the k-branches. Discrete Mathematics, 309(6):1467-1475, 2009. 
[J19] 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. 
[J18]  Y. Villanger, P. Heggerness, C. Paul and J.A. Telle. Interval completion with few edges. In SIAM Journal on Computing, 38(5):2007-2020 , 2009. 
[J17] V. Berry, S. Guillemot, F. Nicolas and C. Paul. Linear time 3-approximation for MAST problem. ACM Transcations on Algorithms, 5(2):1-18, 2009. 
[J16] S. BĂ©rard, C. Chauve and C. Paul. A more efficient algorithm for perfect sorting by reversals. Information Processing Letters, 106:90-95, 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] 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.  
[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. Can transitive orientation make sandwich problems easier? Discrete Mathematics, 307:2030-2041, 2007.
[J11] A. Bergeron, S. BĂ©rard, C. Chauve, and C. Paul. Perfect sorting by reversals is not Always Difficult. IEEE-ACM Transaction on Computational Biology and Bioinformatics, 4(1):4-16, 2007. 
[J10] C. Crespelle and C. Paul. Fully-Dynamic Recognition Algorithm and Certificate for Directed Cographs. Discrete Applied Mathematics, 154(12):1722-1741, 2006. 
[J9] P. Fraigniaud and C. Gavoille and C. Paul. Eclecticism Shrinks Even Small Worlds. Journal of Distributed Computing, 18(4):279-291, 2006. 
[J8] M. Habib and C. Paul. A Simple Linear Time Algorithm for Cograph Recongition. Discrete Applied Mathematics, 145(2):183-197, 2005. 
[J7] C. Gavoille and C. Paul. Distance labeling and split decomposition. Discrete Mathematics, 273(1-3):115-130, 2003. 
[J6] M. Habib and E. Lebhar and C. Paul. A note on finding all homogeneous set sandwiches. Information Processing Letters, 87:147-151, 2003. 
[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. 
[J4] 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. 
[J3] 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. 
[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. 
[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.