Accéder directement au contenu

Christophe Paul

126
Documents

Publications

The mixed search game against an agile and visible fugitive is monotone

Guillaume Mescoff , Christophe Paul , Dimitrios M. Thilikos
Discrete Mathematics, 2023, 346 (4), pp.113345. ⟨10.1016/j.disc.2023.113345⟩
Article dans une revue hal-04042958v1

A Linear Fixed Parameter Tractable Algorithm for Connected Pathwidth

Mamadou Moustapha Kanté , Christophe Paul , Dimitrios M. Thilikos
SIAM Journal on Discrete Mathematics, 2022, 36 (1), pp.411-435. ⟨10.1137/20M1369361⟩
Article dans une revue hal-03771145v1
Image document

A polynomial time algorithm to compute the connected treewidth of a series–parallel graph

Guillaume Mescoff , Christophe Paul , Dimitrios M. Thilikos
Discrete Applied Mathematics, 2022, 312, pp.72-85. ⟨10.1016/j.dam.2021.02.039⟩
Article dans une revue lirmm-03676663v1
Image document

Preface of STACS 2019 Special Issue

Rolf Niedermeier , Christophe Paul
Theory of Computing Systems, 2021, 65 (4), pp.635-637. ⟨10.1007/s00224-020-10026-5⟩
Article dans une revue lirmm-03438659v1
Image document

Connected search for a lazy robber

Isolde Adler , Christophe Paul , Dimitrios M. Thilikos
Journal of Graph Theory, 2021, 97 (4), pp.510-552. ⟨10.1002/jgt.22669⟩
Article dans une revue hal-03327307v1

On independent set in B1-EPG graphs

Stéphane Bessy , Marin Bougeret , Steven Chaplick , Daniel Gonçalves , Christophe Paul
Discrete Applied Mathematics, 2020, 278, pp.62-72. ⟨10.1016/j.dam.2019.10.019⟩
Article dans une revue lirmm-03027587v1
Image document

Edge degeneracy: Algorithmic and structural results

Stratis Limnios , Christophe Paul , Joanny Perret , Dimitrios M. Thilikos
Theoretical Computer Science, 2020, 839, pp.164-175. ⟨10.1016/j.tcs.2020.06.006⟩
Article dans une revue hal-03001062v1
Image document

Parameterized complexity of finding a spanning tree with minimum reload cost diameter

Julien Baste , Didem Gözüpek , Christophe Paul , Ignasi Sau , Mordechai Shalom
Networks, 2020, 75 (3), pp.259-277. ⟨10.1002/net.21923⟩
Article dans une revue lirmm-02989889v1

Strong immersion is a well-quasi-ordering for semicomplete digraphs

Florian Barbero , Christophe Paul , Michał Pilipczuk
Journal of Graph Theory, 2019, 90, pp.484-496. ⟨10.1002/jgt.22408⟩
Article dans une revue lirmm-01918986v1
Image document

Explicit Linear Kernels for Packing Problems

Valentin Garnero , Christophe Paul , Ignasi Sau , Dimitrios M. Thilikos
Algorithmica, 2019, 81 (4), pp.1615-1656. ⟨10.1007/s00453-018-0495-5⟩
Article dans une revue lirmm-02342736v1
Image document

An FPT 2-Approximation for Tree-Cut Decomposition

Eun Jung Kim , Sang-Il Oum , Christophe Paul , Ignasi Sau , Dimitrios M. Thilikos
Algorithmica, 2018, 80 (1), pp.116-135. ⟨10.1007/s00453-016-0245-5⟩
Article dans une revue hal-01690385v1

Exploring the Complexity of Layout Parameters in Tournaments and Semicomplete Digraphs

Florian Barbero , Christophe Paul , Michał Pilipczuk
ACM Transactions on Algorithms, 2018, 14 (3), pp.#38. ⟨10.1145/3196276⟩
Article dans une revue lirmm-01919000v1

Parameterized algorithms for min-max multiway cut and list digraph homomorphism

Eun Jung Kim , Christophe Paul , Ignasi Sau , Dimitrios M. Thilikos
Journal of Computer and System Sciences, 2017, 86, pp.191-206. ⟨10.1016/j.jcss.2017.01.003⟩
Article dans une revue lirmm-01487567v1

Parameterized complexity of the MINCCA problem on graphs of bounded decomposability

Didem Gözüpek , Sibel Özkan , Christophe Paul , Ignasi Sau , Mordechai Shalom
Theoretical Computer Science, 2017, 690, pp.91-103. ⟨10.1016/j.tcs.2017.06.013⟩
Article dans une revue lirmm-01630777v1
Image document

A polynomial-time algorithm for Outerplanar Diameter Improvement

Nathann Cohen , Daniel Gonçalves , Eun Jung Kim , Christophe Paul , Ignasi Sau
Journal of Computer and System Sciences, 2017, 89, pp.315 - 327. ⟨10.1016/j.jcss.2017.05.016⟩
Article dans une revue hal-01592242v1

An FPT Algorithm and a Polynomial Kernel for Linear Rankwidth-1 Vertex Deletion

Mamadou Moustapha Kanté , Eun Jung Kim , O-Joung Kwon , Christophe Paul
Algorithmica, 2017, 79 (1), pp.66-95. ⟨10.1007/s00453-016-0230-z⟩
Article dans une revue lirmm-01692676v1

