Christophe Paul

Order, December, 2025

The Local Structure Theorem for Graph Minors with Finite Index.

[BibT_eX]

[DOI]

CoRR, July, 2025

On a tree-based variant of bandwidth and forbidding simple topological minors.

[BibT_eX]

[DOI]

Hugo Jacob

William Lochet

CoRR, February, 2025

Twin-Width One.

[BibT_eX]

[DOI]

Proceedings of the 42nd International Symposium on Theoretical Aspects of Computer Science, 2025

2024

Tree-Layout Based Graph Classes: Proper Chordal Graphs.

[BibT_eX]

[DOI]

Proceedings of the 41st International Symposium on Theoretical Aspects of Computer Science, 2024

Delineating Half-Integrality of the Erdős-Pósa Property for Minors: The Case of Surfaces.

[BibT_eX]

[DOI]

Proceedings of the 51st International Colloquium on Automata, Languages, and Programming, 2024

Obstructions to Erdös-Pósa Dualities for Minors.

[BibT_eX]

[DOI]

Proceedings of the 65th IEEE Annual Symposium on Foundations of Computer Science, 2024

2023

Edge-treewidth: Algorithmic and combinatorial properties.

[BibT_eX]

[DOI]

Loïc Magne

Abhijat Sharma

Discret. Appl. Math., December, 2023

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

[BibT_eX]

[DOI]

Guillaume Mescoff

Discret. Math., April, 2023

Preface of STACS 2020 Special Issue.

[BibT_eX]

[DOI]

Markus Bläser

Theory Comput. Syst., February, 2023

Universal Obstructions of Graph Parameters.

[BibT_eX]

[DOI]

CoRR, 2023

2022

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

[BibT_eX]

[DOI]

Guillaume Mescoff

Discret. Appl. Math., 2022

2021

Preface of STACS 2019 Special Issue.

[BibT_eX]

[DOI]

Rolf Niedermeier

Theory Comput. Syst., 2021

Edge-trewidth: Algorithmic and combinatorial properties.

[BibT_eX]

[DOI]

Loïc Magne

Abhijat Sharma

CoRR, 2021

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

[BibT_eX]

[DOI]

Proceedings of the Fundamentals of Computation Theory - 23rd International Symposium, 2021

2020

Edge degeneracy: Algorithmic and structural results.

[BibT_eX]

[DOI]

Stratis Limnios

Joanny Perret

Theor. Comput. Sci., 2020

On independent set in B1-EPG graphs.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2020

A polynomial time algorithm to compute the connected tree-width of a series-parallel graph.

[BibT_eX]

[DOI]

Guillaume Mescoff

CoRR, 2020

Special Issue Dedicated to the 13th International Symposium on Parameterized and Exact Computation.

[BibT_eX]

[DOI]

Algorithmica, 2020

Hierarchical Clusterings of Unweighted Graphs.

[BibT_eX]

[DOI]

Svein Høgemo

Proceedings of the 45th International Symposium on Mathematical Foundations of Computer Science, 2020

A Linear Fixed Parameter Tractable Algorithm for Connected Pathwidth.

[BibT_eX]

[DOI]

Mamadou Moustapha Kanté

Proceedings of the 28th Annual European Symposium on Algorithms, 2020

2019

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

[BibT_eX]

[DOI]

J. Graph Theory, 2019

Explicit Linear Kernels for Packing Problems.

[BibT_eX]

[DOI]

Valentin Garnero

Ignasi Sau

Algorithmica, 2019

Connected Search for a Lazy Robber.

[BibT_eX]

[DOI]

Isolde Adler

Proceedings of the 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2019

2018

Exploring the Complexity of Layout Parameters in Tournaments and Semicomplete Digraphs.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2018

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

[BibT_eX]

[DOI]

Derek G. Corneil

Sang-il Oum

Discret. Appl. Math., 2018

2017

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

[BibT_eX]

[DOI]

CoRR, 2017

Parameterized Complexity of Finding a Spanning Tree with Minimum Reload Cost Diameter.

