Christophe Paul

According to our database1, Christophe Paul authored at least 94 papers between 1995 and 2019.

Collaborative distances:



In proceedings 
PhD thesis 





Strong immersion is a well-quasi-ordering for semicomplete digraphs.
Journal of Graph Theory, 2019

Explicit Linear Kernels for Packing Problems.
Algorithmica, 2019

Connected Search for a Lazy Robber.
Proceedings of the 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2019

Exploring the Complexity of Layout Parameters in Tournaments and Semicomplete Digraphs.
ACM Trans. Algorithms, 2018

Preface: Seventh Workshop on Graph Classes, Optimization, and Width Parameters, Aussois, France, October 2015.
Discret. Appl. Math., 2018

An FPT 2-Approximation for Tree-Cut Decomposition.
Algorithmica, 2018

Parameterized complexity of the MINCCA problem on graphs of bounded decomposability.
Theor. Comput. Sci., 2017

Parameterized algorithms for min-max multiway cut and list digraph homomorphism.
J. Comput. Syst. Sci., 2017

A polynomial-time algorithm for Outerplanar Diameter Improvement.
J. Comput. Syst. Sci., 2017

Strong immersion is a well-quasi-ordering for semi-complete digraphs.
CoRR, 2017

An FPT Algorithm and a Polynomial Kernel for Linear Rankwidth-1 Vertex Deletion.
Algorithmica, 2017

Parameterized Complexity of Finding a Spanning Tree with Minimum Reload Cost Diameter.
Proceedings of the 12th International Symposium on Parameterized and Exact Computation, 2017

Exploring the Complexity of Layout Parameters in Tournaments and Semi-Complete Digraphs.
Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017

Split Decomposition via Graph-Labelled Trees.
Encyclopedia of Algorithms, 2016

Linear Kernels and Single-Exponential Algorithms Via Protrusion Decompositions.
ACM Trans. Algorithms, 2016

Linear kernel for Rooted Triplet Inconsistency and other problems based on conflict packing technique.
J. Comput. Syst. Sci., 2016

On the consistency of orthology relationships.
BMC Bioinformatics, 2016

Efficient FPT Algorithms for (Strict) Compatibility of Unrooted Phylogenetic Trees.
Proceedings of the Algorithmic Aspects in Information and Management, 2016

Hadwiger Number of Graphs with Small Chordality.
SIAM J. Discrete Math., 2015

Explicit Linear Kernels via Dynamic Programming.
SIAM J. Discrete Math., 2015

A single-exponential FPT algorithm for the K4-minor cover problem.
J. Comput. Syst. Sci., 2015

FPT Algorithm and Polynomial Kernel for Linear Rank-width One Vertex Deletion.
CoRR, 2015

On Independent Set on B1-EPG Graphs.
Proceedings of the Approximation and Online Algorithms - 13th International Workshop, 2015

Hitting and Harvesting Pumpkins.
SIAM J. Discrete Math., 2014

Parameterized Domination in Circle Graphs.
Theory Comput. Syst., 2014

Contracting Graphs to Paths and Trees.
Algorithmica, 2014

Practical and Efficient Split Decomposition via Graph-Labelled Trees.
Algorithmica, 2014

Practical and Efficient Circle Graph Recognition.
Algorithmica, 2014

Obtaining a Bipartite Graph by Contracting Few Edges.
SIAM J. Discrete Math., 2013

On the (Non-)Existence of Polynomial Kernels for P l -Free Edge Modification Problems.
Algorithmica, 2013

Quartets and Unrooted phylogenetic Networks.
J. Bioinformatics and Computational Biology, 2012

Split decomposition and graph-labelled trees: Characterizations and fully dynamic algorithms for totally decomposable graphs.
Discret. Appl. Math., 2012

A single-exponential FPT algorithm for the $K_4$-minor cover problem
CoRR, 2012

A Single-Exponential FPT Algorithm for the K 4-Minor Cover Problem.
Proceedings of the Algorithm Theory - SWAT 2012, 2012

Kernels for feedback arc set in tournaments.
J. Comput. Syst. Sci., 2011

Contracting chordal graphs and bipartite graphs to paths and trees.
Electron. Notes Discret. Math., 2011

Circle Graph Recognition in Time O(n+m) α(n+m)
CoRR, 2011

Conflict Packing yields linear vertex-kernels for Rooted Triplet Inconsistency and other problems
CoRR, 2011

Conflict Packing Yields Linear Vertex-Kernels for k -FAST, k -dense RTI and a Related Problem.
Proceedings of the Mathematical Foundations of Computer Science 2011, 2011

Polynomial kernels for 3-leaf power graph modification problems.
Discret. Appl. Math., 2010

A survey of the algorithmic aspects of modular decomposition.
Comput. Sci. Rev., 2010

On the (non-)existence of polynomial kernels for Pl-free edge modification problems
CoRR, 2010

Fully Dynamic Algorithm for Recognition and Modular Decomposition of Permutation Graphs.
Algorithmica, 2010

Generalized Graph Clustering: Recognizing (p, q)-Cluster Graphs.
Proceedings of the Graph Theoretic Concepts in Computer Science, 2010