Efficient FPT Algorithms for (Strict) Compatibility of Unrooted Phylogenetic Trees

Julien Baste , Christophe Paul , Ignasi Sau , Celine Scornavacca
Bulletin of Mathematical Biology, 2016, 79 (4), pp.920-938. ⟨10.1007/s11538-017-0260-y⟩
Article dans une revue lirmm-03113710v1
Image document

On the consistency of orthology relationships

Mark Jones , Christophe Paul , Celine Scornavacca
BMC Bioinformatics, 2016, 17 (S14), pp.11-14. ⟨10.1186/s12859-016-1267-3⟩
Article dans une revue lirmm-01481206v1

Linear Kernels and Single-Exponential Algorithms Via Protrusion Decompositions

Eun Jung Kim , Alexander Langer , Christophe Paul , Felix Reidl , Peter Rossmanith
ACM Transactions on Algorithms, 2016, 12 (2), pp.No. 21. ⟨10.1145/2797140⟩
Article dans une revue lirmm-01288472v1

Linear kernel for Rooted Triplet Inconsistency and other problems based on conflict packing technique

Christophe Paul , Anthony Perez , Stéphan Thomassé
Journal of Computer and System Sciences, 2016, 82 (2), ⟨10.1016/j.jcss.2015.08.002⟩
Article dans une revue hal-01367979v1

Hadwiger Number of Graphs with Small Chordality

Petr A. Golovach , Pinar Heggernes , Pim van 'T Hof , Christophe Paul
SIAM Journal on Discrete Mathematics, 2015, 29 (3), pp.1427-1451. ⟨10.1137/140975279⟩
Article dans une revue hal-01263856v1

Explicit Linear Kernels via Dynamic Programming

Valentin Garnero , Christophe Paul , Ignasi Sau , Dimitrios M. Thilikos
SIAM Journal on Discrete Mathematics, 2015, 29 (4), pp.1864-1894. ⟨10.1137/140968975⟩
Article dans une revue lirmm-01263857v1

A single-exponential FPT algorithm for the K4-minor cover problem

Eun Jung Kim , Christophe Paul , Geevarghese Philip
Journal of Computer and System Sciences, 2015, 81 (1), pp.186-207. ⟨10.1016/j.jcss.2014.05.001⟩
Article dans une revue hal-01496435v1

Hitting and harvesting pumpkins

Gwénaël Joret , Christophe Paul , Ignasi Sau , Saket Saurabh , Stéphan Thomassé
SIAM Journal on Discrete Mathematics, 2014, 28 (3), pp.1363-1390. ⟨10.1137/120883736⟩
Article dans une revue hal-01178192v1

Contracting chordal graphs and bipartite graphs to paths and trees

Pinar Heggernes , Pim van ’t Hof , Benjamin Lévêque , Christophe Paul
Discrete Applied Mathematics, 2014, LAGOS’11: Sixth Latin American Algorithms, Graphs, and Optimization Symposium, Bariloche, Argentina, 164, pp.444-449. ⟨10.1016/j.dam.2013.02.025⟩
Article dans une revue lirmm-01266352v1

Contracting Graphs to Paths and Trees

Pinar Heggernes , Pim Van ’t Hof , Benjamin Lévêque , Daniel Lokshtanov , Christophe Paul
Algorithmica, 2014, 68 (1), pp.109-132. ⟨10.1007/s00453-012-9670-2⟩
Article dans une revue lirmm-01076841v1

Practical and Efficient Circle Graph Recognition

Emeric Gioan , Christophe Paul , Marc Tedder , Derek Corneil
Algorithmica, 2014, 69 (4), pp.759-788. ⟨10.1007/s00453-013-9745-8⟩
Article dans une revue lirmm-00805194v1

Practical and Efficient Split Decomposition via Graph-Labelled Trees

Emeric Gioan , Christophe Paul , Marc Tedder , Derek Corneil
Algorithmica, 2014, 69 (4), pp.789-843. ⟨10.1007/s00453-013-9752-9⟩
Article dans une revue lirmm-00805193v1

Parameterized domination in circle graphs

Christophe Paul , Nicolas Bousquet , Daniel Gonçalves , George Mertzios , Ignasi Sau
Theory of Computing Systems, 2014, 54 (1), pp.45-72. ⟨10.1007/s00224-013-9478-8⟩
Article dans une revue hal-01178188v1

Obtaining a Bipartite Graph by Contracting Few Edges

Christophe Paul , Pinar Heggernes , Pim van 'T Hof , Daniel Lokshtanov
SIAM Journal on Discrete Mathematics, 2013, 27 (4), pp.2143-2156. ⟨10.1137/130907392⟩
Article dans une revue hal-01178184v1
Image document

On the (non-)existence of polynomial kernels for $P_l$-free edge modification problems

Sylvain Guillemot , Frédéric Havet , Christophe Paul , Anthony Perez
Algorithmica, 2013, 65 (4), pp.900-926. ⟨10.1007/s00453-012-9619-5⟩
Article dans une revue hal-00821612v1
Image document

Quartets and Unrooted Phylogenetic Networks

