Christophe Crespelle - Publications

Publications

JOURNALS

[J21]	A quasi-quadratic vertex-kernel for Cograph Edge Editing.
	Christophe Crespelle, Remi Pellerin and Stephan Thomasse.
	In Discrete Applied Mathematics [ On-line ], volume 357, pages 282-296, 2024.
[J20]	A survey of parameterized algorithms and the complexity of edge modification.
	Christophe Crespelle, Pål Grønås Drange, Fedor V. Fomin and Petr A. Golovach.
	In Computer Science Review [ On-line ], volume 48, pages 100556, 2023.
[J19]	A graph-theory-based multi-scale analysis of hierarchical cascade in molecular clouds - Application to the NGC 2264 region.
	Benjamin Thomasson, Isabelle Joncour, Estelle Moraux, Christophe Crespelle, Frédérique Motte, Yohan Pouteau and Thomas Nony.
	In Astronomy & Astrophysics [ On-line ], volume 665, pages A119, 2022.
[J18]	Cyclability in Graph Classes.
	Christophe Crespelle and Petr A. Golovach.
	In Discrete Applied mathematics [ On-line ], volume 313, pages 147-178, 2022.
[J17]	On the effectiveness of the incremental approach to minimal chordal edge modification
	Jean R. S. Blair and Christophe Crespelle.
	In Theoretical Computer Science [ On-line ], volume 888, pages 1-12, 2021.
[J16]	Faster and enhanced inclusion-minimal cograph completion
	Christophe Crespelle, Daniel Lokshtanov, Thi Ha Duong Phan and Eric Thierry.
	In Discrete Applied Mathematics [ On-line ], volume 288, pages 138-151, 2021.
[J15]	Fully dynamic representations of interval graphs
	Christophe Crespelle.
	In Theoretical Computer Science [ On-line ], volume 759, pages 14-49, 2019.
[J14]	Non-altering time scales for aggregation of dynamic networks into series of graphs.
	Yannick Léo, Christophe Crespelle and Eric Fleury.
	In Computer Networks [ On-line ], volume 148, pages 108-119, 2019.
[J13]	An O(n²)-time algorithm for the minimal permutation completion problem.
	Christophe Crespelle, Anthony Perez and Ioan Todinca.
	In Discrete Applied Mathematics [ On-line ], volume 254, pages 80-95, 2019.
[J12]	The link stream of contacts in a whole hospital.
	Lucie Martinet, Christophe Crespelle, Eric Fleury, Pierre-Yves Boëlle and Didier Guillemot.
	In Social Network Analysis and Mining [ On-line ], volume 8, article 59, 2018.
[J11]	Rigorous Measurement of the Internet Degree Distribution.
	Matthieu Latapy, Elie Rotenberg, Christophe Crespelle and Fabien Tarissan.
	In Complex Systems [ On-line ], volume 26, issue 1, 2017.
[J10]	Linearity is Strictly More Powerful than Contiguity for Encoding Graphs.
	Christophe Crespelle, Tien-Nam Le, Kevin Perrot and Thi Ha Duong Phan.
	In Discrete Mathematics [ On-line ], volume 339, issue 8, pages 2168-2177, 2016.
[J9]	Computing the Directed Cartesian-Product Decomposition of a Directed Graph from its Undirected Decomposition in Linear Time.
	Christophe Crespelle and Eric Thierry.
	In Discrete Mathematics [ On-line ], volume 338, issue 12, pages 2393-2407, 2015.
	Draft [ pdf ]
[J8]	On the Termination of Some Biclique Operators on Multipartite Graphs.
	Christophe Crespelle, Matthieu Latapy and Thi Ha Duong Phan.
	In Discrete Applied Mathematics [ On-line ], volume 195, pages 59-73, 2015.
	Draft [ pdf ]
[J7]	Termination of the Iterated Strong-Factor Operator on Multipartite Graphs.
	Christophe Crespelle, Thi Ha Duong Phan and The Hung Tran.
	In Theoretical Computer Science [ On-line ], volume 571, pages 67-77, 2015.
	Draft [ pdf ]
[J6]	(Nearly-)Tight Bounds on the Contiguity and Linearity of Cographs.
	Christophe Crespelle and Philippe Gambette.
	In Theoretical Computer Science [ On-line ], volume 522, pages 1-12, 2014.
	Draft [ pdf ]
[J5]	An O(n²)-time Algorithm for the Minimal Interval Completion Problem.
	Christophe Crespelle and Ioan Todinca.
	In Theoretical Computer Science [ On-line ], volume 494, pages 75-85, 2013.
	Draft [ pdf ]