Milling a Graph with Turn Costs: A Parameterized Complexity Perspective.
Proceedings of the Graph Theoretic Concepts in Computer Science, 2010

On the (Non-)existence of Polynomial Kernels for Pl-free Edge Modification Problems.
Proceedings of the Parameterized and Exact Computation - 5th International Symposium, 2010

Linear time 3-approximation for the MAST problem.
ACM Trans. Algorithms, 2009

Interval Completion Is Fixed Parameter Tractable.
SIAM J. Comput., 2009

Computation of Perfect DCJ Rearrangement Scenarios with Linear and Circular Chromosomes.
Journal of Computational Biology, 2009

Edge-maximal graphs of branchwidth k: The k-branches.
Discret. Math., 2009

Branchwidth of chordal graphs.
Discret. Appl. Math., 2009

On the approximability of the Maximum Agreement SubTree and Maximum Compatible Tree problems.
Discret. Appl. Math., 2009

Kinetic maintenance of mobile k-centres on trees.
Discret. Appl. Math., 2009

Abstract Milling with Turn Costs
CoRR, 2009

Computing galled networks from real data.
Bioinformatics, 2009

The Structure of Level-k Phylogenetic Networks.
Proceedings of the Combinatorial Pattern Matching, 20th Annual Symposium, 2009

Competitive graph searches.
Theor. Comput. Sci., 2008

Optimal Distance Labeling for Interval Graphs and Related Graph Families.
SIAM J. Discrete Math., 2008

A Simple Linear Time LexBFS Cograph Recognition Algorithm.
SIAM J. Discrete Math., 2008

A more efficient algorithm for perfect sorting by reversals.
Inf. Process. Lett., 2008

Perfect DCJ Rearrangement.
Proceedings of the Comparative Genomics, International Workshop, 2008

Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations.
Proceedings of the Automata, Languages and Programming, 35th International Colloquium, 2008

A note on alpha-drawable k-trees.
Proceedings of the 20th Annual Canadian Conference on Computational Geometry, 2008

Perfect Sorting by Reversals Is Not Always Difficult.
IEEE/ACM Trans. Comput. Biology Bioinform., 2007

Can transitive orientation make sandwich problems easier?
Discret. Math., 2007

Simple, linear-time modular decomposition
CoRR, 2007

Interval completion with few edges.
Proceedings of the 39th Annual ACM Symposium on Theory of Computing, 2007

Dynamic Distance Hereditary Graphs Using Split Decomposition.
Proceedings of the Algorithms and Computation, 18th International Symposium, 2007

Eclecticism shrinks even small worlds.
Distributed Computing, 2006

Fully dynamic recognition algorithm and certificate for directed cographs.
Discret. Appl. Math., 2006

Generation of Graphs with Bounded Branchwidth.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2006

Aspects algorithmiques de la décomposition modulaire. (Algorithmic aspects of modular decomposition).
, 2006

Edge-maximal graphs of branchwidth k.
Electron. Notes Discret. Math., 2005

A simple linear time algorithm for cograph recognition.
Discret. Appl. Math., 2005

Revisiting T. Uno and M. Yagiura's Algorithm .
Proceedings of the Algorithms and Computation, 16th International Symposium, 2005

New Tools and Simpler Algorithms for Branchwidth.
Proceedings of the Algorithms, 2005

On the Approximation of Computing Evolutionary Trees.
Proceedings of the Computing and Combinatorics, 11th Annual International Conference, 2005

A Simple Linear-Time Modular Decomposition Algorithm for Graphs, Using Order Extension.
Proceedings of the Algorithm Theory, 2004

Maximal Common Connected Sets of Interval Graphs.
Proceedings of the Combinatorial Pattern Matching, 15th Annual Symposium, 2004

A note on finding all homogeneous set sandwiches.
Inf. Process. Lett., 2003

Distance labeling scheme and split decomposition.
Discret. Math., 2003

Approximate Multicommodity Flow for WDM Networks Design.
Proceedings of the SIROCCO 10: Proceedings of the 10th Internaltional Colloquium on Structural Information Complexity, 2003

Optimal Distance Labeling for Interval and Circular-Arc Graphs.
Proceedings of the Algorithms, 2003

A simple paradigm for graph recognition: application to cographs and distance hereditary graphs.
Theor. Comput. Sci., 2001

Split Decomposition and Distance Labelling: An Optimal Scheme For Distance Hereditary Graphs.
Electron. Notes Discret. Math., 2001

Linear time recognition of P4-indifference graphs.
Discrete Mathematics & Theoretical Computer Science, 2001

Diameter determination on restricted graph families.
Discret. Appl. Math., 2001

Approximate Distance Labeling Schemes.
Proceedings of the Algorithms, 2001

Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing.
Theor. Comput. Sci., 2000

Approximate Distance Labeling Schemes.
Electron. Notes Discret. Math., 2000

Partition Refinement Techniques: An Interesting Algorithmic Tool Kit.
Int. J. Found. Comput. Sci., 1999

Diameter Determination on Restricted Graph Faminlies.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 1998

A Synthesis on Partition Refinement: A Useful Routine for Strings, Graphs, Boolean Matrices and Automata.
Proceedings of the STACS 98, 1998

Chordal Graphs and Their Clique Graphs.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 1995