Philippe Gambette , Vincent Berry , Christophe Paul
Journal of Bioinformatics and Computational Biology, 2012, 10 (4), pp.1250004.1-1250004.23. ⟨10.1142/S0219720012500047⟩
Article dans une revue hal-00678046v1

Split Decomposition and Graph-Labelled Trees: Characterizations and Fully-Dynamic Algorithms for Totally Decomposable Graphs

Emeric Gioan , Christophe Paul
Discrete Applied Mathematics, 2012, 160 (6), pp.708-733. ⟨10.1016/j.dam.2011.05.007⟩
Article dans une revue lirmm-00783420v1
Image document

Kernels for feedback arc set in tournaments

Stéphane Bessy , Fedor V. Fomin , Serge Gaspers , Christophe Paul , Anthony Perez
Journal of Computer and System Sciences, 2011, 77 (6), pp.1071-1078. ⟨10.1016/j.jcss.2010.10.001⟩
Article dans une revue lirmm-00738221v1

A Survey on Algorithmic Aspects of Modular Decomposition

Michel Habib , Christophe Paul
Computer Science Review, 2010, 4 (1), pp.41-59. ⟨10.1016/j.cosrev.2010.01.001⟩
Article dans une revue lirmm-00533514v1

Polynomial Kernels for 3-Leaf Power Graph Modification Problems

Stéphane Bessy , Christophe Paul , Anthony Perez
Discrete Applied Mathematics, 2010, 158 (16), pp.1732-1744. ⟨10.1016/j.dam.2010.07.002⟩
Article dans une revue lirmm-00533517v1

Fully Dynamic Algorithm for Modular Decomposition and Recognition of Permutation Graphs

Christophe Crespelle , Christophe Paul
Algorithmica, 2010, 58 (2), pp.405-432. ⟨10.1007/s00453-008-9273-0⟩
Article dans une revue lirmm-00533516v1
Image document

Linear time 3-approximation for MAST problem

Vincent Berry , Sylvain Guillemot , François Nicolas , Christophe Paul
ACM Transactions on Algorithms, 2009, 5 (2), pp.1-18. ⟨10.1145/1497290.1497299⟩
Article dans une revue lirmm-00324073v1

Computation of Perfect DCJ Rearrangement Scenarios with Linear and Circular Chromosomes

Sèverine Bérard , Annie Chateau , Cedric Chauve , Christophe Paul , Eric Tannier
Journal of Computational Biology, 2009, 16 (10), pp.1287-1309. ⟨10.1089/cmb.2009.0088⟩
Article dans une revue lirmm-00432670v1
Image document

Computing Galled Networks from Real Data

Daniel Huson , Regula Rupp , Vincent Berry , Philippe Gambette , Christophe Paul
Bioinformatics, 2009, 25 (12), pp.i85-i93. ⟨10.1093/bioinformatics/btp217⟩
Article dans une revue lirmm-00368545v2

Kinetic Maintenance of Mobile k-Centres in Trees

Christophe Paul , Stéphane Durocher
Discrete Applied Mathematics, 2009, 157 (7), pp.1432-1446. ⟨10.1007/978-3-540-77120-3_31⟩
Article dans une revue lirmm-00371207v1

Edge Maximal Graphs of Branchwidth k: The k-Branches

Christophe Paul , Jan Arne Telle
Discrete Mathematics, 2009, 309 (6), pp.1467-1475. ⟨10.1016/j.disc.2008.02.030⟩
Article dans une revue lirmm-00371208v1

Branchwidth of Chordal Graphs

Christophe Paul , Jan Arne Telle
Discrete Applied Mathematics, 2009, 157 (12), pp.2718-2725. ⟨10.1016/j.dam.2008.08.006⟩
Article dans une revue lirmm-00394553v1

Interval completion is Fixed Parameter Tractable

Yngve Villanger , Pinar Heggernes , Christophe Paul , Jan Arne Telle
SIAM Journal on Computing, 2009, 38 (5), pp.2007-2020. ⟨10.1137/070710913⟩
Article dans une revue lirmm-00371876v1

On the Approximability Results for Maximum Agreement Subtree and Maximum Compatible Tree Problems

François Nicolas , Sylvain Guillemot , Vincent Berry , Christophe Paul
Discrete Applied Mathematics, 2009, 157 (7), pp.1555-1570. ⟨10.1016/j.dam.2008.06.007⟩
Article dans une revue lirmm-00371209v1

A Simple Linear Time LexBFS Cograph Recongition Algorithm

Anna Bretscher , Derek Corneil , Michel Habib , Christophe Paul
SIAM Journal on Discrete Mathematics, 2008, 22 (4), pp.1277-1296. ⟨10.1137/060664690⟩
Article dans une revue lirmm-00324572v1

Optimal Distance Labeling for Interval Graphs and Related Graphs Families

Cyril Gavoille , Christophe Paul
SIAM Journal on Discrete Mathematics, 2008, 22 (3), pp.1239-1258. ⟨10.1137/050635006⟩
Article dans une revue hal-00366618v1

Competitive Graph Searches

Binh-Minh Bui-Xuan , Michel Habib , Christophe Paul
Theoretical Computer Science, 2008, 393 (1-3), pp.72-80. ⟨10.1016/j.tcs.2007.10.048⟩
Article dans une revue lirmm-00324565v1

A More Efficient Algorithm for Perfect Sorting by Reversals

