Submitted manuscripts
- Algorithms and complexity for geodetic sets on planar and chordal graphs. With Dibyayan Chakraborty, Sandip Das, Harmender Gahlawat, Dimitri Lajou and Bodhayan Roy.
Manuscript, 2021. [arXiv]
A preliminary conference version was presented at ISAAC 2020.
- Characterizing extremal graphs for open neighbourhood location-domination. With Narges Ghareghani, Aida Roshany Tabrizi and Pouyeh Sharifani.
Manuscript, 2021. [arXiv]
- Monitoring the edges of a graph using distances. With Shih-Shun Kao, Ralf Klasing, Mirka Miller and Joe Ryan.
Manuscript, 2020. [arXiv].
A preliminary conference version was presented at CALDAM 2020.
- Smallest C2l+1-critical graphs of odd-girth 2k+1. With Laurent Beaudou and Reza Naserasr.
Manuscript, 2020. [arXiv]
A preliminary conference version was presented at CALDAM 2020.
- Parameterized complexity of edge-coloured and signed graph homomorphism problems. With Hervé Hocquard, Dimitri Lajou, Valia Mitsou and Théo Pierron.
Manuscript, 2020. [arXiv]
A preliminary conference version was presented at IPEC 2019.
Publications in peer-reviewed journals and conference proceedings
- [J36] On the complexity of broadcast domination and multipacking in digraphs. With Benjamin Gras, Anthony Perez and Florian Sikora.
Algorithmica, to appear in the Special issue for selected papers of IWOCA 2020. [PDF | arXiv | www]
A preliminary conference version was presented at IWOCA 2020.
2021
- [J35] Complexity and algorithms for injective edge-coloring in graphs. With Hervé Hocquard and Dimitri Lajou.
Information Processing Letters 170:106121, 2021. [PDF | HAL | arXiv | www]
- [J34] Exact square coloring of subcubic planar graphs. With Hervé Hocquard, Suchismita Mishra, Narayanan N, Reza Naserasr, Éric Sopena and Petru Valicov.
Discrete Applied Mathematics 293:74-89, 2021. [PDF | HAL | arXiv | www]
- [C18] Cliques in exact distance powers of graphs of given maximum degree. With Suchismita Mishra, Narayanan N, Reza Naserasr and Petru Valicov.
Accepted for presentation at LAGOS 2021.
2020
- [J33] Complexity of planar signed graph homomorphisms to cycles. With François Dross, Valia Mitsou, Pascal Ochem and Théo Pierron.
Discrete Applied Mathematics 284:166-178, 2020. [PDF | arXiv | www]
- [J32] Domination and location in twin-free digraphs. With Shahrzad Heydarshahi and Aline Parreau.
Discrete Applied Mathematics 284:42-52, 2020. [PDF | arXiv | www]
- [C16] Algorithms and complexity for geodetic sets on planar and chordal graphs. With Dibyayan Chakraborty, Sandip Das, Harmender Gahlawat, Dimitri Lajou and Bodhayan Roy.
Proceedings of the 31st International Symposium on Algorithms and Computation (ISAAC 2020), Leibniz International Proceedings in Informatics 181,7:1-7:15, 2020. [PDF | arXiv (full version) | www]
- [C15] Discriminating codes in geometric setups. With Sanjana Dey, Subhas C. Nandy and Arunhaba Sen.
Proceedings of the 31st International Symposium on Algorithms and Computation (ISAAC 2020), Leibniz International Proceedings in Informatics 181,24:1-24:16, 2020. [PDF | arXiv (full version) | www]
- [C14] On the complexity of broadcast domination and multipacking in digraphs. With Benjamin Gras, Anthony Perez and Florian Sikora.
Proceeedings of the 31st International Workshop on Combinatorial Algorithms (IWOCA 2020), Lecture Notes in Computer Science 12126:264-276, 2020. [PDF | www]
The full version will appear in the journal Algorithmica.
- [C13] Hardness and approximation for the geodetic set problem in some graph classes. With Dibyayan Chakraborty, Harmender Gahlawat, Subir Kumar Ghosh and Bodhayan Roy.
Proceedings of the 6th International Conference on Algorithms and Discrete Applied Mathematics (CALDAM 2020), Lecture Notes in Computer Science 12016:102-115, 2020. [PDF | arXiv | www]
- [C12] Monitoring the edges of a graph using distances. With Ralf Klasing, Mirka Miller and Joe Ryan.
Proceedings of the 6th International Conference on Algorithms and Discrete Applied Mathematics (CALDAM 2020), Lecture Notes in Computer Science 12016:28-40, 2020. [PDF | arXiv (full version) | www]
- [C11] Smallest C2l+1-critical graphs of odd-girth 2k+1. With Laurent Beaudou and Reza Naserasr.
Proceedings of the 6th International Conference on Algorithms and Discrete Applied Mathematics (CALDAM 2020), Lecture Notes in Computer Science 12016:184-196, 2020. [PDF | arXiv (full version) | www]
2019
- [J31] Strengthening the Murty-Simon conjecture on diameter 2 critical graphs. With Antoine Dailly and Adriana Hansberg.
Discrete Mathematics 342(11):3142-3159, 2019. [PDF | HAL | arXiv | www]
- [J30] Broadcast domination and multipacking: bounds and the integrality gap. With Laurent Beaudou and Richard C. Brewster.
The Australasian Journal of Combinatorics 74(1):86-97, 2019. [PDF | arXiv | www]
- [J29] Homomorphism bounds of signed bipartite K4-minor-free graphs and edge-colourings of 2k-regular K4-minor-free multigraphs. With Laurent Beaudou and Reza Naserasr.
Discrete Applied Mathematics 261:40-51, 2019. Special issue for the 2016 GO X Meeting. [PDF | HAL | arXiv | www]
- [J28] Parameterized and approximation complexity of PARTIAL VC DIMENSION. With Cristina Bazgan and Florian Sikora.
Theoretical Computer Science 766:1-15, 2019. [PDF | arXiv | www]
A preliminary conference version was presented at COCOA 2016.
- [C10] Parameterized complexity of edge-coloured and signed graph homomorphism problems. With Hervé Hocquard, Dimitri Lajou, Valia Mitsou and Théo Pierron.
Proceedings of the 14th International Symposium on Parameterized and Exact Computation (IPEC 2019), Leibniz International Proceedings in Informatics 148,15:1-15:16, 2019. [PDF | arXiv (full version) | www]
- [C9] Complexity of conjunctive regular path query homomorphisms. With Laurent Beaudou, Florent Madelaine, Lhouari Nourine and Gaétan Richard.
Proceedings of the 15th Conference on Computability in Europe (CIE 2019), Lecture Notes in Computer Science 11558:108-119, 2019. [PDF | www]
2018
- [J27] Complexity of Grundy coloring and its variants. With Édouard Bonnet, Eun Jung Kim and Florian Sikora.
Discrete Applied Mathematics 243:99-114, 2018. [PDF | www | arXiv]
A preliminary conference version was presented at COCOON 2015.
- [J26] Bounding the order of a graph using its diameter and metric dimension: a study through tree decompositions and VC dimension. With Laurent Beaudou, Peter Dankelmann, Michael A. Henning, Arnaud Mary and Aline Parreau.
SIAM Journal on Discrete Mathematics 32(2):902-918, 2018. [PDF | www | arXiv]
2017
- [J25] Parameterized and approximation complexity of the detection pair problem in graphs. With Ralf Klasing.
Journal of Graph Algorithms and Applications 21(6):1039-1056, 2017. [PDF | www | arXiv]
- [J24] The complexity of tropical graph homomorphisms. With Ararat Harutyunyan, Pavol Hell, Sylvain Legay, Yannis Manoussakis and Reza Naserasr.
Discrete Applied Mathematics 229:64-81, 2017. [PDF | www | arXiv (enhanced version)]
- [J23] Homomorphism bounds and edge-colourings of K4-minor-free graphs. With Laurent Beaudou and Reza Naserasr.
Journal of Combinatorial Theory, Series B 124:128-164, 2017. [PDF | www | arXiv]
- [J22] Identification, location-domination and metric dimension on interval and permutation graphs. II. Algorithms and complexity. With George B. Mertzios, Reza Naserasr, Aline Parreau and Petru Valicov.
Algorithmica 78(3):914-944, 2017. [PDF | www | arXiv]
A preliminary conference version was presented at WG 2015.
- [J21] Identification, location-domination and metric dimension on interval and permutation graphs. I. Bounds. With George B. Mertzios, Reza Naserasr, Aline Parreau and Petru Valicov.
Theoretical Computer Science 668:43-58, 2017. [PDF | www | arXiv]
- [J20] Structural properties of recursively partitionable graphs with connectivity 2. With Olivier Baudon, Julien Bensmail and Monika Pilśniak.
Discussiones Mathematicae Graph Theory 37(1):89-115, 2017. [PDF | www | HAL]
- [J19] Random subgraphs make identification affordable. With Guillem Perarnau and Oriol Serra.
Journal of Combinatorics 8(1):57-77, 2017. [PDF | www | arXiv]
A preliminary conference version was presented at EUROCOMB 2013.
- [J18] The complexity of signed and edge-coloured graph homomorphisms. With Richard C. Brewster, Pavol Hell and Reza Naserasr.
Discrete Mathematics 340(2):223-235, 2017. [PDF | www | arXiv]
- [J17] Location domination in line graphs. With Michael A. Henning.
Discrete Mathematics 340(1):3140-3153, 2017. [PDF | www | arXiv]
2016
- [J16] Locating-total dominating sets in twin-free graphs: a conjecture. With Michael A. Henning.
The Electronic Journal of Combinatorics 23(3):P3.9, 2016. [PDF | www | arXiv]
- [J15] Location-domination and matching in cubic graphs. With Michael A. Henning.
Discrete Mathematics 339(4):1221-1231, 2016. [PDF | www | arXiv]
- [J14] Locating-dominating sets in twin-free graphs. With Michael A. Henning, Christian Löwenstein and Thomas Sasse.
Discrete Applied Mathematics 200:52-58, 2016. [PDF | www | arXiv]
- [C8] On the approximability of PARTIAL VC DIMENSION. With Cristina Bazgan and Florian Sikora.
Proceedings of the 10th Annual International Conference on Combinatorial Optimization and Applications (COCOA 2016), Lecture Notes in Computer Science 10043:92-106, 2016. [PDF | www]
The full version appeared in the journal Theoretical Computer Science in 2019.
2015
- [J13] Locating-dominating sets and identifying codes in graphs of girth at least 5. With Camino Balbuena and Adriana Hansberg.
The Electronic Journal of Combinatorics 22(2):P2.15, 2015. [PDF | www | arXiv]
- [J12] Decision and approximation complexity for identifying codes and locating-dominating sets in restricted graph classes.
Journal of Discrete Algorithms 31:48-68, 2015. Special issue for selected papers of IWOCA 2013. [PDF | www | HAL]
A preliminary conference version was presented at IWOCA 2013.
- [J11] Large subgraphs without short cycles. With Michael Krivelevich and Guillem Perarnau.
SIAM Journal on Discrete Mathematics 29(1):65-78, 2015. [PDF | www | arXiv]
- [C7] Algorithms and complexity for metric dimension and location-domination on interval and permutation graphs. With George B. Mertzios, Reza Naserasr, Aline Parreau and Petru Valicov.
Proceedings of the 41st International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2015), Lecture Notes in Computer Science 9224:456-471, 2016. [PDF | www]
The full version appeared in the journal Algorithmica in 2017.
- [C6] Complexity of Grundy coloring and its variants. With Édouard Bonnet, Eun Jung Kim and Florian Sikora.
Proceedings of the 21st International Conference on Computing and Combinatorics (COCOON 2015), Lecture Notes in Computer Science 9198:109-120, 2015. [PDF | www]
The full version appeared in the journal Discrete Applied Mathematics in 2018.
2014
- [J10] Centroidal bases in graphs. With Ralf Klasing and Peter J. Slater.
Networks 64(2):96-108, 2014. [PDF | www | arXiv]
- [J9] An improved lower bound for (1,<=2)-identifying codes in the king grid. With Tero Laihonen and Aline Parreau.
Advances in Mathematics of Communications 8(1):35-52, 2014. [PDF | www | arXiv]
- [J8] On the structure of arbitrarily partitionable graphs with given connectivity. With Olivier Baudon, Jakub Przybyło and Mariusz Woźniak.
Discrete Applied Mathematics 162:381-385, 2014. [PDF | www | HAL]
- [C5] The complexity of signed graph homomorphisms and signed constraint satisfaction. With Reza Naserasr.
Proceedings of the 11th Latin American Symposium on Theoretical Informatics (LATIN 2014), Lecture Notes in Computer Science 8392:526-537, 2014. [PDF | www]
2013
- [J7] Identifying path covers in graphs. With Matjaž Kovše.
Journal of Discrete Algorithms 23:21-34, 2013. Special issue for selected papers of IWOCA 2012. [PDF | www]
A preliminary conference version was presented at IWOCA 2012.
- [J6] Identifying codes in line graphs. With Sylvain Gravier, Reza Naserasr, Aline Parreau and Petru Valicov.
Journal of Graph Theory 73(4):425-448, 2013. [PDF | www | arXiv]
A preliminary conference version was presented at EUROCOMB 2011.
- [J5] Characterizing extremal digraphs for identifying codes and extremal cases of Bondy's theorem on induced subsets. With Reza Naserasr and Aline Parreau.
Graphs and Combinatorics 29(3):463-473, 2013. [PDF | www | arXiv]
- [C4] Random subgraphs make identification affordable. With Guillem Perarnau and Oriol Serra.
Proceedings of the 7th European Conference on Combinatorics, Graph Theory and Applications (EUROCOMB 2013), CRM Series 16:415-420, 2013. [PDF | www]
The full version appeared in the journal Journal of Combinatorics in 2017.
- [C3] The complexity of the identifying code problem in restricted graph classes.
Proceedings of the 24th International Workshop on Combinatorial Algorithms (IWOCA 2013), Lecture Notes in Computer Science 8288:150-163, 2013. [PDF | www]
The full version appeared in the journal Journal of Discrete Algorithms in 2015.
2012
- [J4] On the size of identifying codes in triangle-free graphs. With Ralf Klasing, Adrian Kosowski and André Raspaud.
Discrete Applied Mathematics 160(10-11):1532-1546, 2012. [PDF | www | arXiv]
- [J3] Locally identifying colourings for graphs with given maximum degree. With Tero Laihonen, Aline Parreau and Guillem Perarnau.
Discrete Mathematics 312(10):1832-1837, 2012. [PDF | www | arXiv]
- [J2] Bounds on identifying codes in terms of degree parameters. With Guillem Perarnau.
The Electronic Journal of Combinatorics 19:P32, 2012. [PDF | www | arXiv]
- [C2] On graph identification problems and the special case of identifying vertices using paths. With Matjaž Kovše.
Proceedings of the 23rd International Workshop on Combinatorial Algorithms (IWOCA 2012), Lecture Notes in Computer Science 7643:32-45, 2012. [PDF | www]
The full version appeared in the journal Journal of Discrete Algorithms in 2013.
2011
- [J1] Extremal graphs for the identifying code problem. With Eleonora Guerrini, Matjaž Kovše, Reza Naserasr, Aline Parreau and Petru Valicov.
European Journal of Combinatorics 32(4):628-638, 2011. [PDF | www | arXiv]
- [C1] Edge identifying codes. With Sylvain Gravier, Reza Naserasr, Aline Parreau and Petru Valicov.
Proceedings of the 6th European Conference on Combinatorics, Graph Theory and Applications (EUROCOMB 2011), Electronic Notes in Discrete Mathematics 38:343-348, 2011. [PDF | www]
The full version appeared in the journal Journal of Graph Theory in 2013.
Other material
- IWOCA 2020 in Bordeaux (Oops! On-line!). With Leszek A. Gąsieniec, Ralf Klasing, Tomasz Radzik and William F. Smyth. [PDF]
Bulletin of the EATCS 132:73-76, 2020. [www]
IFIP News, September 2020, pp. 9-10. [PDF]
IFORS News, September 2020, pp. 24-25. [PDF]
- Complexity of MULTIPACKING in graphs.
IWOCA Open Problem, 2020. [www]
- On powers of interval graphs and their orders. With Reza Naserasr, Aline Parreau and Petru Valicov.
Manuscript, 2015. [arXiv]
- The complexity of covering a ladder using cycles.
IWOCA Open Problem, 2012. [www]
- Locally identifying colouring planar graphs of small maximum degree and girth 5 with four colours is NP-hard. With Aline Parreau and Petru Valicov.
Manuscript, 2011. [PDF]