[J4]	Evaluation of a New Method for Measuring the Internet Degree Distribution: Simulation Results.
	Christophe Crespelle and Fabien Tarissan.
	In Computer Communications [ On-line ], volume 34, issue 5, pages 635-648, 2011.
	Draft [ pdf ]
[J3]	Unrestricted and Complete Breadth-First Search of Trapezoid Graphs in O(n) Time.
	Christophe Crespelle and Philippe Gambette.
	In Information Processing Letters [ On-line ], volume 110, issues 12-13, pages 497-502, 2010.
	Draft [ pdf ]
[J2]	Fully Dynamic Algorithm for Recognition and Modular Decomposition of Permutation Graphs.
	Christophe Crespelle and Christophe Paul.
	In Algorithmica [ On-line ], volume 58, number 2, pages 405-432, 2010.
	Draft [ pdf ]
[J1]	Fully Dynamic Recognition Algorithm and Certificate for Directed Cographs.
	Christophe Crespelle and Christophe Paul.
	In Discrete Applied Mathematics [ On-line ], volume 154, issue 12, pages 1722-1741, 2006.
	Draft [ pdf ]

CONFERENCES AND WORKSHOPS

[C21]	Dividing Permutations in the Semiring of Functional Digraphs.
	Florian Bridoux, Christophe Crespelle, Thi Ha Duong Phan and Adrien Richard.
	30th International Workshop on Cellular Automata and Discrete Complex Systems – AUTOMATA 2024 [ On-line ]. Number 14782 in LNCS, pages 95-107, 2024.
[C20]	Linear-Time Minimal Cograph Editing.
	Christophe Crespelle.
	23rd International Symposium on Fundamentals of Computation Theory – FCT 2021 [ On-line ]. Number 12867 in LNCS, pages 176-189, 2021.
[C19]	Completion to chordal distance-hereditary graphs: a quartic vertex-kernel.
	Christophe Crespelle, Benjamin Gras and Anthony Perez
	47th International Workshop on Graph-Theoretic Concepts in Computer Science – WG 2021 [ On-line ]. Number 12911 in LNCS, pages 156-168, 2021.
[C18]	Cyclability in Graph Classes.
	Christophe Crespelle, Carl Feghali and Petr A. Golovach.
	30th International Symposium on Algorithms and Computation – ISAAC 2019 [ On-line ]. Number 149 in LIPIcs, article 16, Schloss Dagstuhl, 2019.
[C17]	Faster and Enhanced Inclusion-Minimal Cograph Completion.
	Christophe Crespelle, Daniel Lokshtanov, Thi Ha Duong Phan and Eric Thierry.
	In 11th Annual International Conference on Combinatorial Optimization and Applications – COCOA 2017 [ On-line ]. Number 10627 in LNCS, part I, pages 210-224, 2017.
[C16]	An O(n²)-time algorithm for the minimal permutation completion problem.
	Christophe Crespelle, Anthony Perez and Ioan Todinca.
	In 41st International Workshop on Graph-Theoretic Concepts in Computer Science – WG 2015 [ On-line ]. Number 9224 in LNCS, pages 103-115, 2016.
	Draft [ pdf ]
[C15]	Non-Altering Time Scales for Aggregation of Dynamic Networks into Series of Graphs.
	Yannick Léo, Christophe Crespelle and Eric Fleury.
	In 11th International Conference on emerging Networking EXperiments and Technologies – CoNEXT 2015 [ On-line ]. ACM, 2015.
[C14]	Linearity is Strictly More Powerful than Contiguity for Encoding Graphs.
	Christophe Crespelle, Tien-Nam Le, Kevin Perrot and Thi Ha Duong Phan.
	In 14th International Symposium on Algorithms and Data Structures – WADS 2015 [ On-line ]. Number 9214 in LNCS, pages 212-223, 2015.
	Draft [ pdf ]
[C13]	Measuring the Degree Distribution of Routers in the Core Internet.
	Matthieu Latapy, Elie Rotenberg, Christophe Crespelle and Fabien Tarissan.
	In 13th IFIP International Conference on Networking – Networking 2014 [ On-line ]. IEEE, pages 1-9, 2014.
	Draft [ pdf ]
[C12]	Measuring Routing Tables in the Internet.
	Elie Rotenberg, Christophe Crespelle and Matthieu Latapy.
	6th IEEE International Workshop on Network Science and Communication Networks – NetSciCom 2014 [ On-line ].
	In INFOCOM IEEE Conference on Computer Communications Workshops. IEEE, pages 795-800, 2014.
	Draft [ pdf ]