Sèverine Bérard , Cedric Chauve , Christophe Paul
Information Processing Letters, 2008, 106, pp.90-95. ⟨10.1016/j.ipl.2007.10.012⟩
Article dans une revue lirmm-00274051v1

Can Transitive Orientation Make Sandwich Problems Easier?

Michel Habib , David Kelly , Emmanuelle Lebhar , Christophe Paul
Discrete Mathematics, 2007, 307 (16), pp.2030-2041. ⟨10.1016/j.disc.2005.12.048⟩
Article dans une revue lirmm-00189518v1

Perfect Sorting by Reversals is not Always Difficult

Christophe Paul , Sèverine Bérard , Anne Bergeron , Cedric Chauve
IEEE/ACM Transactions on Computational Biology and Bioinformatics, 2007, 4 (1), pp.12. ⟨10.1109/TCBB.2007.1011⟩
Article dans une revue lirmm-00111979v1

Fully-Dynamic Recognition Algorithm and Certificate for Directed Cographs

Christophe Crespelle , Christophe Paul
Discrete Applied Mathematics, 2006, 154, pp.1722-1741. ⟨10.1016/j.dam.2006.03.005⟩
Article dans une revue lirmm-00102849v1

Eclectism Shrinks Even Small Worlds

Pierre Fraigniaud , Cyril Gavoille , Christophe Paul
Distributed Computing, 2006, 18 (4), pp.279-291. ⟨10.1007/s00446-005-0137-4⟩
Article dans une revue lirmm-00102848v1

Fully Dynamic Recognition Algorithm and Certificate for Directed Cographs

Christophe Crespelle , Christophe Paul
Discrete Applied Mathematics, 2006, 154 (12), pp.1722-1741. ⟨10.1016/j.dam.2006.03.005⟩
Article dans une revue hal-01424432v1
Image document

A Simple Linear Time Algorithm for Cograph Recognition

Michel Habib , Christophe Paul
Discrete Applied Mathematics, 2005, 145 (2), pp.183-197. ⟨10.1016/j.dam.2004.01.011⟩
Article dans une revue lirmm-00105298v1

Edge-Maximal Graphs of Branchwidth $k$

Christophe Paul , Jan Arne Telle
Electronic Notes in Discrete Mathematics, 2005, 22 (7th International Colloquium on Graph Theory), pp.363-368. ⟨10.1016/j.endm.2005.06.075⟩
Article dans une revue lirmm-00106051v1

Distance Labeling Scheme and Split Decomposition

Cyril Gavoille , Christophe Paul
Discrete Mathematics, 2003, 273, pp.115-130
Article dans une revue hal-00307384v1

A Note on Finding All Homogeneous Set Sandwiches

Michel Habib , Emmanuelle Lebhar , Christophe Paul
Information Processing Letters, 2003, 87, pp. 147-151. ⟨10.1016/S0020-0190(03)00265-5⟩
Article dans une revue lirmm-00269575v1

Distance Labeling and Split Decomposition

Cyril Gavoille , Christophe Paul
Discrete Mathematics, 2003, 273 (1-3), pp.147-151. ⟨10.1016/S0012-365X(03)00232-2⟩
Article dans une revue lirmm-00269634v1
Image document

A Simple Paradigm for Graph Recognition : Application to Cographs and Distance Hereditary Graphs

Guillaume Damiand , Michel Habib , Christophe Paul
Theoretical Computer Science, 2001, 263 (1-2), pp.99-111. ⟨10.1016/S0304-3975(00)00234-6⟩
Article dans une revue lirmm-00090372v1
Image document

Linear time recognition of P4-indifference graphs

Michel Habib , Christophe Paul , Laurent Viennot
Discrete Mathematics and Theoretical Computer Science, 2001, Vol. 4 no. 2 (2), pp.173-178. ⟨10.46298/dmtcs.269⟩
Article dans une revue inria-00471619v1
Image document

Diameter Determination on Restricted Graph Families

Derek G. Corneil , Feodor F. Dragan , Michel Habib , Christophe Paul
Discrete Applied Mathematics, 2001, 113 (2-3), pp.146-166. ⟨10.1016/S0166-218X(00)00281-X⟩
Article dans une revue lirmm-00090363v1
Image document

Lex-BFS a partition refining technique, application to transitive orientation and consecutive 1's testing

Michel Habib , Ross Mac Connell , Christophe Paul , Laurent Viennot
Theoretical Computer Science, 2000, 234, ⟨10.1016/S0304-3975(97)00241-7⟩
Article dans une revue inria-00471613v1

On Dasgupta’s Hierarchical Clustering Objective and Its Relation to Other Graph Parameters

Svein Høgemo , Benjamin Bergougnoux , Ulrik Brandes , Christophe Paul , Jan Arne Telle
FCT 2021 - 23rd International Symposium on Fundamentals of Computation Theory, Sep 2021, Athens, Greece. pp.287-300, ⟨10.1007/978-3-030-86593-1_20⟩
Communication dans un congrès lirmm-03867040v1
Image document

Hierarchical Clusterings of Unweighted Graphs

Svein Hogemo , Christophe Paul , Jan Arne Telle
MFCS 2020 - 45th International Symposium on Mathematical Foundations of Computer Science, Aug 2020, Prague, Czech Republic. pp.47:1-47:13, ⟨10.4230/LIPIcs.MFCS.2020.47⟩
Communication dans un congrès lirmm-03027532v1
Image document

