{"id":2266,"date":"2024-04-17T13:36:27","date_gmt":"2024-04-17T11:36:27","guid":{"rendered":"https:\/\/perso.lirmm.fr\/christophe-paul\/?page_id=2266"},"modified":"2024-09-13T17:01:03","modified_gmt":"2024-09-13T15:01:03","slug":"publication","status":"publish","type":"page","link":"https:\/\/www.lirmm.fr\/christophe-paul\/publication\/","title":{"rendered":"Publications"},"content":{"rendered":"\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t\t
\n\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t

Publications<\/strong> (complete versions gathered with the extended abstract, if any)<\/h4>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t

[92]\u00a0<\/strong>C. Paul,<\/span>\u00a0<\/span>E. Protopapas, D.M. Thilikos and S. Wiederrecht. Obstructions to Erd\u00f6s-Posa dualities for minors. In\u00a0IEEE Symposium on Foundations of Computer Science – FOCS<\/strong>. 2024, to appear.
See also arXiv:2407.09671<\/a><\/i><\/b>, 2024.<\/em><\/span><\/p>

[91] <\/strong>C. Paul, E. Protopapas, D.M. Thilikos and S. Wiederrecht.\u00a0<\/span>Delineating Half-Integrality of the Erd\u0151s-P\u00f3sa Property for Minors: the Case of Surfaces<\/a>. In \u00a0International Colloquium on Automata, Logic and Programming \u2013 ICALP<\/em><\/strong>. Number 297 of\u00a0Leibnitz International Proceedings in Informatics<\/em>, pages 35:1-35:20, 2024.
See also arXiv:2406.16647<\/a><\/i><\/b>, 2024.<\/p>

[90]<\/strong> D.G. Corneil, M. Habib, C. Paul, M. Tedder. A recursive linear time modular decomposition algorithm via LexBFS.\u00a0arXiv:0710.3901<\/a><\/strong><\/em>, 2024.
Extended abstract:<\/i> Simple, linear-time modular decomposition.\u00a0In<\/span> International Colloquium on Automata, Languages and Programming \u2013 ICALP<\/em><\/strong>. Number 5125 in\u00a0<\/span>Lecture Notes in Computer Science<\/em>, pages 634-645, 2008.
Implementation of the algorithm (by C. Bouvier):\u00a0<\/i>\u00a0GitHub:modular decomposition<\/strong><\/a><\/em><\/span><\/p>

[89]<\/strong> C. Paul, E. Protopapas, D.M. Thilikos. Graph Parameters, Universal Obstructions, and WQO<\/span>. arXiv:2304.03688<\/a><\/em><\/strong>, 2023.<\/p>

[88]<\/strong> C. Paul, E. Protopapas.\u00a0<\/span>Tree-Layout Based Graph Classes: Proper Chordal Graphs<\/a>. In International Symposium on Theoretical Aspects of Computer Science \u2013 STACS<\/em><\/strong>. Number 289 of\u00a0Leibnitz International Proceedings in Informatics<\/em>, pages 55:1-55:18, 2024.
See also <\/span>arXiv:2211.07550<\/a><\/em><\/strong>, 2022.<\/span><\/p>

[87]<\/strong> C. Paul, E. Protopapas, D.M. Thilikos. Universal obstructions of graph parameters<\/a>. arXiv<\/strong><\/em> 2304.14121, 2023.<\/p>

[86]<\/strong> L. Magne<\/span>,\u00a0C. Paul,\u00a0A. Sharma<\/span>,\u00a0D.M. Thilikos.\u00a0<\/span>Edge-treewidth: Algorithmic and combinatorial properties<\/a>.\u00a0Discrete Applied Mathematics<\/em><\/strong>, 341:40-54, 2023.
See also arXiv:2112.07524<\/a><\/strong><\/em>, 2021.<\/p>

[85]<\/strong> G. Mescoff<\/span>,\u00a0C. Paul,\u00a0D.M. Thilikos.\u00a0<\/span>The mixed search game against an agile and visible fugitive is monotone<\/a>.\u00a0Discrete Mathematics<\/em><\/strong>, 346(4):113345, 2023.
See also\u00a0arXiv:2204.10691<\/a><\/strong><\/em>, 2022.<\/p>

[84]<\/strong> C. Paul,\u00a0M. Bl\u00e4ser.\u00a0<\/span>Preface of STACS 2020<\/a>. Special issue of\u00a0Theory of Computing Systems<\/em><\/strong>, 67(1):1-3, 2023.<\/p>

[83]<\/strong> G. Mescoff<\/span>,\u00a0C. Paul,\u00a0D.M. Thilikos.\u00a0<\/span>A polynomial time algorithm to compute the connected treewidth of a series-parallel graph<\/a>.\u00a0Discrete Applied Mathematics<\/strong>,<\/em>\u00a0312:72-85, 2022.
See also arXiv:2004.00547<\/a><\/strong>, 2020.<\/em><\/p>

[82]<\/strong> M.M. Kant\u00e9<\/span>,\u00a0C. Paul,\u00a0D.M. Thilikos.\u00a0<\/span>A Linear Fixed Parameter Tractable Algorithm for Connected Pathwidth<\/a>.\u00a0SIAM Journal on Discrete Mathematics<\/em>,<\/strong> 36(1):411-435, 2022.
Extended abstract<\/em><\/strong><\/a> in <\/span>Annual European Symposium on Algorithms \u2013\u00a0<\/em>ESA<\/em><\/strong>. Number 173 of\u00a0<\/span>Leibnitz International Proceedings in Informatics<\/em>, pages\u00a064:1-64:16, 2020.
See also\u00a0arXiv:2004.11937<\/a><\/strong>, 2020.<\/em><\/span><\/p>

[81]<\/strong> S. H\u00f8gemo<\/span>, B. Bergougnoux<\/span>, U. Brandes<\/span>, C. Paul, J.A. Telle.\u00a0<\/span>On Dasgupta\u2019s Hierarchical Clustering Objective and Its Relation to Other Graph Parameters<\/a>.\u00a0In International Symposium\u00a0Fundamentals of Computation Theory \u2013 FCT<\/em><\/strong>. Number 12867 of\u00a0Lecture Notes in Computer Science<\/em>, pages\u00a0287-300, 2021.
See also\u00a0<\/strong>arXiv:2105.12093<\/a><\/strong><\/em>, 2021.<\/p>

[80]<\/strong> I. Adler<\/span>,\u00a0C. Paul,\u00a0D.M. Thilikos.\u00a0<\/span>Connected search for a lazy robber<\/a>.\u00a0Journal of Graph Theory<\/em><\/strong>, 97(4):510-552, 2021.
Extended abstract<\/a><\/strong> <\/em>in <\/span>IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science \u2013\u00a0<\/em>FSTTCS.<\/em><\/strong>\u00a0Number 150 of\u00a0<\/span>Leibnitz International Proceedings in Informatics<\/em>, page 7:1-7:14, 2019.<\/span><\/p>

[79]<\/strong> R. Niedermeier<\/span>,\u00a0C. Paul.\u00a0Preface of STACS 2019<\/a> Special Issue of\u00a0Theory of Computing Systems<\/em><\/strong>, 65(4):635-637, 2021.<\/p>

[78]<\/strong> C. Paul,\u00a0M. Pilipczuk.\u00a0<\/span>Special Issue Dedicated to the 13th International Symposium on Parameterized and Exact Computation<\/a>.\u00a0Algorithmica<\/em><\/strong>, 82(8): 2133-2134, 2020.<\/p>

[77]<\/strong> S. H\u00f8gemo<\/span>, C. Paul, J.A.\u00a0Telle.\u00a0<\/span>Hierarchical Clusterings of Unweighted Graphs<\/a>. In International Symposium on Mathematical Foundations of Computer Science \u2013\u00a0<\/strong><\/em>MFCS<\/em><\/strong>. Number 173 of\u00a0Leibnitz International Proceedings in Informatics<\/em>, pages\u00a047:1-47:13, 2020.
See also arXiv:2008.03061<\/a><\/strong><\/em>, 2020.<\/p>

[76]<\/strong> S. Bessy, M. Bougeret, S. Chaplick, D. Gon\u00e7alves, C. Paul.\u00a0On independent set in B1-EPG graphs<\/a>.\u00a0Discrete Applied Mathematics<\/em><\/strong>, 278:62-72, 2020.
Extended abstract<\/em><\/a><\/strong> in <\/span>Workshop on Approximation and Online Algorithms \u2013 WAOA<\/em><\/strong>. Number 9499 of\u00a0<\/span>Lecture Notes in Computer Science\u00a0<\/em>, page 158-169, 2015.
See also arXiv:1510.00598<\/a><\/strong><\/em>, 2015.<\/span><\/p>

[75]<\/strong> J. Baste, D. G\u00f6z\u00fcpek, C. Paul, I. Sau, M. Shalom, D.M. Thilikos. Parameterized complexity of finding a spanning tree with minimum reload cost diameter<\/a>.\u00a0Networks<\/em><\/strong>, 75(3):259-277, 2020.
Extended abstract<\/a><\/strong><\/em> in <\/span>International Symposium on Parameterized and Exact Computation \u2013 IPEC<\/em><\/strong>. Number 89 of\u00a0<\/span>Leibnitz International Proceedings in Informatics<\/em>, page 3:1-3:12, 2017.
See also\u00a0arXiv:1703.01686<\/a><\/strong><\/em>, 2017.<\/em><\/span><\/p>

[74]<\/strong> S. Limnios, C. Paul, J. Perret and D.M. Thilikos. Edge degeneracy: algorithmic and structural results<\/a>.\u00a0Theoretical Computer Science<\/em><\/strong>, 839:164-175, 2020.
See also\u00a0arXiv:2009.03809<\/a><\/strong><\/em>, 2020.<\/em><\/p>

[73]<\/strong> C. Paul, M. Bl\u00e4ser. Proceedings of the\u00a0<\/a><\/span>37th International Symposium on Theoretical Aspects of Computer Science \u2013 STACS\u201920<\/strong><\/em>. Number 154 of Leibnitz International Proceedings in Informatics, 2020.<\/em><\/p>

[72]<\/strong> V. Garnero, C. Paul, I. Sau and D.M. Thilikos. Explicit linear kernels for packing problems.<\/a>\u00a0Algorithmica<\/em><\/strong>, 81(4):1615-1656, 2019.
See also\u00a0arXiv:1610.06131<\/a><\/strong><\/em>, 2016.<\/p>

[71]<\/strong> F. Barbero, C. Paul and M. Pilipczuk. Strong immersion is a well-quasi-ordering for semi-complete digraphs<\/a>.\u00a0Journal of Graph Theory<\/em><\/strong>, 90(4):484-496, 2019.
See also\u00a0arXiv:1707.03563<\/a><\/strong><\/em>, 2017.<\/em><\/p>

[70]<\/strong> C. Paul, R. Niedermeier. Proceedings of the\u00a0<\/a><\/span>36th International Symposium on Theoretical Aspects of Computer Science \u2013 STACS\u201919<\/em><\/strong>. Number 129 of Leibnitz International Proceedings in Informatics, 2019.<\/em><\/p>

[69]\u00a0<\/strong>C. Paul, M. Pilipczuk. Proceedings of the\u00a0<\/a><\/span>13th International Symposium on Parameterized and Exact Computation \u2013 IPEC\u201918. <\/strong><\/em>Number\u00a0115 of Leibnitz International Proceedings in Informatics, 2019.<\/em><\/p>

[68]<\/strong> E.J. Kim, S.I. Oum, C. Paul, I. Sau and D.M. Thilikos. An FPT 2-Approximation for Tree-Cut Decomposition<\/a>.\u00a0Algorithmica<\/strong><\/em>, 80(1):116,135, 2018.
Extended abstract<\/a><\/strong><\/em> in <\/span>Workshop on Approximation and Online Algorithms \u2013 WAOA<\/em>.<\/strong> Number 9499 of\u00a0<\/span>Lecture Notes in Computer Science\u00a0<\/em>, page 35-46, 2015.
See also\u00a0arXiv:1509.04880<\/a><\/strong><\/em>,<\/em> 2015.<\/span><\/p>

[67]<\/strong> D.G. Cor<\/span>neil<\/span>,\u00a0S.-I. Oum<\/span>,\u00a0C. Paul.\u00a0Preface: Seventh \u00a0Workshop on Graph Classes, Optimization, and Width Parameters, Aussois, France, October 2015<\/a>.\u00a0Discrete Applied Mathematics<\/strong><\/em>, 248: 1-2, 2018.<\/p>

[66]<\/strong> F. Barbero, C. Paul and M. Pilipczuk. Exploring the complexity of layout parameters in tournaments and semi-complete digraphs<\/a>.\u00a0ACM Transactions on Algorithmics<\/strong><\/em>, 14(3):38:1-38-31, 2018.
Extended abstract<\/a><\/strong><\/em> in<\/span> International Colloquim on Automata, Languages, and Programming \u2013 ICALP<\/em><\/strong>. Number 80 of\u00a0<\/span>Leibnitz International Proceedings in Informatics<\/em>, page 70:1-70:13, 2017.
See also\u00a0arXiv:1706.00617<\/a><\/strong><\/em>, 2017.<\/em><\/span><\/p>

[65]<\/strong> M.M. Kant\u00e9, E.J. Kim, O. Kwon and C. Paul. An FPT algorithm and a polynomial kernel for linear rankwidth-1 vertex deletion<\/a>.\u00a0Algorithmica<\/strong><\/em>, 79(1):66-95, 2017.\u00a0
Extended abstract<\/a><\/strong><\/em> in<\/span> International Symposium on Parameterized and Exact Computation \u2013 IPEC<\/em><\/strong>. Number 43 of\u00a0<\/span>Leibnitz International Proceedings in Informatics<\/em>, page 138-150, 2015.
See also\u00a0arXiv:1504.05905<\/a><\/strong><\/em>, 2015.<\/span><\/p>

[64]<\/strong> E.J. Kim, C. Paul, I. Sau and D.M. Thilikos. Parameterized algorithms for min-max multiway cut and list digraph homomorphism<\/a>.\u00a0Journal of Computer and System Science<\/strong><\/em>, 86:191-206, 2017.
Extended abstract<\/a><\/strong><\/em> in <\/span>International Symposium on Parameterized and Exact Computation \u2013 IPEC<\/em><\/strong>. Number 43 of\u00a0<\/span>Leibnitz International Proceedings in Informatics<\/em>, page 78-89, 2015.
See also\u00a0arXiv:1509.07404<\/a><\/strong><\/em>, 2015.<\/span><\/p>

[63]<\/strong> N. Cohen, D. Gon\u00e7alves, E.J. Kim, C. Paul, I. Sau, D.M. Thilikos and M. Weller. A polynomial-time algorithm for outerplanar diameter improvement<\/a>.\u00a0Journal of Computer and System Science,<\/em><\/strong> 89:315-327, 2017.
Extended abstract<\/a><\/strong><\/em> in <\/span>International Workshop on\u00a0<\/strong><\/em>Graph Theoretical Concepts in Computer Science \u2013 WG<\/em><\/strong>. Number 8747 of\u00a0<\/span>Lecture Notes in Computer Science\u00a0<\/em>, page 201-213, 2015.
See also\u00a0arXiv:1403.5702<\/a><\/strong><\/em>, 2014.<\/span><\/p>

[62]<\/strong> \u00a0<\/b>D. G\u00f6z\u00fcpek, S. \u00d6zkan, C. Paul, I. Sau, M. Shalom. Parameterized complexity of the MINCCA problem on graphs of bounded decomposability<\/a>.\u00a0Theoretical Computer Science,<\/em><\/strong> 690:91-103, 2017.
Extended abstract<\/strong><\/em><\/a> in <\/span>International Workshop on\u00a0<\/strong><\/em>Graph Theoretical Concepts in Computer Science \u2013 WG<\/em><\/strong>. Number 9941 of\u00a0<\/span>Lecture Notes in Computer Science\u00a0<\/em>, page 195-206, 2016.
See also\u00a0arXiv:1605.00532<\/a><\/strong><\/em>, 2016.<\/span><\/p>

[61]<\/strong> M. Jones<\/span>,\u00a0C. Paul,\u00a0C. Scornavacca.\u00a0<\/span>On the consistency of orthology relationships.<\/a> In RECOMB Comparative Genomics Satellite Workshop \u2013 RECOMB-CG.\u00a0BMC Bioinformatics<\/strong><\/em>, 17(S-14):251-262, 2016.<\/p>

[60]<\/strong> J. Baste, C. Paul, I. Sau and C. Scornavacca. Efficient FPT algorithms for (strict) compatibility of unrooted phylogenetic trees<\/a>.\u00a0Bulletin of Mathematical Biology<\/strong><\/em>, 79:<\/span>920\u2013938,\u00a02017.
<\/span>Extended abstract<\/strong><\/em><\/a> in\u00a0<\/span>International Conference on Algorithmic Aspects in Information and Management – AAIM<\/em>.<\/strong> Number 9778 of\u00a0<\/span>Lecture Notes in Computer Science\u00a0<\/em>, page 53-64, 2016.
See also\u00a0arXiv:1604.03008<\/a><\/strong><\/em>, 2016.<\/span><\/p>

[59]<\/strong> C. Paul, A. Perez and S. Thomass\u00e9. Linear kernel for rooted triplet inconsistency and other problems based on conflict packing technique<\/a>.\u00a0Journal of Computer and System Science<\/strong><\/em>, 82(2):366-379, 2016.
Extended abstract<\/strong><\/em><\/a>: Conflict packing yields linear vertex-kernels for k-FAST, k-dense RTI and a related problem.\u00a0<\/span>Mathematical Foundations of Computer Science \u2013 MFCS<\/em><\/strong>. Number 6907 of\u00a0<\/span>Lecture Notes in Computer Science\u00a0<\/em>, page 497-507, 2011.
See also\u00a0arXiv:1101.4491<\/a><\/strong><\/em>, 2011.<\/span><\/p>

[58]<\/strong> 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<\/a>.\u00a0ACM Transactions on Algorithms<\/strong><\/em>, 12(2):21, 2016.
Extended abstract<\/strong><\/em><\/a> in <\/span>International Colloquim on Automata, Languages, and Programming \u2013 ICALP<\/em><\/strong>. Number 7965 of\u00a0<\/span>Lecture Notes in Computer Science\u00a0<\/em>, page 613-624, 2013.
See also\u00a0arXiv:1207.0835<\/a><\/strong><\/em>, 2012.<\/span><\/p>

[57]<\/strong> E.J. Kim, C. Paul and G. Philip. A single-exponential FPT algorithm for the K4-minor cover problem<\/a>.\u00a0Journal of Computer and System Science<\/strong><\/em>, 81(1) :186-207, 2015.
Extended abstract<\/strong><\/em><\/a> in <\/span>Scandinavian Workshop On Algorithmic Theory \u2013 SWAT<\/em><\/strong>. Number 7357 of\u00a0<\/span>Lecture Notes in Computer Science\u00a0<\/em>, page 119-130, 2012.
See also\u00a0arXiv:1204.1417<\/a><\/strong><\/em>, 2012.<\/span><\/p>

[56]<\/strong> P. Golovach, P. Heggernes, P. van\u2019t Hof and C. Paul. Hadwiger number of graphs with small chordality<\/a>. SIAM Journal on\u00a0Discrete Applied Mathematics<\/strong><\/em>, 29(3) :1427-1451, 2015.
Extended abstract<\/strong><\/em><\/a> in <\/span>Workshop on Approximation and Online Algorithms \u2013 WAOA<\/em><\/strong>. Number 9499 of\u00a0<\/span>Lecture Notes in Computer Science\u00a0<\/em>, page 158-169, 2014.
See also\u00a0arXiv:1406.3812<\/a><\/strong><\/em>, 2014.<\/span><\/p>

[55]<\/strong> V. Garnero, C. Paul, I. Sau and D. Thilikos. Explicit linear kernels via dynamic programming<\/a>.\u00a0SIAM Journal on Discrete Mathematics<\/em>,<\/strong> 29(4) :1864-1894, 2015.
Extended abstract<\/strong><\/em><\/a> in <\/span>Symposium on Theoretical Aspect of Computer Science \u2013 STACS<\/em>.<\/strong> Number 25 of\u00a0<\/span>Leibnitz International Proceedings in Informatics<\/em>, page 312-324, 2014.
See also\u00a0arXiv:1312.6585<\/a><\/strong><\/em>, 2013.<\/span><\/p>

[54]<\/strong> G. Joret, C. Paul, I. Sau, S. Saurabh and S. Thomass\u00e9. Hitting and harvesting pumpkins<\/a>.\u00a0SIAM Journal on Discrete Mathematics<\/em><\/strong>, 28(3):1363-1390, 2014.
Extended abstract<\/strong><\/em><\/a> in <\/span>European Symposium on Algorithms \u2013 ESA<\/em><\/strong>. Number 6942 of\u00a0<\/span>Lecture Notes in Computer Science\u00a0<\/em>, page 394-407, 2011.
See also\u00a0arXiv:1105.2704<\/a><\/strong><\/em>, \u00a02011.<\/span><\/p>

[53]<\/strong> E. Gioan, C. Paul, M. Tedder and D.G. Corneil. Circle Graph Recognition in Time O(n+m).\\alpha(n+m)<\/a>.\u00a0Algorithmica<\/em><\/strong>, 69(4):759-788, 2014.
See also\u00a0arXiv:1104.3284<\/a><\/strong><\/em>, 2011.<\/p>

[52]<\/strong> E. Gioan, C. Paul, M. Tedder and D.G. Corneil. Practical and Efficient Split Decomposition via Graph-Labelled Trees<\/a>.\u00a0Algorithmica<\/em><\/strong>, 69(4):789-843, 2014.
See also\u00a0arXiv:1104.3283<\/a><\/strong><\/em>, \u00a02011.<\/p>

[51]<\/strong>\u00a0P. Heggernes, P. van\u2019t Hof, B. L\u00e9v\u00eaque and C. Paul. Contracting chordal graphs and bipartite graphs to paths and trees<\/a>.\u00a0Discrete Applied Mathematics<\/em><\/strong>, 164(2):444-449, 2014.
Extended abstract<\/strong><\/em><\/a> in<\/span> Latin-American<\/em> Algorithms, Graphs, and Optimization Symposium – LAGOS<\/em><\/strong>, \u00a0<\/span>Electronic Notes in Discrete Mathematics<\/em>, 37:87-92, 2011.<\/span><\/p>

[50]<\/strong> N. Bousquet, G. Mertzios, C. Paul, I. Sau and S. Thomass\u00e9.\u00a0Parameterized domination in circle graphs<\/a>.\u00a0Theory of Computing Systems<\/em><\/strong>, 54(1):45-72, 2014.
Extended abstract<\/strong><\/em><\/a> in <\/span>International Workshop on\u00a0Graph Theoretical Concepts in Computer Science \u2013 WG<\/em><\/strong>. Number 7551 of\u00a0<\/span>Lecture Notes in Computer Science\u00a0<\/em>, page 308-319, 2012.
See also\u00a0arXiv:1205.3728<\/a><\/strong><\/em>, 2012.<\/span><\/p>

[49]<\/strong> P. Heggernes P. van \u2018t Hof, B. L\u00e9v\u00eaque, D. Lokshtanov and C. Paul. Contracting graphs to paths and trees.<\/a>\u00a0Algorithmica<\/strong>, 68(1):109-132, 2014.
Extended abstract<\/strong><\/em><\/a> in\u00a0<\/span>International Symposium on Parameterized and exact Computation – IPEC<\/em><\/strong>. Number 7112 of\u00a0<\/span>Lecture Notes in Computer Science\u00a0<\/em>, page 55-66, 2011.
See also\u00a0arXiv:1104.3677<\/a><\/strong><\/em>, 2011.<\/span><\/p>

[48]<\/strong> S. Guillemot, F. Havet, C. Paul and A. Perez. On the (non-)existence of polynomial kernels for Pl-free edge modification problems.<\/a>\u00a0Algorithmica<\/em><\/strong>, 65(4):900-926, 2013.
Extended abstract<\/strong><\/em><\/a> in\u00a0<\/span>International Symposium on Parameterized and Exact Computation \u2013 IPEC<\/em><\/strong>. Number 6478 in Lecture Notes in Computer Science, pages 147-157, 2010.
See also\u00a0arXiv:1007.4011<\/a><\/strong><\/em>, 2010.<\/span><\/p>

[47]<\/strong> P. Heggernes, P. van \u2018t Hof, D. Lokshtanov and C. Paul. Obtaining a bipartite graph by contracting few edges<\/a>.\u00a0SIAM Journal on Discrete Mathematics<\/em><\/strong>, 27(4):2143-2156, 2013.
Extended abstract<\/strong><\/em><\/a> in <\/span>IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science \u2013 FSTTCS<\/em><\/strong>. Number 13 of\u00a0<\/span>Leibnitz International Proceedings in Informatics<\/em>, page 217-228, 2011.
See also\u00a0arXiv:1102.5441<\/a><\/strong><\/em>, 2011.<\/span><\/p>

[46]<\/strong> E. Gioan and C. Paul. Split decomposition and graph-labelled trees: characterizations and fully-dynamic algorithms for totally decomposable graphs<\/a>.\u00a0Discrete Applied Mathematics<\/em><\/strong>, 160(6):708-733, 2012.\u00a0
Extended abstract<\/a><\/strong><\/em>: Dynamic distance hereditary graphs using split decomposition. In\u00a0<\/span>International Symposium on Algorithms and Computation <\/em>\u2013\u00a0ISAAC<\/em><\/strong>, number 4835 in\u00a0<\/span>Lecture Notes in Computer Science<\/em>, pages 41-51, 2007.
See also\u00a0arXiv:0810.1823<\/a><\/strong><\/em>, 2008.<\/span><\/p>

[45]<\/strong> P. Gambette, V. Berry and C. Paul. Quartet and unrooted phylogenetic networks<\/a>.\u00a0Journal of Bioinformatics and Computational Biology<\/strong>,<\/em>\u00a010(4):23 pages, 2012.<\/p>

[44]<\/strong> \u00a0<\/b>S. Bessy, F. Fomin, S. Gaspers, C. Paul, A. Perez, S. Saurabh and S. Thomass\u00e9. Kernels for feedback arc set in tournaments<\/a>.\u00a0Journal of Computer and System Science<\/em><\/strong>, 77(6):1071-1078, 2011.
Extended abstract<\/strong><\/em><\/a> in <\/span>International Workshop On Combinatorial Algorithms \u2013 FSTTCS<\/em><\/strong>. Number 4 in\u00a0<\/span>Leibnitz International Proceedings in Informatics<\/em>, pages 37-47, 2009.
See also\u00a0arXiv:0907.2165<\/a><\/strong><\/em>, 2009.<\/span><\/p>

[43]\u00a0<\/strong>C. Paul, M. Habib. Proceedings of the 35th International Workshop on\u00a0<\/strong><\/em><\/a><\/span>Graph-Theoretic Concepts in Computer Science \u2013 WG\u201909<\/strong><\/em>. Revised Papers. Number 5911 of Lecture Notes in Computer Science<\/em>, 2010<\/p>

[42]<\/strong> P. Heggernes, D. Lokshtanov, J. Nederlof, C. Paul and J.A. Telle. Generalized graph clustering : recognizing (p,q)-cluster<\/a>. In International Workshop on\u00a0<\/strong><\/em>Graph Theoretical Concepts in Computer Science \u2013 WG<\/em><\/strong>. Number 6410 in\u00a0Lecture Notes in Computer Science<\/em>, pages 171-183, 2010.<\/p>

[41]<\/strong> M. Fellows, P. Giannopoulos, C. Knauer, C. Paul, F. Rosamond, S. Whitesides and \u00a0N. Yu. Milling a graph with turn costs : a parameterized complexity perspective<\/a>. In International Workshop on\u00a0<\/strong><\/em>Graph Theoretical\u00a0Concepts in Computer Science \u2013 WG<\/em><\/strong>. Number 6410 in\u00a0Lecture Notes in Computer Science<\/em>, pages 123-134, 2010.\u00a0
See also arXiv:0912.1050<\/a><\/strong><\/em><\/span>,<\/strong><\/em>\u00a02009.<\/span><\/p>

[40]<\/strong> C. Crespelle and C. Paul. Fully Dynamic Algorithm for Modular Decomposition and Recognition of Permutation Graphs<\/a>.\u00a0Algorithmica<\/em><\/strong>, 58(2):405-432, 2010.
Extended abstract<\/strong><\/em><\/a> in <\/span>International Workshop on Graph Theoretical Concepts in Computer Science- WG<\/em><\/strong>, number 3787 in\u00a0<\/span>Lecture Notes in Computer Science<\/em>, pages 38-48, 2005.<\/span><\/p>

[39]<\/strong> M. Habib and C. Paul. A survey on algorithmic aspects of modular decomposition<\/a>.\u00a0Computer Science Review<\/em>, 4(1):41-59, 2010.
See also\u00a0arXiv:0912.1457<\/a><\/strong><\/em>, 2009.<\/p>

[38]<\/strong> S. Bessy and C. Paul and A. Perez. Polynomial kernels for 3-leaf power graph modification problems<\/a>.\u00a0Discrete Applied Mathematics<\/em><\/strong>, 158(16):1732-1744, 2010.
Extended abstract<\/strong><\/em><\/a> in\u00a0<\/span>International Workshop On Combinatorial Algorithms \u2013 IWOCA<\/em><\/strong>. Number 5874 in\u00a0<\/span>Lecture Notes in Computer Science<\/em>, pages 72-80, 2009.
See also arXiv:0809.2858<\/a><\/strong><\/em>, 2009.<\/span><\/p>

[37]<\/strong> D.H. Huson,\u00a0R. Rupp<\/span>,\u00a0V. Berry<\/span>, P.\u00a0Gambette<\/span>, C. Paul. Computing galled networks from real data<\/a>. In\u00a0International Conference on Intelligent Systems for Molecular Biology – ISMB<\/em>,\u00a0Bioinformatics<\/strong>, 25(12),\u00a02009.<\/p>

[36]<\/strong> P. Gambette, V. Berry and C. Paul. The structure of level-k phylogenetic networks<\/a>. In\u00a0Annual Symposium on Combinatorial Pattern Matching \u2013 CPM<\/em><\/strong>. Number 5577 in\u00a0Lecture Notes in\u00a0Computer Science<\/em>, pages 289-300, 2009.\u00a0<\/p>

[35] <\/strong>S. Durocher, C. Paul. Kinetic maintenance of mobile k-centres on trees<\/a>.\u00a0Discrete Applied Mathematics<\/em><\/strong>, 157(7):1432-1446, 2009.
Extended abstract<\/strong><\/em><\/a> in <\/span>International Symposium on Algorithms and Computation<\/em>\u00a0\u2013\u00a0ISAAC<\/em><\/strong>, number 4825 in\u00a0<\/span>Lecture Notes in Computer Science<\/em>, pages 341-352, 2007.<\/span><\/p>

[34]<\/strong> S. Guillemot, F. Nicolas, V. Berry and C. Paul. On the approximability results for maximum agreement subtree and maximum compatible tree problems.<\/a>\u00a0Discrete Applied Mathematics<\/em><\/strong>, 157(7):1555-1570, 2009.
See also\u00a0arXiv:0802.2736<\/a><\/strong><\/em>, \u00a02008.<\/p>

[33]<\/strong>\u00a0C. Paul and J.A. Telle. Branchwidth of chordal graphs<\/a>.\u00a0Discrete Applied Mathematics<\/em><\/strong>, 157(12):2718-2725, 2009.<\/p>

[32]<\/strong> C. Paul and J.A. Telle. Edge maximal graphs of branchwidth k : the k-branches.<\/a>\u00a0Discrete Mathematics<\/em><\/strong>, 309(6):1467-1475, 2009.
Extended abstract:<\/strong><\/em><\/a> New Tools and Simpler Algorithms for Branchwidth. In\u00a0<\/span>European Symposium on Algorithms – ESA<\/em><\/strong>, number 3669 in\u00a0<\/span>Lecture Notes in Computer Science<\/em>, pages 379-390, 2005.<\/span><\/p>

[31]<\/strong> Y. Villanger, P. Heggerness, C. Paul and J.A. Telle. Interval completion is fixed parameter tractable<\/a>. In SIAM Journal on Computing<\/strong>, 38(5):2007-2020 , 2009.
Extended abstract<\/strong><\/em><\/a> in <\/span>ACM Symposium on Theory of Computing \u2013 STOC<\/em><\/strong>, pages 347-381, 2007.<\/span><\/p>

[30]<\/strong>\u00a0S. B\u00e9rard, A. Chateau, C. Chauve, C. Paul and E. Tannier. Computation of perfect DCJ rearrangement with linear and circular chromosomes<\/a>. In Journal of Computational Biology<\/strong>, 16(10) :1287-1309, 2009.
Extend abstract:<\/strong><\/em><\/a> Perfect DCJ rearrangement. In\u00a0<\/span>Annual RECOMB Satellite Workshop on Comparative Genomic \u2013 RECOMB-CG<\/strong><\/em>. Number 5267 in\u00a0<\/span>Lecture Notes in Bioinformatics<\/em>, pages 156-167, 2008.\u00a0<\/span><\/p>

[29]<\/strong> D. Bremner, J. Lenchner, G. Liotta, C. Paul, M. Pouget, S. Stolpner, S. Wismath. A note on \u03b1-drawable k-trees<\/a>. In\u00a0Canadian Conference on Computational Geometry \u2013 CCCG<\/em><\/strong>. 2008.<\/p>

[28]<\/strong> V. Berry, S. Guillemot, F. Nicolas and C. Paul. Linear time 3-approximation for MAST problem<\/a>.\u00a0ACM Transcations on Algorithms<\/em><\/strong>, 5(2):1-18, 2009.
Extended abstract:<\/strong><\/em><\/a> On the Approximation of Computing Evolutionary Trees.\u00a0<\/span>International Computing and Combinatorics Conference \u2013 COCOON<\/em><\/strong>, number 3595 in\u00a0<\/span>Lecture Notes in Computer Science<\/em>, pages 115-125, 2005.<\/span><\/p>

[27]\u00a0<\/b><\/strong>B.M. Bui Xuan and M. habib and C. Paul. Competitive Graph Searches<\/a>.\u00a0Theoretical Computer Science<\/em><\/strong>, 393(1-3):72-80, 2008.<\/p>

[26]<\/strong> S. B\u00e9rard, C. Chauve and C. Paul. A more efficient algorithm for perfect sorting by reversals<\/a>.\u00a0Information Processing Letters<\/em><\/strong>, 106:90-95, 2008.<\/p>

[25]<\/strong> C. Gavoille and C. Paul. Optimal Distance Labeling for Interval and Circular-Arc Graphs<\/a>.\u00a0SIAM Journal on Discrete Mathematics<\/em><\/strong>, 22(3) :1239-1258, 2008.
Extended abstract<\/strong><\/em><\/a> in <\/span>Annual European Symposium on Algorithms \u2013 ESA<\/em><\/strong>,\u00a0number 2832 in\u00a0<\/span>Lecture Notes in Computer Science<\/em>, pages 254-265, 2003.<\/span><\/p>

[24]<\/strong> A. Bretscher, D. Corneil, M. Habib and C. Paul. A simple linear time LexBFS cograph recognition algorithm<\/a>.\u00a0SIAM Journal on Discrete Mathematics<\/em><\/strong>, 22(4) :1277-1296, 2008.
Extended abstract<\/strong><\/em><\/a> in <\/span>International Workshop on\u00a0Graph-Theoretic Concepts in Computer Science \u2013 WG<\/em><\/strong>, number 2880 in\u00a0<\/span>Lecture Notes in Computer Science<\/em>, pages 119-130, 2003.\u00a0<\/span><\/p>

[23]<\/strong> M. Habib, D. Kelly, E. Lebhar and C. Paul. Can transitive orientation make sandwich problems easier ?<\/a>\u00a0Discrete Mathematics<\/em><\/strong>, 307:2030-2041, 2007.<\/p>

[22]<\/strong> A. Bergeron, S. B\u00e9rard, C. Chauve, and C. Paul. Perfect sorting by reversals is not Always Difficult<\/a>.\u00a0IEEE-ACM Transaction on Computational Biology and Bioinformatics<\/em><\/strong>, 4(1):4-16, 2007.
Extended abstract<\/strong><\/em><\/a> in<\/span>\u00a0International Workshop on Algorithm in Bioinformatics – WABI<\/strong><\/em>. Number 3692 in <\/span>Lecture Notes in Bioinformatics<\/em>, pages 228-238, 2005.<\/span><\/p>

[21]<\/strong> C. Paul, A. Proskurowski and J.A. Telle. Algorithmic generation of graphs of branchwidth <= k<\/a>. In\u00a0International Workshop on Graph Theoretical Concepts in Computer Science \u2013 WG<\/em><\/strong>, number 4271 in\u00a0Lecture Notes in Computer Science<\/em>, pages 206-216, 2006.<\/p>

[20]<\/strong> C. Crespelle and C. Paul. Fully-Dynamic Recognition Algorithm and Certificate for Directed Cographs.<\/a>\u00a0Discrete Applied Mathematics<\/em><\/strong>, 154(12):1722-1741, 2006.
Extended abstract<\/strong><\/em><\/a> in <\/span>International Workshop on Graph Theoretical Concepts in Computer Science \u2013 WG<\/em><\/strong>, number 3353 in\u00a0<\/span>Lecture Notes in Computer Science<\/em>, pages 93-104, 2004.<\/span><\/p>

[19]<\/strong> P. Fraigniaud and C. Gavoille and C. Paul. Eclecticism Shrinks Even Small Worlds<\/a>.\u00a0Journal of Distributed Computing<\/em><\/strong>, 18(4):279-291, 2006.
Extended abstract<\/strong><\/em><\/a> in <\/span>Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing \u2013 PODC<\/em><\/strong>,<\/em>\u00a0pages 168-178, 2004.<\/span><\/p>

[18]<\/strong> B.M. Bui Xuan, M. Habib and C. Paul. Revisiting Uno and Yagiura\u2019s Algorithm<\/a>. In\u00a0International Symposium on Algorithms and Computation- ISAAC<\/strong><\/em>, number 3827 in\u00a0Lecture Notes in Computer Science<\/em>, pages 146\u2013155, 2005.<\/p>

[17]<\/strong> C. Paul,\u00a0J.A. Telle.\u00a0<\/span>Edge-maximal graphs of branchwidth k<\/a>. In International Colloquium on Graph Theory – ICGT<\/strong><\/em>.\u00a0Electronic Notes in Discrete Mathematics,\u00a0<\/em>22: 363-368, 2005.<\/p>

[16]<\/strong> M. Habib and C. Paul. A Simple Linear Time Algorithm for Cograph Recongition<\/a>.\u00a0Discrete Applied Mathematics<\/em><\/strong>, 145(2):183-197, 2005.<\/p>

[15]<\/strong> M. Habib, C. Paul and M. Raffinot. Common connected Components of Interval Graphs<\/a>. In\u00a0Annual Combinatorial Pattern Matching Symposium \u2013 CPM<\/em><\/strong>, number 3109 in\u00a0Lecture Notes in Computer Science<\/em>, pages 347-358, 2004.<\/p>

[14]<\/strong> M. Habib, F. de Montgolfier and C. Paul. A simple linear-time modular decomposition algorithm<\/a>. In\u00a0\u00a0Scandinavian Workshop on Algorithm Theory – SWAT<\/strong><\/em>, number 3111 in\u00a0Lecture Notes in Computer Science<\/em>, pages 187-198, 2004.
There is a flaw in the algorithm presented in that paper.<\/span><\/p>

[13]<\/strong> M. Bouklit and D. Coudert and J.-F. Lalande and C. Paul and H. Rivano. Approximate multicommodity flow for WDM networks design<\/a>. In International Colloquium on Structural Information Complexity \u2013 SIROCCO<\/em>,<\/strong> number 17 of Proceedings in Informatics<\/em>, Carleton Scientific, pages 43-56, \u00a02003.<\/p>

[12]<\/strong> C. Gavoille and C. Paul. Distance labeling and split decomposition<\/a>.\u00a0Discrete Mathematics<\/em><\/strong>, 273(1-3):115-130, 2003.<\/p>

[11]<\/strong> M. Habib and E. Lebhar and C. Paul. A note on finding all homogeneous set sandwiches<\/a>.\u00a0Information Processing Letters<\/em><\/strong>, 87:147-151, 2003.<\/p>

[10]<\/strong> D. Corneil, F. Dragan, M. Habib, and C. Paul. Diameter determination on restricted graph families.<\/a>\u00a0Discrete Applied Mathematics<\/em><\/strong>, 113(2-3):143-166, 2001.
Extended abstract<\/strong><\/em><\/a> in <\/span>International Workshop Graph-Theoretic Concepts in Computer Science \u2013 WG<\/em><\/strong>, volume 1517 of\u00a0<\/span>Lecture Notes in Computer Science<\/em>, pages 192-202, 1998.<\/span><\/p>

[9]<\/strong> M. Habib, C. Paul, and L. Viennot. Linear time recognition of\u00a0P<\/em>4-indifference graphs<\/a>.\u00a0Discrete Mathematics and Theoretical Computer Science<\/em>,<\/strong> 4(2):173-178, 2001. Special issue: Graph Decomposition.<\/p>

[8]<\/strong> C. Gavoille<\/span>, C. Paul.\u00a0Split Decomposition and Distance Labelling: An Optimal Scheme For Distance Hereditary Graphs<\/a>. In Euroconference on Combinatorics, Graph Theory and Applications – EuroComb<\/strong><\/em>.\u00a0Electronic Notes in Discrete Mathematics<\/em>, 10:117-120, 2001.<\/p>

[7]<\/strong> G. Damiand, M. Habib, and C. Paul. A simple paradigm for graph recognition : application to cographs and distance hereditary graphs<\/a>.\u00a0Theoretical Computer Science<\/em><\/strong>, 263:99-111, 2001.\u00a0<\/p>

[6]<\/strong>\u00a0C. Gavoille, M. Katz, N. Katz, C. Paul, and D. Peleg. Approximate distance labeling scheme<\/a>. In Annual European Symposium on Algorithms – ESA<\/em><\/strong>, number 2161 in\u00a0Lecture Notes in Computer Science<\/em>, pages 476-487. 9th , 2001.<\/p>

[5]<\/strong> C. Gavoille<\/span>, C. Paul.\u00a0Approximate Distance Labeling Schemes<\/a>. In\u00a0International Conference on Graph Theory – ICGT<\/em><\/strong>. Electronic Notes in Discrete Mathematics<\/em>, 5: 134-137, 2000.<\/p>

[4]<\/strong> 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<\/a>.\u00a0Theoretical Computer Science<\/em><\/strong>, 234:59-84, 2000.<\/p>

[3]<\/strong> M. Habib, C. Paul, and L. Viennot. Partition refinement: an interested algorithmic tool kit.<\/a>\u00a0International Journal of Foundation of Computer Science<\/em><\/strong>, 10(2):147-170, 1999<\/p>

[2]\u00a0<\/strong>M. Habib, C. Paul, and L. Viennot. A synthesis on partition refinement: a useful routine for strings, graphs, boolean matrices and automata.<\/a> In International\u00a0Symposium on Theoretical Aspect of Computer Science \u2013 STACS<\/strong>,<\/em>\u00a0number 1373 in Lecture Notes in Computer Science<\/em>, pages 25-38, 1998.<\/p>

[1]\u00a0<\/strong>P. Galinier, M. Habib, and C. Paul. Chordal graphs and their clique graph<\/a>. In International Workshop on\u00a0Graph-Theoretic Concepts in Computer Science \u2013 WG<\/strong>,<\/em>\u00a0volume 1017 of\u00a0Lecture Notes in Computer Science<\/em>, pages 358-371, 1995.<\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<\/div>\n\t\t","protected":false},"excerpt":{"rendered":"

Publications (complete versions gathered with the extended abstract, if any) [92]\u00a0C. Paul,\u00a0E. Protopapas, D.M. Thilikos and S. Wiederrecht. Obstructions to Erd\u00f6s-Posa dualities for minors. In\u00a0IEEE…<\/p>\n","protected":false},"author":34,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"elementor_header_footer","meta":{"_crdt_document":"","_uag_custom_page_level_css":"","footnotes":""},"class_list":["post-2266","page","type-page","status-publish","hentry"],"uagb_featured_image_src":{"full":false,"thumbnail":false,"medium":false,"medium_large":false,"large":false,"1536x1536":false,"2048x2048":false},"uagb_author_info":{"display_name":"Christophe PAUL","author_link":"https:\/\/www.lirmm.fr\/christophe-paul\/author\/christophe-paul\/"},"uagb_comment_info":0,"uagb_excerpt":"Publications (complete versions gathered with the extended abstract, if any) [92]\u00a0C. Paul,\u00a0E. Protopapas, D.M. Thilikos and S. Wiederrecht. Obstructions to Erd\u00f6s-Posa dualities for minors. In\u00a0IEEE…","_links":{"self":[{"href":"https:\/\/www.lirmm.fr\/christophe-paul\/wp-json\/wp\/v2\/pages\/2266","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.lirmm.fr\/christophe-paul\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/www.lirmm.fr\/christophe-paul\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/www.lirmm.fr\/christophe-paul\/wp-json\/wp\/v2\/users\/34"}],"replies":[{"embeddable":true,"href":"https:\/\/www.lirmm.fr\/christophe-paul\/wp-json\/wp\/v2\/comments?post=2266"}],"version-history":[{"count":0,"href":"https:\/\/www.lirmm.fr\/christophe-paul\/wp-json\/wp\/v2\/pages\/2266\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.lirmm.fr\/christophe-paul\/wp-json\/wp\/v2\/media?parent=2266"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}