[BibT_eX]

[DOI]

Proceedings of the 12th International Symposium on Parameterized and Exact Computation, 2017

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

[BibT_eX]

[DOI]

Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017

2016

Split Decomposition via Graph-Labelled Trees.

[BibT_eX]

[DOI]

Encyclopedia of Algorithms, 2016

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

[BibT_eX]

[DOI]

Stéphan Thomassé

J. Comput. Syst. Sci., 2016

On the consistency of orthology relationships.

[BibT_eX]

[DOI]

Mark Jones

Céline Scornavacca

BMC Bioinform., 2016

Parameterized Complexity of the MINCCA Problem on Graphs of Bounded Decomposability.

[BibT_eX]

[DOI]

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2016

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

[BibT_eX]

[DOI]

Proceedings of the Algorithmic Aspects in Information and Management, 2016

2015

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

[BibT_eX]

[DOI]

Geevarghese Philip

J. Comput. Syst. Sci., 2015

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

[BibT_eX]

[DOI]

Mamadou Moustapha Kanté

O-joung Kwon

CoRR, 2015

An FPT 2-Approximation for Tree-cut Decomposition.

[BibT_eX]

[DOI]

Proceedings of the Approximation and Online Algorithms - 13th International Workshop, 2015

On Independent Set on B1-EPG Graphs.

[BibT_eX]

[DOI]

Proceedings of the Approximation and Online Algorithms - 13th International Workshop, 2015

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

[BibT_eX]

[DOI]

Mamadou Moustapha Kanté

O-joung Kwon

Proceedings of the 10th International Symposium on Parameterized and Exact Computation, 2015

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

[BibT_eX]

[DOI]

Ignasi Sau

Proceedings of the 10th International Symposium on Parameterized and Exact Computation, 2015

A Polynomial-Time Algorithm for Outerplanar Diameter Improvement.

[BibT_eX]

[DOI]

Mathias Weller

Proceedings of the Computer Science - Theory and Applications, 2015

2014

Practical and Efficient Split Decomposition via Graph-Labelled Trees.

[BibT_eX]

[DOI]

Algorithmica, 2014

Practical and Efficient Circle Graph Recognition.

[BibT_eX]

[DOI]

Algorithmica, 2014

Hadwiger Number of Graphs with Small Chordality.

[BibT_eX]

[DOI]

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2014

Explicit Linear Kernels via Dynamic Programming.

[BibT_eX]

[DOI]

Valentin Garnero

Ignasi Sau

Proceedings of the 31st International Symposium on Theoretical Aspects of Computer Science, 2014

2013

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

[BibT_eX]

[DOI]

Algorithmica, 2013

Linear Kernels and Single-Exponential Algorithms via Protrusion Decompositions.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages, and Programming - 40th International Colloquium, 2013

2012

Quartets and Unrooted phylogenetic Networks.

[BibT_eX]

[DOI]

Philippe Gambette

Vincent Berry

J. Bioinform. Comput. Biol., 2012

Split decomposition and graph-labelled trees: Characterizations and fully dynamic algorithms for totally decomposable graphs.

[BibT_eX]

[DOI]

Emeric Gioan

Discret. Appl. Math., 2012

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

[BibT_eX]

[DOI]

Geevarghese Philip

CoRR, 2012

Parameterized Domination in Circle Graphs.

[BibT_eX]

[DOI]

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2012

A Single-Exponential FPT Algorithm for the K 4-Minor Cover Problem.

[BibT_eX]

[DOI]

Geevarghese Philip

Proceedings of the Algorithm Theory - SWAT 2012, 2012

2011

Contracting chordal graphs and bipartite graphs to paths and trees.

[BibT_eX]

[DOI]

Electron. Notes Discret. Math., 2011

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

[BibT_eX]

[DOI]

CoRR, 2011

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

[BibT_eX]

[DOI]

Stéphan Thomassé

CoRR, 2011

Conflict Packing Yields Linear Vertex-Kernels for k -FAST, k -dense RTI and a Related Problem.

[BibT_eX]

[DOI]