A linear fixed parameter tractable algorithm for connected pathwidth

Mamadou Moustapha Kanté , Christophe Paul , Dimitrios M. Thilikos
ESA 2020 - 28th Annual European Symposium on Algorithms, Sep 2020, Milan, Italy. pp.64:1-64:16, ⟨10.4230/LIPIcs.ESA.2020.64⟩
Communication dans un congrès hal-03002761v1
Image document

Connected Search for a Lazy Robber

Isolde Adler , Christophe Paul , Dimitrios M. Thilikos
FSTTCS 2019 - 39th IARCS Conference on Foundations of Software Technology and Theoretical Computer Science, Dec 2019, Bombay, India. pp.7:1--7:14, ⟨10.4230/LIPIcs.FSTTCS.2019.7⟩
Communication dans un congrès hal-03003243v1
Image document

Connected tree-width and connected cops and robber game

Christophe Paul
CAALM 2019 - Complexity, Algorithms, Automata and Logic Meet, Jan 2019, Chennai, India
Communication dans un congrès lirmm-02079017v1

A polynomial Turing kernel to compute the cut-width of semi-complete digraph

Christophe Paul
FILOFOCS 2018 - 7th French-Israeli Workshop on Foundations of Computer Science, Oct 2018, Paris, France
Communication dans un congrès lirmm-02078882v1
Image document

Exploring the Complexity of Layout Parameters in Tournaments and Semi-Complete Digraphs

Florian Barbero , Christophe Paul , Michał Pilipczuk
44th International Colloquium on Automata, Languages, and Programming (ICALP 2017), Jul 2017, Warsaw, Poland. pp.70:1--70:13, ⟨10.4230/LIPIcs.ICALP.2017.70⟩
Communication dans un congrès lirmm-02021567v1
Image document

Parameterized Complexity of the MINCCA Problem on Graphs of Bounded Decomposability

Didem Gözüpek , Sibel Özkan , Christophe Paul , Ignasi Sau , Mordeshai Shalom
WG 2016 - 42nd International Workshop on Graph-Theoretic Concepts in Computer Science, Jun 2016, Istanbul, Turkey. pp.195-206, ⟨10.1007/978-3-662-53536-3_17⟩
Communication dans un congrès lirmm-01481360v1
Image document

Efficient FPT Algorithms for (Strict) Compatibility of Unrooted Phylogenetic Trees

Julien Baste , Christophe Paul , Ignasi Sau , Celine Scornavacca
AAIM: Algorithmic Aspects in Information and Management, Jul 2016, Bergamo, Italy. pp.53-64, ⟨10.1007/978-3-319-41168-2_5⟩
Communication dans un congrès lirmm-01481368v1
Image document

Parameterized Algorithms for Min-Max Multiway Cut and List Digraph Homomorphism

Eun Jung Kim , Christophe Paul , Ignasi Sau , Dimitrios M. Thilikos
IPEC 2015 - 10th International Symposium on Parameterized and Exact Computation, Sep 2015, Patras, Greece. pp.78-89, ⟨10.4230/LIPIcs.IPEC.2015.78⟩
Communication dans un congrès lirmm-01263999v1
Image document

An FPT Algorithm and a Polynomial Kernel for Linear Rankwidth-1 Vertex Deletion

Mamadou Moustapha Kanté , Eun Jung Kim , O-Joung Kwon , Christophe Paul
IPEC 2015 - 10th International Symposium on Parameterized and Exact Computation, Sep 2015, Patras, Greece. pp.138-150, ⟨10.4230/LIPIcs.IPEC.2015.138⟩
Communication dans un congrès lirmm-01264011v1

An FPT 2-Approximation for Tree-cut Decomposition

Eun Jung Kim , Sang-Il Oum , Christophe Paul , Ignasi Sau , Dimitrios M. Thilikos
WAOA 2015 - 13th International Workshop on Approximation and Online Algorithms, Sep 2015, Patras, Greece. pp.35-46, ⟨10.1007/978-3-319-28684-6_4⟩
Communication dans un congrès lirmm-01264015v1

Introduction to parameterized complexity and some algorithmic consequences of the graph minor theory

Christophe Paul
Workshop on Graph Theory and its Applications, 2015, Istanbul, Turkey
Communication dans un congrès lirmm-02078876v1

On Independent Set on B1-EPG Graphs

Marin Bougeret , Stéphane Bessy , Daniel Gonçalves , Christophe Paul
WAOA 2015 - 13th International Workshop on Approximation and Online Algorithms, Sep 2015, Patras, Greece. pp.158-169, ⟨10.1007/978-3-319-28684-6_14⟩
Communication dans un congrès lirmm-01264022v1

A Polynomial-Time Algorithm for Outerplanar Diameter Improvement

Nathann Cohen , Daniel Gonçalves , Eun Jung Kim , Christophe Paul , Ignasi Sau
CSR: Computer Science in Russia, Jul 2015, Listvyanka, Russia. pp.123-142, ⟨10.1007/978-3-319-20297-6_9⟩
Communication dans un congrès hal-01178222v1
Image document

Hadwiger Number of Graphs with Small Chordality

