Christophe Paul

Evangelos Protopapas

Proceedings of the 41st International Symposium on Theoretical Aspects 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]

Evangelos Protopapas

CoRR, 2023

Graph Parameters, Universal Obstructions, and WQO.

[BibT_eX]

[DOI]

Evangelos Protopapas

CoRR, 2023

2022

A Linear Fixed Parameter Tractable Algorithm for Connected Pathwidth.

[BibT_eX]

[DOI]

Mamadou Moustapha Kanté

SIAM J. Discret. Math., 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

Connected search for a lazy robber.

[BibT_eX]

[DOI]

Isolde Adler

J. Graph Theory, 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

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

[BibT_eX]

[DOI]

Networks, 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

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

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

An FPT 2-Approximation for Tree-Cut Decomposition.

[BibT_eX]

[DOI]

Algorithmica, 2018

2017

Parameterized complexity of the MINCCA problem on graphs of bounded decomposability.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2017

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

[BibT_eX]

[DOI]

Ignasi Sau

J. Comput. Syst. Sci., 2017

A polynomial-time algorithm for Outerplanar Diameter Improvement.

[BibT_eX]

[DOI]

Mathias Weller

J. Comput. Syst. Sci., 2017

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

[BibT_eX]

[DOI]

CoRR, 2017

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

[BibT_eX]

[DOI]

Mamadou Moustapha Kanté

O-joung Kwon

Algorithmica, 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 Kernels and Single-Exponential Algorithms Via Protrusion Decompositions.

[BibT_eX]

[DOI]

ACM Trans. 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

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

[BibT_eX]

[DOI]

Proceedings of the Algorithmic Aspects in Information and Management, 2016

2015

Hadwiger Number of Graphs with Small Chordality.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2015

Explicit Linear Kernels via Dynamic Programming.

[BibT_eX]

[DOI]

Valentin Garnero

Ignasi Sau

SIAM J. Discret. Math., 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

On Independent Set on B1-EPG Graphs.

[BibT_eX]

[DOI]

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

2014

Hitting and Harvesting Pumpkins.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2014

Parameterized Domination in Circle Graphs.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2014

Contracting Graphs to Paths and Trees.

[BibT_eX]

[DOI]

Algorithmica, 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

2013

Obtaining a Bipartite Graph by Contracting Few Edges.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2013

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

[BibT_eX]

[DOI]

Algorithmica, 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

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

Kernels for feedback arc set in tournaments.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 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

2010

Polynomial kernels for 3-leaf power graph modification problems.

[BibT_eX]

[DOI]

Stéphane Bessy

Discret. Appl. Math., 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

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

[BibT_eX]

[DOI]

Christophe Crespelle

Algorithmica, 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

Kinetic maintenance of mobile k-centres on trees.

[BibT_eX]

[DOI]

Stephane Durocher

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

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 Simple Linear Time LexBFS Cograph Recognition Algorithm.

[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

Perfect Sorting by Reversals Is Not Always Difficult.

[BibT_eX]

[DOI]

IEEE ACM Trans. Comput. Biol. Bioinform., 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

2006

Eclecticism shrinks even small worlds.

[BibT_eX]

[DOI]

Pierre Fraigniaud

Distributed Comput., 2006

Fully dynamic recognition algorithm and certificate for directed cographs.

[BibT_eX]

[DOI]

Christophe Crespelle

Discret. Appl. Math., 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

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

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

[BibT_eX]

[DOI]

Fabien de Montgolfier

Proceedings of the Algorithm Theory, 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

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