Stéphan Thomassé

Proceedings of the Mathematical Foundations of Computer Science 2011, 2011

Contracting Graphs to Paths and Trees.

[BibT_eX]

[DOI]

Proceedings of the Parameterized and Exact Computation - 6th International Symposium, 2011

Obtaining a Bipartite Graph by Contracting Few Edges.

[BibT_eX]

[DOI]

Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2011

Hitting and Harvesting Pumpkins.

[BibT_eX]

[DOI]

Proceedings of the Algorithms - ESA 2011, 2011

2010

A survey of the algorithmic aspects of modular decomposition.

[BibT_eX]

[DOI]

Comput. Sci. Rev., 2010

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

[BibT_eX]

[DOI]

Sylvain Guillemot

CoRR, 2010

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

[BibT_eX]

[DOI]

Proceedings of the Graph Theoretic Concepts in Computer Science, 2010

Milling a Graph with Turn Costs: A Parameterized Complexity Perspective.

[BibT_eX]

[DOI]

Proceedings of the Graph Theoretic Concepts in Computer Science, 2010

On the (Non-)existence of Polynomial Kernels for Pl-free Edge Modification Problems.

[BibT_eX]

[DOI]

Sylvain Guillemot

Proceedings of the Parameterized and Exact Computation - 5th International Symposium, 2010

2009

Linear time 3-approximation for the MAST problem.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2009

Interval Completion Is Fixed Parameter Tractable.

[BibT_eX]

[DOI]

SIAM J. Comput., 2009

Computation of Perfect DCJ Rearrangement Scenarios with Linear and Circular Chromosomes.

[BibT_eX]

[DOI]

J. Comput. Biol., 2009

Edge-maximal graphs of branchwidth k: The k-branches.

[BibT_eX]

[DOI]

Discret. Math., 2009

Branchwidth of chordal graphs.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2009

On the approximability of the Maximum Agreement SubTree and Maximum Compatible Tree problems.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2009

Abstract Milling with Turn Costs

[BibT_eX]

[DOI]

CoRR, 2009

Computing galled networks from real data.

[BibT_eX]

[DOI]

Bioinform., 2009

Polynomial Kernels for 3-Leaf Power Graph Modification Problems.

[BibT_eX]

[DOI]

Stéphane Bessy

Proceedings of the Combinatorial Algorithms, 20th International Workshop, 2009

Kernels for Feedback Arc Set In Tournaments.

[BibT_eX]

[DOI]

Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2009

The Structure of Level-k Phylogenetic Networks.

[BibT_eX]

[DOI]

Philippe Gambette

Vincent Berry

Proceedings of the Combinatorial Pattern Matching, 20th Annual Symposium, 2009

2008

Competitive graph searches.

[BibT_eX]

[DOI]

Binh-Minh Bui-Xuan

Theor. Comput. Sci., 2008

Optimal Distance Labeling for Interval Graphs and Related Graph Families.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2008

A more efficient algorithm for perfect sorting by reversals.

[BibT_eX]

[DOI]

Sèverine Bérard

Cédric Chauve

Inf. Process. Lett., 2008

Perfect DCJ Rearrangement.

[BibT_eX]

[DOI]

Proceedings of the Comparative Genomics, International Workshop, 2008

Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 35th International Colloquium, 2008

A note on alpha-drawable k-trees.

[BibT_eX]

Proceedings of the 20th Annual Canadian Conference on Computational Geometry, 2008

2007

Can transitive orientation make sandwich problems easier?

[BibT_eX]

[DOI]

Discret. Math., 2007

Simple, linear-time modular decomposition

[BibT_eX]

[DOI]

CoRR, 2007

Interval completion with few edges.

[BibT_eX]

[DOI]

Proceedings of the 39th Annual ACM Symposium on Theory of Computing, 2007

Dynamic Distance Hereditary Graphs Using Split Decomposition.

[BibT_eX]

[DOI]

Emeric Gioan

Proceedings of the Algorithms and Computation, 18th International Symposium, 2007