Petr A. Golovach , Pinar Heggernes , Pim van 'T Hof , Christophe Paul
WG 2014 - 40th International Workshop on Graph-Theoretic Concepts in Computer Science, Jun 2014, Nouan-le-Fuzelier, France. pp.201-213, ⟨10.1007/978-3-319-12340-0_17⟩
Communication dans un congrès hal-01178217v1

Recognition of dynamic circle graphs

Christophe Crespelle , Emeric Gioan , Christophe Paul
ICGT: International Colloquium on Graph Theory and combinatorics, Jun 2014, Grenoble, France
Communication dans un congrès hal-01178215v1
Image document

Explicit linear kernels via dynamic programming

Valentin Garnero , Christophe Paul , Ignasi Sau , Dimitrios M. Thilikos
STACS: Symposium on Theoretical Aspects of Computer Science, Mar 2014, Lyon, France. pp.312-324, ⟨10.4230/LIPIcs.STACS.2014.312⟩
Communication dans un congrès hal-01084007v1

Complexité et algorithmes paramétrés

Christophe Paul
Ecole Jeunes Chercheurs en Informatique Mathématique, 2013, Perpignan, France
Communication dans un congrès hal-01178227v1

Linear Kernels and Single-exponential Algorithms via Protrusion Decompositions

Eun Jung Kim , Alexander Langer , Christophe Paul , Felix Reidl , Peter Rossmanith
ICALP: International Colloquium on Automata, Languages and Programming, Jul 2013, Riga, Latvia. pp.613-624, ⟨10.1007/978-3-642-39206-1_52⟩
Communication dans un congrès lirmm-00829999v1

Algorithmics of Modular Decomposition

Christophe Paul
Algorithms and Permutations, Feb 2012, Paris, France
Communication dans un congrès lirmm-00805415v1

Parameterized K_4-Cover in Single Exponential Time

Eunjung Kim , Christophe Paul , Geevarghese Philip
SWAT: Scandinavian Workshop on Algorithmic Theory, Jul 2012, Helsinki, Sweden. pp.199-130
Communication dans un congrès lirmm-00805191v1
Image document

Parameterized domination in circle graphs

Nicolas Bousquet , Daniel Gonçalves , George B. Mertzios , Christophe Paul , Ignasi Sau
WG 2012 - 38th International Workshop on Graph Theoretic-Concepts in Computer Science, Jun 2012, Jerusalem, Israel. pp.45-72, ⟨10.1007/s00224-013-9478-8⟩
Communication dans un congrès lirmm-00738534v1
Image document

Obtaining a Bipartite Graph by Contracting Few Edges

Pinar Heggerness , Pim Van'T Hof , Daniel Lokshtanov , Christophe Paul
IARCS 31st Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011), Dec 2011, Mumbai, India. pp.217-228, ⟨10.4230/LIPIcs.FSTTCS.2011.217⟩
Communication dans un congrès lirmm-00805189v1

Conflict Packing Yield Linear Vertex-Kernels for k- Fast, $k-Dense$ RTI and a Related Problem

Christophe Paul , Anthony Perez , Stéphan Thomassé
36th International Symposium on Mathematical Foundations of Computer Science (MFCS 2011), Aug 2011, Warsaw, Poland. pp.497-507, ⟨10.1007/978-3-642-22993-0_45⟩
Communication dans un congrès lirmm-00642335v1

Hitting and Harvesting Pumpkins

Gwénaël Joret , Christophe Paul , Ignasi Sau , Saket Saurabh , Stéphan Thomassé
ESA 2011 - 19th Annual European Symposium on Algorithms, Sep 2011, Saarbrücken, Germany. pp.394-407, ⟨10.1007/978-3-642-23719-5_34⟩
Communication dans un congrès lirmm-00642341v1

Contracting Chordal Graphs and Bipartite Graphs to Paths and Trees

Pinar Heggernes , Pim van 'T Hof , Benjamin Lévêque , Christophe Paul
LAGOS: Latin-American Algorithms, Graphs and Optimization Symposium, Mar 2011, Bariloche, Argentina. pp.87-92
Communication dans un congrès lirmm-00620732v1

Contracting Graphs to Paths and Trees

Pinar Heggerness , Pim Van'T Hof , Benjamin Lévêque , Daniel Lokshtanov , Christophe Paul
IPEC 2011 - 6th International Symposium on Parameterized and Exact Computation, Sep 2011, Saarbrücken, Germany. pp.55-66, ⟨10.1007/978-3-642-28050-4_5⟩
Communication dans un congrès lirmm-00805183v1

Generalized Graph Clustering: Recognizing (p,q)-Cluster

Pinar Heggerness , Daniel Lokshtanov , Jesper Nederlof , Christophe Paul , Jan Arne Telle
WG'10: International Workshop on Graph Theoretic Concepts in Computer Science, Jun 2010, Zarós, Greece. pp.12
Communication dans un congrès lirmm-00533520v1

On the (Non-)Existence of Polynomial Kernels for Pl -Free Edge Modification Problems

Sylvain Guillemot , Christophe Paul , Anthony Perez
IPEC 2010 - 5th International Symposium on Parameterized and Exact Computation, Dec 2010, Chennai, India. pp.147-157, ⟨10.1007/978-3-642-17493-3_15⟩
Communication dans un congrès lirmm-00533519v1
Image document