[C11]	Dynamic Contact Network Analysis in Hospital Wards.
	Lucie Martinet, Christophe Crespelle and Eric Fleury.
	In 5th Workshop on Complex Networks – CompleNet 2014 [ On-line ]. Number 549 in Studies in Computational Intelligence Series, pages 241-249, Springer, 2014.
	Draft [ pdf ]
[C10]	A Linear-Time Algorithm for Computing the Prime Decomposition of a Directed Graph with Regard to the Cartesian Product.
	Christophe Crespelle, Eric Thierry and Thomas Lambert.
	In 19th Annual International Computing and Combinatorics Conference – COCOON 2013 [ On-line ]. Number 7936 in LNCS, pages 469-480, 2013.
	Draft [ pdf ]
[C9]	Linear-time Constant-ratio Approximation Algorithm and Tight Bounds for the Contiguity of Cographs.
	Christophe Crespelle and Philippe Gambette.
	In Seventh International Workshop on Algorithms and Computation – WALCOM 2013 [ On-line ]. Number 7748 in LNCS, pages 126-136, 2013.
	Draft [ pdf ]
[C8]	On the Structure of Changes in Dynamic Contact Networks.
	Vincent Neiger, Christophe Crespelle and Eric Fleury.
	Workshop on Complex Networks and their Applications – Complex Networks 2012 [ On-line ].
	In Eighth International Conference on Signal Image Technology and Internet Based Systems – SITIS 2012. IEEE, pages 731 - 738, 2012.
	Draft [ pdf ]
[C7]	Termination of Multipartite Graph Series Arising from Complex Network Modelling.
	Matthieu Latapy, Thi Ha Duong Phan, Christophe Crespelle and Thanh Qui Nguyen.
	In 4th Annual International Conference on Combinatorial Optimization and Applications – COCOA 2010 [ On-line ]. Number 6508 in LNCS, part I, pages 1-10, 2010.
	Draft [ pdf ]
[C6]	An O(n²)-time Algorithm for the Minimal Interval Completion Problem.
	Christophe Crespelle and Ioan Todinca.
	In 7th Annual Conference on Theory and Applications of Models of Computation – TAMC 2010 [ On-line ]. Number 6108 in LNCS, pages 175-186, 2010.
	Draft [ pdf ]
[C5]	Rigorous Measurement of IP-level Neighborhood of Internet Core Routers.
	Christophe Crespelle, Matthieu Latapy and Elie Rotenberg.
	2nd IEEE International Workshop on Network Science and Communication Networks – NetSciCom 2010 [ On-line ].
	In INFOCOM IEEE Conference on Computer Communications Workshops. IEEE, pages 1-6, 2010.
	Draft [ pdf ]
[C4]	Fully Dynamic Representations of Interval Graphs.
	Christophe Crespelle.
	In 35th International Workshop on Graph-Theoretic Concepts in Computer Science – WG 2009 [ On-line ]. Number 5911 in LNCS, pages 77-87, 2009.
	Draft [ pdf ]
[C3]	Efficient Neighborhood Encoding for Interval Graphs and Permutation Graphs and O(n) Breadth-First Search.
	Christophe Crespelle and Philippe Gambette.
	In 20th International Workshop on Combinatorial Algorithms – IWOCA 2009 [ On-line ]. Number 5874 in LNCS, pages 146-157, 2009.
	Draft [ pdf ]
[C2]	Fully Dynamic Algorithm for Recognition and Modular Decomposition of Permutation Graphs.
	Christophe Crespelle and Christophe Paul.
	In 31st International Workshop on Graph-Theoretic Concepts in Computer Science – WG 2005 [ On-line ]. Number 3787 in LNCS, pages 38-48, 2005.
	Draft [ pdf ]
[C1]	Fully Dynamic Recognition Algorithm and Certificate for Directed Cographs.
	Christophe Crespelle and Christophe Paul.
	In 30th International Workshop on Graph-Theoretic Concepts in Computer Science – WG 2004 [ On-line ]. Number 3353 in LNCS, pages 93-104, 2004.
	Draft [ pdf ]

THESES

[T3]	Structures of Complex Networks and of their Dynamics.
	Christophe Crespelle.
	Habilitation Thesis (HDR, Habilitation à Diriger des Recherches), University Claude Bernard Lyon 1, 2017. [ pdf ]
[T2]	Représentations dynamiques de graphes.
	Christophe Crespelle.
	Ph.D. Thesis, University of Montpellier II, 2007. [ pdf ]
[T1]	Quelques variations sur la dimension des ensembles partiellement ordonnés.
	Christophe Crespelle.
	Master Thesis, University of Montpellier II, 2003. [ pdf ]

Main page