Kinetic Maintenance of Mobile k-Centres on Trees.

[BibT_eX]

[DOI]

Stephane Durocher

Proceedings of the Algorithms and Computation, 18th International Symposium, 2007

2006

Generation of Graphs with Bounded Branchwidth.

[BibT_eX]

[DOI]

Andrzej Proskurowski

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2006

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

[BibT_eX]

[DOI]

, 2006

2005

Edge-maximal graphs of branchwidth k.

[BibT_eX]

[DOI]

Electron. Notes Discret. Math., 2005

A simple linear time algorithm for cograph recognition.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2005

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

[BibT_eX]

[DOI]

Christophe Crespelle

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2005

Perfect Sorting by Reversals Is Not Always Difficult.

[BibT_eX]

[DOI]

Proceedings of the Algorithms in Bioinformatics, 5th International Workshop, 2005

Revisiting T. Uno and M. Yagiura's Algorithm .

[BibT_eX]

[DOI]

Binh-Minh Bui-Xuan

Proceedings of the Algorithms and Computation, 16th International Symposium, 2005

New Tools and Simpler Algorithms for Branchwidth.

[BibT_eX]

[DOI]

Proceedings of the Algorithms, 2005

On the Approximation of Computing Evolutionary Trees.

[BibT_eX]

[DOI]

Proceedings of the Computing and Combinatorics, 11th Annual International Conference, 2005

2004

Fully-Dynamic Recognition Algorithm and Certificate for Directed Cographs.

[BibT_eX]

[DOI]

Christophe Crespelle

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2004

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

[BibT_eX]

[DOI]

Fabien de Montgolfier

Proceedings of the Algorithm Theory, 2004

Eclecticism shrinks even small worlds.

[BibT_eX]

[DOI]

Pierre Fraigniaud

Proceedings of the Twenty-Third Annual ACM Symposium on Principles of Distributed Computing, 2004

Maximal Common Connected Sets of Interval Graphs.

[BibT_eX]

[DOI]

Mathieu Raffinot

Proceedings of the Combinatorial Pattern Matching, 15th Annual Symposium, 2004

2003

A note on finding all homogeneous set sandwiches.

[BibT_eX]

[DOI]

Emmanuelle Lebhar

Inf. Process. Lett., 2003

Distance labeling scheme and split decomposition.

[BibT_eX]

[DOI]

Discret. Math., 2003

A Simple Linear Time LexBFS Cograph Recognition Algorithm.

[BibT_eX]

[DOI]

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2003

Approximate Multicommodity Flow for WDM Networks Design.

[BibT_eX]

Mohamed Bouklit

David Coudert

Jean-François Lalande

Hervé Rivano

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.

[BibT_eX]

[DOI]

Proceedings of the Algorithms, 2003

2001

A simple paradigm for graph recognition: application to cographs and distance hereditary graphs.

[BibT_eX]

[DOI]

Guillaume Damiand

Theor. Comput. Sci., 2001

Split Decomposition and Distance Labelling: An Optimal Scheme For Distance Hereditary Graphs.

[BibT_eX]

[DOI]

Electron. Notes Discret. Math., 2001

Linear time recognition of P4-indifference graphs.

[BibT_eX]

[DOI]

Laurent Viennot

Discret. Math. Theor. Comput. Sci., 2001

Diameter determination on restricted graph families.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2001

Approximate Distance Labeling Schemes.

[BibT_eX]

[DOI]

Proceedings of the Algorithms, 2001

2000

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

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2000

Approximate Distance Labeling Schemes.

[BibT_eX]

[DOI]

Electron. Notes Discret. Math., 2000

1999

Partition Refinement Techniques: An Interesting Algorithmic Tool Kit.

[BibT_eX]

[DOI]

Laurent Viennot

Int. J. Found. Comput. Sci., 1999

1998

Diameter Determination on Restricted Graph Faminlies.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

Laurent Viennot

Proceedings of the STACS 98, 1998

1995

Chordal Graphs and Their Clique Graphs.

[BibT_eX]

[DOI]

Philippe Galinier