Milling a Graph with Turn Costs: a Parameterized Complexity Perspective

Micheal Fellows , Panos Giannopoulos , Christian Knauer , Christophe Paul , Fran Rosamond
WG 2010 - 36th International Workshop on Graph-Theoretic Concepts in Computer Science, Jun 2010, Zarós, Greece. pp.123-134, ⟨10.1007/978-3-642-16926-7_13⟩
Communication dans un congrès lirmm-00533521v1
Image document

The Structure of Level-k Phylogenetic Networks

Philippe Gambette , Vincent Berry , Christophe Paul
CPM: Combinatorial Pattern Matching, Jun 2009, Lille, France. pp.289-300, ⟨10.1007/978-3-642-02441-2_26⟩
Communication dans un congrès lirmm-00371485v1
Image document

Kernels for Feedback Arc Set In Tournaments

Stéphane Bessy , Fedor V. Fomin , Serge Gaspers , Christophe Paul , Anthony Perez
IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, Dec 2009, IIT Kanpur, India. pp.37-47, ⟨10.4230/LIPIcs.FSTTCS.2009.2305⟩
Communication dans un congrès lirmm-00432668v1

Polynomial Kernels for 3-Leaf Power Graph Modification Problems

Stéphane Bessy , Anthony Perez , Christophe Paul
IWOCA'09: International Workshop on Combinatorial Algorithms, pp.72-82
Communication dans un congrès lirmm-00432664v1
Image document

A Note on α-Drawable k-Trees

David Bremner , Jonathan Lenchner , Giuseppe Liotta , Christophe Paul , Marc Pouget
CCCG 2008 - 20th Annual Canadian Conference on Computational Geometry, Aug 2008, Montréal, Québec, Canada. pp.23-26
Communication dans un congrès lirmm-00324589v1
Image document

Perfect DCJ rearrangement

Annie Chateau , Cedric Chauve , Sèverine Bérard , Eric Tannier , Christophe Paul
RECOMB-CG: Comparative Genomics, Oct 2008, Paris, France. pp.158-169, ⟨10.1007/978-3-540-87989-3_12⟩
Communication dans un congrès lirmm-00327258v1

Simple, Linear-Time Modular Decomposition

Marc Tedder , Derek Corneil , Michel Habib , Christophe Paul
ICALP: International Colloquium on Automata, Languages and Programming, Jul 2008, Reykjavik, Iceland. pp.634-645
Communication dans un congrès lirmm-00324557v1

Kinetic Maintenance of Mobile k-Centre in Trees

Stéphane Durocher , Christophe Paul
ISAAC'07: 18th International Symposium on Algorithms and Computation, 2007, Sendei, Japan. pp.341-352
Communication dans un congrès lirmm-00189505v1

Interval Completion with Few Edges

Pinar Heggerness , Christophe Paul , Jan Arne Telle , Yngve Villanger
STOC'07: 39th ACM Symposium on Theory of Computing, Jun 2007, San Diego, CA, United States. pp.374-381, ⟨10.1145/1250790.1250847⟩
Communication dans un congrès lirmm-00189511v1

Dynamic Distance Hereditary Graphs Using Split Decomposition

Emeric Gioan , Christophe Paul
ISAAC'07: 18th International Symposium on Algorithms and Computation, 2007, Sendei, Japan. pp.41-51
Communication dans un congrès lirmm-00189506v1
Image document

Algorithmic Generation of Graphs of Branch-width ≤ k

Christophe Paul , Andrzej Proskurowski , Jan Arne Telle
WG 2006 - 32nd International Workshop on Graph-Theoretic Concepts in Computer Science, Jun 2006, Bergen, Norway. pp.206-216, ⟨10.1007/11917496_19⟩
Communication dans un congrès lirmm-00324551v1
Image document

Perfect Sorting by Reversal is not Always Difficult

Sèverine Bérard , Anne Bergeron , Cédric Chauve , Christophe Paul
WABI: Workshop on Algorithms in Bioinformatics, Oct 2005, Mallorca, Spain. pp.228-238, ⟨10.1007/11557067_19⟩
Communication dans un congrès lirmm-00106465v1

Fully Dynamic Algorithm for Modular Decomposition and Recognition of Permutation Graphs

Christophe Crespelle , Christophe Paul
WG'05: 31st International Workshop on Graph Theoretical Concepts in Computer Science, Jun 2005, Metz, France. pp.38-48, ⟨10.1007/11604686_4⟩
Communication dans un congrès lirmm-00106039v1
Image document

On the Approximation of Computing Evolutionary Trees

Vincent Berry , Sylvain Guillemot , Nicolas François , Christophe Paul
COCOON: Computing and Combinatorics Conference, Aug 2005, Kunming, China. pp.115-125, ⟨10.1007/11533719_14⟩
Communication dans un congrès lirmm-00106451v1

Revisiting Uno and Yagiura's Algorithms

Binh-Minh Bui-Xuan , Michel Habib , Christophe Paul
ISAAC'05: 16th Annual Symposium on Algorithms and Computation, 2005
Communication dans un congrès lirmm-00106037v1
Image document

New Tools and Simpler Algorithms for Branchwidth

Christophe Paul , Jan Arne Telle
ESA 2003 - 13rd Annual European Symposium on Algorithms, Oct 2005, Palma de Mallorca, Spain. pp.379-390, ⟨10.1007/11561071_35⟩
Communication dans un congrès lirmm-00106466v1

Eclecticism Shrinks Even Small Worlds

Pierre Fraigniaud , Cyril Gavoille , Christophe Paul
$23^{rd}$ Annual ACM Symposium on Principles of Distributed Computing (PODC), 2004, Canada. pp.169-178
Communication dans un congrès hal-00307394v1
Image document

Fully-Dynamic Recognition Algorithm and Certificate for Directed Cographs

Christophe Crespelle , Christophe Paul
WG 2004 - 30th International Workshop on Graph-Theoretic Concepts in Computer Science, Jun 2004, Bad Honnef, Germany. pp.93-104
Communication dans un congrès lirmm-00108770v1
Image document

A Simple Linear-Time Modular Decomposition Algorithm for Graphs, Using Order Extension

Michel Habib , Fabien de Montgolfier , Christophe Paul
SWAT 2004 - 9th Scandinavian Workshop on Algorithm Theory, Jul 2004, Humlebaek, Denmark. pp.187-198, ⟨10.1007/978-3-540-27810-8_17⟩
Communication dans un congrès hal-00159601v1
Image document

Maximal Common Connected Sets of Interval Graphs

Michel Habib , Christophe Paul , Mathieu Raffinot
CPM: Combinatorial Pattern Matching, 2004, Istanbul, Turkey. pp.359-372, ⟨10.1007/978-3-540-27801-6_27⟩
Communication dans un congrès lirmm-00108787v1

Eclectisme dans les petits mondes

Pierre Fraigniaud , Cyril Gavoille , Christophe Paul
AlgoTel: Aspects Algorithmiques des Télécommunications, May 2004, Lyon, France. pp.270-284
Communication dans un congrès hal-00307396v1
Image document

Approximate Multicommodity Flow for WDM Networks Design

Mohamed Bouklit , David Coudert , Jean-François Lalande , Christophe Paul , Hervé Rivano
SIROCCO: Structural Information and Communication Complexity, Jun 2003, Umeä, Sweden. pp.43-56
Communication dans un congrès lirmm-00269524v1
Image document

A Linear-Time Algorithm for Recognition of Catval Graphs

Michel Habib , Christophe Paul , Jan Arne Telle
EuroComb: European Conference on Combinatorics, Graph Theory and Applications, 2003, Prague, Czech Republic
Communication dans un congrès lirmm-00269443v1

A Simple Linear Time LexBFS Cograph Recognition Algorithm

Anna Bretscher , Derek Corneil , Michel Habib , Christophe Paul
WG 2003 - 29th International Workshop on Graph-Theoretic Concepts in Computer Science, Jun 2003, Elspeet, Netherlands. pp.119-130, ⟨10.1007/978-3-540-39890-5_11⟩
Communication dans un congrès lirmm-00269525v1

Optimal Distance Labeling Schemes for Interval and Circular-arc Graphs

Cyril Gavoille , Christophe Paul
$11^{th}$ Annual European Symposium on Algorithms (ESA), 2003, United States. pp.254-265
Communication dans un congrès hal-00307388v1

Optimal Distance Labeling for Interval and Circular-Arc Graphs

Cyril Gavoille , Christophe Paul
ESA 2003 - 11th Annual European Symposium on Algorithms, Sep 2003, Budapest, Hungary. pp.254-265, ⟨10.1007/978-3-540-39658-1_25⟩
Communication dans un congrès lirmm-00269576v1

On Poset Sandwich Problems

Michel Habib , David Kelly , Emmanuelle Lebhar , Christophe Paul
EuroComb: European Conference on Combinatorics, Graph Theory and Applications, 2003, Prague, Czech Republic
Communication dans un congrès lirmm-00269577v1
Image document

Partition refinement and graph decomposition

Michel Habib , Christophe Paul , Laurent Viennot
Symposium on Discrete Algorithms (SODA), 1999, Baltimore, United States. pp.1-2
Communication dans un congrès inria-00471612v1
Image document

A Synthesis on Partition Refinement: a Usefull Routine for Strings, Graphs, Boolean Matrices and Automata

Michel Habib , Christophe Paul , Laurent Viennot
STACS: Symposium on Theoretical Aspects of Computer Science, Feb 1998, Paris, France. pp.25-38, ⟨10.1007/BFb0028546⟩
Communication dans un congrès inria-00471611v1

Split decomposition, circle graphs and related graph families

Christophe Paul
Ming-Yang Kao. Encyclopedia of Algorithms, 2051-2056, Springer, 2015, 978-1-4939-2863-7. ⟨10.1007/978-1-4939-2864-4_686⟩
Chapitre d'ouvrage hal-01178198v1

Complexité et algorithmes paramétrés

Christophe Paul
Philippe Langlois. Informatique mathématique, une photographie en 2013, Presse universitaires de Perpignan, 2013
Chapitre d'ouvrage hal-01178225v1
Image document

Aspects algorithmiques de la décomposition modulaire

Christophe Paul
Mathématiques [math]. Université Montpellier II - Sciences et Techniques du Languedoc, 2006
HDR tel-00112390v1