Publications of Nicolas Nisse
BACK TO COATI PUBLICATION INDEX
Publications of Nicolas Nisse
-
Fedor V. Fomin,
Pierre Fraigniaud,
Nicolas Nisse,
and Dimitrios M. Thilikos.
Forewords: Special issue on Theory and Applications of Graph Searching Problems,
volume 655:1 of Theoretical Computer Science - Special Issue on Theory and Applications of Graph Searching Problems.
December 2016.
[WWW
] [bibtex-entry]
-
Fedor Fomin,
Pierre Fraigniaud,
Nicolas Nisse,
and Dimitrios M. M. Thilikos.
Report on GRASTA 2014.
2014.
[WWW
] [PDF
] [bibtex-entry]
-
Roberto Baldoni,
N. Nisse,
and Maarten van Steen, editors.
Proceedings of the 17th International Conference on Principles of Distributed Systems (OPODIS),
volume 8304 of Lecture Notes in Computer Science,
December 2013.
Springer.
[WWW
] [bibtex-entry]
-
Yann Busnel,
N. Nisse,
and Franck Rousseau, editors.
Actes des 15es Rencontres Francophones sur les aspects Algorithmiques des Télécommunications (AlgoTel),
May 2013.
Univ. Nantes.
[WWW
] [bibtex-entry]
-
Nicolas Nisse.
Algorithmic complexity: Between Structure and Knowledge How Pursuit-evasion Games help..
Habilitation à diriger des recherches,
Université Nice Sophia Antipolis,
May 2014.
[WWW
] [PDF
]
Keywords:
Algorithm,
Graph Theory,
Pursuit-Evasion Games,
Cops and Robber,
Graph Searching,
Graph decompositions,
Graph Structural Properties,
Mobile Agents Computing,
Telecommunication Networks,
Routing,
Distributed Computing,
Algorithmes,
Th eorie des Graphes,
Jeux de Poursuite- Evasion,
Gendarmes et voleur,
Encerclement dans les graphes,
D ecompositions de graphes,
Propri et es structurelles de graphes,
Agents Mobiles,
R eseaux de t el ecommunication,
Routage,
Calcul distribu é.
[bibtex-entry]
-
Julien Bensmail,
Foivos Fioravantes,
Fionn Mc Inerney,
and Nicolas Nisse.
Further Results on an Equitable 1-2-3 Conjecture.
Discrete Applied Mathematics,
297:1-20,
2021.
[WWW
] [PDF
]
Keywords:
Proper labellings,
Equitable labellings,
1-2-3 Conjecture.
[bibtex-entry]
-
Julien Bensmail,
Foivos Fioravantes,
and Nicolas Nisse.
On Proper Labellings of Graphs with Minimum Label Sum.
Algorithmica,
2021.
[WWW
] [PDF
] [bibtex-entry]
-
Julien Bensmail,
Bi Li,
Binlong Li,
and Nicolas Nisse.
On Minimizing the Maximum Color for the 1-2-3 Conjecture.
Discrete Applied Mathematics,
289:32-51,
2021.
[WWW
] [PDF
]
Keywords:
proper vertex-colorings,
edge labelings,
1-2-3 Conjecture,
small vertex colors.
[bibtex-entry]
-
Jean-Claude Bermond,
Frédéric Giroire,
and Nicolas Nisse.
Graphes et Télécommunications.
Bibliothèque Tangente,
(Hors Serie 75):120-125,
2021.
[WWW
] [PDF
] [bibtex-entry]
-
Fionn Mc Inerney,
Nicolas Nisse,
and Stéphane Pérennes.
Eternal Domination: D-Dimensional Cartesian and Strong Grids and Everything in Between.
Algorithmica,
83(5):1459-1492,
2021.
[WWW
] [PDF
]
Keywords:
King's graph,
Strong grid,
Cartesian grid,
Grids,
Graphs,
Eternal Domination,
Combinatorial Games.
[bibtex-entry]
-
Julien Bensmail,
François Dross,
and Nicolas Nisse.
Decomposing degenerate graphs into locally irregular subgraphs.
Graphs and Combinatorics,
36(6):1869--1889,
2020.
[WWW
] [PDF
]
Keywords:
planar graphs,
k-trees,
locally irregular decompositions,
degenerate graphs,
cacti.
[bibtex-entry]
-
Julien Bensmail,
Dorian Mazauric,
Fionn Mc Inerney,
Nicolas Nisse,
and Stéphane Pérennes.
Sequential Metric Dimension.
Algorithmica,
82(10):2867-2901,
2020.
[WWW
] [PDF
]
Keywords:
Complexity,
Metric dimension,
Games in graphs.
[bibtex-entry]
-
Julien Bensmail,
Fionn Mc Inerney,
and Nicolas Nisse.
Metric Dimension: from Graphs to Oriented Graphs.
Discrete Applied Mathematics,
2020.
[WWW
] [PDF
]
Keywords:
Strongly-connected orientations,
Metric dimension,
Resolving sets.
[bibtex-entry]
-
Nathann Cohen,
Fionn Mc Inerney,
Nicolas Nisse,
and Stéphane Pérennes.
Study of a Combinatorial Game in Graphs Through Linear Programming.
Algorithmica,
82(2):212-244,
2020.
[WWW
] [PDF
]
Keywords:
Grid,
Tree,
Linear Programming,
Domination,
Graphs,
Spy game,
Cops and Robber games.
[bibtex-entry]
-
Guillaume Ducoffe,
Sylvain Legay,
and Nicolas Nisse.
On the Complexity of Computing Treebreadth.
Algorithmica,
82(6):1574-1600,
2020.
[WWW
] [PDF
] [bibtex-entry]
-
Fionn Mc Inerney,
Nicolas Nisse,
and Stéphane Pérennes.
Eternal Domination: D-Dimensional Cartesian and Strong Grids and Everything in Between.
Algorithmica,
2020.
[WWW
] [PDF
]
Keywords:
King's graph,
Strong grid,
Cartesian grid,
Grids,
Graphs,
Eternal Domination,
Combinatorial Games.
[bibtex-entry]
-
Spyros Angelopoulos,
Nicolas Nisse,
and Dimitrios M. Thilikos.
Preface to special issue on Theory and Applications of Graph Searching.
Theoretical Computer Science,
794:1-2,
November 2019.
[WWW
] [PDF
] [bibtex-entry]
-
Frédéric Havet and Nicolas Nisse.
Constrained ear decompositions in graphs and digraphs.
Discrete Mathematics and Theoretical Computer Science,
vol. 21 no. 4,
September 2019.
[WWW
] [PDF
] [bibtex-entry]
-
Kolja Knauer and Nicolas Nisse.
Computing metric hulls in graphs.
Discrete Mathematics and Theoretical Computer Science,
vol. 21 no. 1, ICGT 2018,
May 2019.
[WWW
] [PDF
] [bibtex-entry]
-
Nicolas Nisse.
Network Decontamination.
In Distributed Computing by Mobile Entities,
volume 11340 of LNCS,
pages 516-548.
Springer,
2019.
[WWW
] [PDF
]
Keywords:
Computational Complexity,
(Distributed) Graph Algorithms,
Graph Searching,
Path-and Tree-Decompositions.
[bibtex-entry]
-
Julio Araujo,
Guillaume Ducoffe,
Nicolas Nisse,
and Karol Suchan.
On interval number in cycle convexity.
Discrete Mathematics and Theoretical Computer Science,
Vol. 20 no. 1(1):1-28,
May 2018.
[WWW
] [PDF
]
Keywords:
convexity,
domination problems in graphs,
interval number,
graph convexity,
complexity,
complexity and algorithms,
dominating set,
graph.
[bibtex-entry]
-
Julien Bensmail,
Valentin Garnero,
and Nicolas Nisse.
On improving matchings in trees, via bounded-length augmentations.
Discrete Applied Mathematics,
250(11):110-129,
2018.
[WWW
] [PDF
]
Keywords:
trees,
maximum matchings,
bounded-length augmentations.
[bibtex-entry]
-
Bartlomiej Bosek,
Przemyslaw Gordinowicz,
Jaroslaw Grytczuk,
Nicolas Nisse,
Joanna Sokol,
and Malgorzata Sleszynska-Nowak.
Centroidal Localization Game.
The Electronic Journal of Combinatorics,
2018.
[WWW
] [PDF
] [bibtex-entry]
-
Bartlomiej Bosek,
Przemyslaw Gordinowicz,
Jaroslaw Grytczuk,
Nicolas Nisse,
Joanna Sokol,
and Malgorzata Sleszynska-Nowak.
Localization game on geometric and planar graphs.
Discrete Applied Mathematics,
2018.
[WWW
] [PDF
] [bibtex-entry]
-
Nathann Cohen,
Frédéric Havet,
William Lochet,
and Nicolas Nisse.
Subdivisions of oriented cycles in digraphs with large chromatic number.
Journal of Graph Theory,
89(4):439-456,
April 2018.
[WWW
] [PDF
] [bibtex-entry]
-
Nathann Cohen,
Nicolas Martins,
Fionn Mc Inerney,
Nicolas Nisse,
Stéphane Pérennes,
and Rudini Sampaio.
Spy-game on graphs: Complexity and simple topologies.
Theoretical Computer Science,
725:1 - 15,
May 2018.
[WWW
] [PDF
]
Keywords:
Graphs,
Cops and Robber games,
PSPACE-hard.
[bibtex-entry]
-
Nathann Cohen,
Fionn Mc Inerney,
Nicolas Nisse,
and Stéphane Pérennes.
Study of a Combinatorial Game in Graphs Through Linear Programming.
Algorithmica,
August 2018.
[WWW
] [PDF
]
Keywords:
Domination,
Graphs,
Spy game,
Cops and Robber games,
Linear Programming,
Tree,
Grid.
[bibtex-entry]
-
David Coudert,
Guillaume Ducoffe,
Nicolas Nisse,
and Mauricio Soto.
On distance-preserving elimination orderings in graphs: Complexity and algorithms.
Discrete Applied Mathematics,
243:140-153,
March 2018.
[WWW
] [PDF
]
Keywords:
bounded treewidth,
integer linear programming,
Keyword: distance-preserving elimination ordering,
metric graph theory,
NP-complete,
exact exponential algorithm.
[bibtex-entry]
-
Lélia Blin,
Janna Burman,
and Nicolas Nisse.
Exclusive Graph Searching.
Algorithmica,
77(3):942-969,
2017.
[WWW
] [PDF
] [bibtex-entry]
-
Gianlorenzo D 'angelo,
Alfredo Navarra,
and Nicolas Nisse.
A unified approach for Gathering and Exclusive Searching on rings under weak assumptions.
Distributed Computing,
30(1):17-48,
2017.
[WWW
] [PDF
] [bibtex-entry]
-
Frédéric Giroire,
Remigiusz Modrzejewski,
Nicolas Nisse,
and Stéphane Pérennes.
Maintaining Balanced Trees for Structured Distributed Streaming Systems.
Discrete Applied Mathematics,
232:176 - 188,
December 2017.
[WWW
] [PDF
]
Keywords:
Peer-to-peer,
Distributed Live Streaming System,
Graph Algorithm,
Balanced Trees.
[bibtex-entry]
-
Bi Li,
Fatima Zahra Moataz,
Nicolas Nisse,
and Karol Suchan.
Minimum Size Tree-Decompositions.
Discrete Applied Mathematics,
February 2017.
[WWW
] [PDF
] [bibtex-entry]
-
Euripides Markou,
Nicolas Nisse,
and Stéphane Pérennes.
Exclusive graph searching vs. pathwidth.
Information and Computation,
252:243 - 260,
2017.
[WWW
] [PDF
]
Keywords:
graph searching,
pathwidth.
[bibtex-entry]
-
Sahel Sahhaf,
Wouter Tavernier,
Dimitri Papadimitriou,
Davide Careglio,
Alok Kumar,
Christian Glacet,
David Coudert,
Nicolas Nisse,
Lluis Fàbrega,
Pere Vilà,
Miguel Camelo,
Pieter Audenaert,
Didier Colle,
and Piet Demeester.
Routing at Large Scale: Advances and Challenges for Complex Networks.
IEEE Network,
pp 12 - 22,
2017.
[WWW
] [PDF
]
Keywords:
Complex networks,
Geometric routing,
Compact routing,
Algebraic routing,
Path-vector routing.
[bibtex-entry]
-
David Coudert,
Guillaume Ducoffe,
and Nicolas Nisse.
To Approximate Treewidth, Use Treelength!.
Siam Journal on Discrete Mathematics,
30(3):13,
2016.
[WWW
] [PDF
]
Keywords:
Graph,
Treewidth,
Treelength,
Cycle basis,
Genus.
[bibtex-entry]
-
David Coudert,
Dorian Mazauric,
and Nicolas Nisse.
Experimental Evaluation of a Branch and Bound Algorithm for Computing Pathwidth and Directed Pathwidth.
ACM Journal of Experimental Algorithmics,
21(1):23,
2016.
[WWW
] [PDF
] [bibtex-entry]
-
Nicolas Nisse and Ronan Pardo Soares.
On the Monotonicity of Process Number.
Discrete Applied Mathematics,
210:103-111,
2016.
[WWW
] [PDF
]
Keywords:
Graph Searching,
Process Number,
Monotonicity.
[bibtex-entry]
-
Omid Amini,
David Coudert,
and Nicolas Nisse.
Non-deterministic graph searching in trees.
Journal of Theoretical Computer Science (TCS),
580:101-121,
May 2015.
[WWW
] [PDF
]
Keywords:
Pathwidth,
Trees,
Graph Searching,
Treewidth.
[Abstract] [bibtex-entry]
-
Florent Becker,
Adrian Kosowski,
Martin Matamala,
Nicolas Nisse,
Ivan Rapaport,
Karol Suchan,
and Ioan Todinca.
Allowing each node to communicate only once in a distributed system: shared whiteboard models.
Distributed Computing,
28(3):189-200,
2015.
[WWW
] [PDF
] [Abstract] [bibtex-entry]
-
Jean-Claude Bermond,
Bi Li,
Nicolas Nisse,
Hervé Rivano,
and Min-Li Yu.
Data gathering and personalized broadcasting in radio grids with interference.
Journal of Theoretical Computer Science (TCS),
562:453-475,
2015.
[WWW
] [PDF
]
Keywords:
Gathering,
Personalized broadcasting,
Interference,
Grid,
Radio networks.
[Abstract] [bibtex-entry]
-
Gianlorenzo d'Angelo,
Gabriele Di Stefano,
Alfredo Navarra,
Nicolas Nisse,
and Karol Suchan.
Computing on rings by oblivious robots: a unified approach for different tasks.
Algorithmica,
72(4):1055-1096,
2015.
[WWW
] [PDF
] [Abstract] [bibtex-entry]
-
Frédéric Giroire,
Ioannis Lamprou,
Dorian Mazauric,
Nicolas Nisse,
Stéphane Pérennes,
and Ronan Soares.
Connected Surveillance Game.
Journal of Theoretical Computer Science (TCS),
584:131-143,
June 2015.
[WWW
] [PDF
]
Keywords:
Surveillance game,
Cops and robber games,
Prefetching,
Online strategy,
Competitive ratio,
Cost of connectivity.
[Abstract] [bibtex-entry]
-
Adrian Kosowski,
Bi Li,
Nicolas Nisse,
and Karol Suchan.
k-Chordal Graphs: from Cops and Robber to Compact Routing via Treewidth.
Algorithmica,
72(3):758-777,
2015.
[WWW
] [PDF
] [Abstract] [bibtex-entry]
-
Julio Araujo,
Nicolas Nisse,
and Stéphane Pérennes.
Weighted Coloring in Trees.
Siam Journal on Discrete Mathematics,
28(4):2029 - 2041,
2014.
[WWW
] [PDF
] [bibtex-entry]
-
Fedor V. Fomin,
Frédéric Giroire,
Alain Jean-Marie,
Dorian Mazauric,
and Nicolas Nisse.
To satisfy impatient Web surfers is hard.
Journal of Theoretical Computer Science (TCS),
526:1-17,
March 2014.
[WWW
] [PDF
] [bibtex-entry]
-
J. Araujo,
V. Campos,
F. Giroire,
N. Nisse,
L. Sampaio,
and R Soares.
On the hull number of some graph classes.
Theoretical Computer Science,
475:1-12,
January 2013.
[WWW
] [PDF
] [bibtex-entry]
-
L. Barrière,
P. Flocchini,
F. Fomin,
P. Fraigniaud,
N. Nisse,
N. Santoro,
and D. Thilikos.
Connected Graph Searching.
Information and Computation,
219:1-16,
2012.
[WWW
] [PDF
] [Abstract] [bibtex-entry]
-
N. Nisse,
I. Rapaport,
and K. Suchan.
Distributed computing of efficient routing schemes in generalized chordal graphs.
Theoretical Computer Science,
444(27):17-27,
2012.
[WWW
] [PDF
] [Abstract] [bibtex-entry]
-
J. Chalopin,
V. Chepoi,
N. Nisse,
and Y. Vaxès.
Cop and robber games when the robber can hide and ride.
SIAM Journal of Discrete Maths.,
25(1):333-359,
2011.
[WWW
] [PDF
] [Abstract] [bibtex-entry]
-
N. Cohen,
D. Coudert,
D. Mazauric,
N. Nepomuceno,
and N. Nisse.
Tradeoffs in process strategy games with application in the WDM reconfiguration problem.
Theoretical Computer Science (TCS),
412(35):4675-4687,
August 2011.
[WWW
] [PDF
] [Abstract] [bibtex-entry]
-
F. V. Fomin,
P. A. Golovach,
J. Kratochvil,
N. Nisse,
and K. Suchan.
Pursuing a fast robber on a graph.
Theoretical Computer Science,
411(7-9):1167-1181,
2010.
[WWW
] [PDF
] [Abstract] [bibtex-entry]
-
O. Amini,
F. Mazoit,
N. Nisse,
and S. Thomassé.
Submodular partition functions.
Discrete Mathematics,
309(20):6000-6008,
2009.
[WWW
] [PDF
] [Abstract] [bibtex-entry]
-
F. V. Fomin,
P. Fraigniaud,
and N. Nisse.
Nondeterministic Graph Searching: From Pathwidth to Treewidth.
Algorithmica,
53(3):358-373,
2009.
[WWW
] [PDF
] [Abstract] [bibtex-entry]
-
D. Ilcinkas,
N. Nisse,
and D. Soguet.
The Cost of Monotonicity in Distributed Graph Searching.
Distributed Computing,
22(2):117-127,
2009.
[WWW
] [PDF
] [Abstract] [bibtex-entry]
-
N. Nisse and D. Soguet.
Graph Searching with Advice.
Theoretical Computer Science,
410(14):1307-1318,
2009.
[WWW
] [PDF
] [Abstract] [bibtex-entry]
-
N. Nisse.
Connected graph searching in chordal graphs.
Discrete Applied Mathematics,
157(12):2603-2610,
2009.
[WWW
] [PDF
] [Abstract] [bibtex-entry]
-
L. Blin,
P. Fraigniaud,
N. Nisse,
and S. Vial.
Distributed chasing of network intruders.
Theoretical Computer Science,
399(1-2):12-37,
2008.
[WWW
] [PDF
] [Abstract] [bibtex-entry]
-
P. Fraigniaud and N. Nisse.
Monotony Properties of Connected Visible Graph Searching.
Information and Computation,
206(12):1383-1393,
2008.
[Abstract] [bibtex-entry]
-
F. Mazoit and N. Nisse.
Monotonicity of non-deterministic graph searching.
Theoretical Computer Science,
399(3):169-178,
2008.
[WWW
] [PDF
] [Abstract] [bibtex-entry]
-
Ali Al Zoobi,
David Coudert,
and Nicolas Nisse.
De la difficulté de trouver des chemins dissimilaires.
In ALGOTEL 2021 - 23èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications,
La Rochelle, France,
September 2021.
[WWW
] [PDF
]
Keywords:
Similarité entre chemins,
$k$ plus courts chemins simples.
[bibtex-entry]
-
Julien Bensmail,
Foivos Fioravantes,
Fionn Mc Inerney,
and Nicolas Nisse.
Connexions ! Le jeu du plus grand sous-graphe connexe.
In ALGOTEL 2021 - 23èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications,
La Rochelle, France,
September 2021.
[WWW
] [PDF
]
Keywords:
Games on graphs,
Scoring games,
Connection games,
PSPACE-complete,
Jeux à deux joueurs dans les graphes,
Jeux de connexion,
Jeux à score.
[bibtex-entry]
-
Julien Bensmail,
Foivos Fioravantes,
Fionn Mc Inerney,
and Nicolas Nisse.
The Largest Connected Subgraph Game.
In WG 2021 - The 47th International Workshop on Graph-Theoretic Concepts in Computer Science,
volume 12911 of Lecture Notes in Computer Science,
Warsaw, Poland,
pages 296-307,
June 2021.
Springer.
[WWW
] [PDF
]
Keywords:
Games on graphs,
Scoring games,
Connection games,
PSPACE-complete.
[bibtex-entry]
-
Thomas Dissaux,
Guillaume Ducoffe,
Nicolas Nisse,
and Simon Nivelle.
Treelength of Series-parallel graphs.
In LAGOS 2021 - XI Latin and American Algorithms, Graphs and Optimization Symposium,
São Paulo / Virtual, Brazil,
May 2021.
[WWW
] [PDF
] [bibtex-entry]
-
Thomas Dissaux,
Guillaume Ducoffe,
Nicolas Nisse,
and Simon Nivelle.
Longueur Arborescente des Graphes Série-Parallèles.
In ALGOTEL 2021 - 23èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications,
La Rochelle, France,
September 2021.
[WWW
] [PDF
]
Keywords:
décomposition arborescente,
longueur arborescente,
graphes série-parallèles,
sous-graphes isométriques.
[bibtex-entry]
-
Ali Al Zoobi,
David Coudert,
and Nicolas Nisse.
Compromis espace-temps pour le problème de k plus courts chemins simples.
In ALGOTEL 2020 -- 22èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications,
Lyon, France,
pages 4,
September 2020.
[WWW
] [PDF
]
Keywords:
k plus courts chemins simples,
algorithmes de graphes,
compromis complexité espace-temps.
[bibtex-entry]
-
Ali Al Zoobi,
David Coudert,
and Nicolas Nisse.
Space and Time Trade-Off for the k Shortest Simple Paths Problem.
In SEA 2020 - 18th International Symposium on Experimental Algorithms,
volume 160 of Leibniz International Proceedings in Informatics (LIPIcs),
Catania, Italy,
pages 13,
June 2020.
Schloss Dagstuhl--Leibniz-Zentrum f'ur Informatik.
[WWW
] [PDF
]
Keywords:
k shortest simple paths,
graph algorithm,
space-time trade-off.
[bibtex-entry]
-
Julien Bensmail,
Foivos Fioravantes,
and Nicolas Nisse.
On Proper Labellings of Graphs with Minimum Label Sum.
In IWOCA 2020 - 31st International Workshop on Combinatorial Algorithms,
Bordeaux, France,
June 2020.
[WWW
] [PDF
] [bibtex-entry]
-
Julien Bensmail,
Fionn Mc Inerney,
and Nicolas Nisse.
Dimension Métrique des Graphes Orientés.
In AlgoTel 2019 - 21èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications,
Saint Laurent de la Cabrerisse, France,
June 2019.
[WWW
] [PDF
]
Keywords:
Graphes,
Dimension Métrique,
Ensembles Resolvants,
Orientations fortement connexes.
[bibtex-entry]
-
Julien Bensmail,
Fionn Mc Inerney,
and Nicolas Nisse.
Metric Dimension: from Graphs to Oriented Graphs.
In LAGOS 2019 - 10th Latin & American Algorithms, Graphs and Optimization Symposium,
volume 346 of Electronic Notes in Theoretical Computer Science,
Belo Horizonte, Brazil,
pages 111-123,
June 2019.
[WWW
] [PDF
]
Keywords:
Strongly-connected orientations,
Resolving sets,
Metric dimension.
[bibtex-entry]
-
Fionn Mc Inerney,
Nicolas Nisse,
and Stéphane Pérennes.
Eternal Domination in Grids.
In CIAC 2019 - 11th International Conference on Algorithms and Complexity,
volume 11485 of Algorithms and Complexity. Lecture Notes in Computer Science,
Rome, Italy,
pages 311-322,
May 2019.
[WWW
] [PDF
]
Keywords:
Grids,
Combinatorial Games,
Graphs,
Eternal Domination.
[bibtex-entry]
-
Julien Bensmail,
Dorian Mazauric,
Fionn Mc Inerney,
Nicolas Nisse,
and Stéphane Pérennes.
Sequential Metric Dimension.
In 16th Workshop on Approximation and Online Algorithms (WAOA 2018),
Helsinki, Finland,
August 2018.
[WWW
] [PDF
]
Keywords:
metric dimension,
Games in graphs,
complexity.
[bibtex-entry]
-
Julien Bensmail,
Dorian Mazauric,
Fionn Mc Inerney,
Nicolas Nisse,
and Stéphane Pérennes.
Localiser une cible dans un graphe.
In ALGOTEL 2018 - 20èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications,
Roscoff, France,
May 2018.
[WWW
] [PDF
]
Keywords:
Mots-clefs : Graphes,
Dimension Métrique,
Dimension Centro¨idaleCentro¨idale,
Jeux dans les graphes.
[bibtex-entry]
-
Julien Bensmail,
Valentin Garnero,
Nicolas Nisse,
Alexandre Salch,
and Valentin Weber.
Recovery of disrupted airline operations using k-Maximum Matching in graphs.
In IX Latin and American Algorithms, Graphs and Optimization Symposium (LAGOS),
volume 62 of Electronic Notes in Discrete Mathematics (IX Latin and American Algorithms, Graphs and Optimization Symposium (LAGOS)),
Marseille, France,
pages 3-8,
September 2017.
[WWW
] [PDF
]
Keywords:
Graph,
Matching,
Augmenting paths,
Complexity,
Trees.
[bibtex-entry]
-
Nathann Cohen,
Nìcolas A Martins,
Fionn Mc Inerney,
Nicolas Nisse,
Stéphane Pérennes,
and Rudini Sampaio.
Enquêter dans les graphes.
In ALGOTEL 2017 - 19èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications,
Quiberon, France,
May 2017.
[WWW
] [PDF
]
Keywords:
Jeu de Gendarmes et Voleur,
Programmation Linéaire,
Mots-clefs : Jeux combinatoires à deux joueurs dans les graphes.
[bibtex-entry]
-
Nathann Cohen,
Fionn Mc Inerney,
Nicolas Nisse,
and Stéphane Pérennes.
Study of a combinatorial game in graphs through Linear Programming.
In 28th International Symposium on Algorithms and Computation (ISAAC 2017),
Phuket, Thailand,
2017.
[WWW
] [PDF
]
Keywords:
Turn-by-turn games in graphs,
Graph algorithms,
Linear Programming.
[bibtex-entry]
-
Nathann Cohen,
Frédéric Havet,
William Lochet,
and Nicolas Nisse.
Subdivisions of oriented cycles in digraphs with large chromatic number.
In Bordeaux Graph Wokshop 2016,
Bordeaux, France,
pages 85-88,
November 2016.
[WWW
] [PDF
] [bibtex-entry]
-
Nathann Cohen,
Mathieu Hilaire,
Nicolas Martins,
Nicolas Nisse,
and Stéphane Pérennes.
Spy-Game on graphs.
In Erik D. Demaine and Fabrizio Grandoni, editors,
8th International Conference on Fun with Algorithms, FUN 2016,
volume 49 of Leibniz International Proceedings in Informatics (LIPIcs),
La Maddalena, Maddalena Islands, Italy,
2016.
Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik.
[WWW
] [PDF
] [bibtex-entry]
-
Guillaume Ducoffe,
Sylvain Legay,
and Nicolas Nisse.
On the Complexity of Computing Treebreadth.
In Veli Mäkinen,
Simon J. Puglisi,
and Leena Salmela, editors,
27th International Workshop on Combinatorial Algorithms, IWOCA 2016,
number 9843 of Combinatorial Algorithms,
Helsinki, Finland,
pages 3-15,
August 2016.
Springer International Publishing.
[WWW
] [PDF
] [bibtex-entry]
-
David Coudert,
Guillaume Ducoffe,
and Nicolas Nisse.
Structure vs métrique dans les graphes.
In ALGOTEL 2015 - 17èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications,
Beaune, France,
June 2015.
[WWW
] [PDF
]
Keywords:
Genre,
Hyperbolicité,
Graphe,
Largeur arborescente (Treewidth),
Longueur arborescente (Treelength).
[Abstract] [bibtex-entry]
-
Mamadou Moustapha Kanté,
Fatima Zahra Moataz,
Benjamin Momège,
and Nicolas Nisse.
Finding Paths in Grids with Forbidden Transitions.
In WG 2015, 41st International Workshop on Graph-Theoretic Concepts in Computer Science,
Munich, Germany,
June 2015.
[WWW
] [PDF
] [Abstract] [bibtex-entry]
-
Mamadou Moustapha Kanté,
Fatima Zahra Moataz,
Benjamin Momège,
and Nicolas Nisse.
On paths in grids with forbidden transitions.
In ALGOTEL 2015 - 17èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications,
Beaune, France,
June 2015.
[WWW
] [PDF
]
Keywords:
Forbidden transitions,
planar graph,
grid,
asymmetric nodes.
[Abstract] [bibtex-entry]
-
Bi Li,
Fatima Zahra Moataz,
Nicolas Nisse,
and Karol Suchan.
Minimum Size Tree-decompositions.
In LAGOS 2015 -- VIII Latin-American Algorithms, Graphs and Optimization Symposium,
Beberibe, Ceará, Brazil,
May 2015.
[WWW
] [PDF
]
Keywords:
Minimum size tree-decomposition,
treewidth,
NP-hard.
[Abstract] [bibtex-entry]
-
Nicolas Nisse,
Alexandre Salch,
and Valentin Weber.
Comment appliquer les chaînes augmentantes pour atterrir a l'heure ?.
In ALGOTEL 2015 - 17èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications,
Beaune, France,
June 2015.
[WWW
] [PDF
] [Abstract] [bibtex-entry]
-
Julio Araújo,
Nicolas Nisse,
and Stéphane Pérennes.
Weighted Coloring in Trees.
In 31st Symposium on Theoretical Aspects of Computer Science (STACS),
Lyon, France,
pages 75-86,
March 2014.
Dagstuhl Publishing.
[WWW
] [PDF
] [bibtex-entry]
-
David Coudert,
Dorian Mazauric,
and Nicolas Nisse.
Experimental Evaluation of a Branch and Bound Algorithm for computing Pathwidth.
In 13th International Symposium on Experimental Algorithms,
volume 8504 of Lecture Notes in Computer Science,
Copenhagen, Denmark,
pages 46-58,
2014.
[WWW
] [PDF
] [bibtex-entry]
-
Gianlorenzo D'Angelo,
Xavier Défago,
and Nicolas Nisse.
Understanding the Power of Stigmergy of Anonymous Agents in Discrete Environments.
In Second International Symposium on Computing and Networking (CANDAR),
Mt. Fuji, Shizuoka, Japan,
December 2014.
[WWW
] [PDF
] [bibtex-entry]
-
Gianlorenzo D'Angelo,
Alfredo Navarra,
and Nicolas Nisse.
Gathering and Exclusive Searching on Rings under Minimal Assumptions.
In Mainak Chatterjee,
Jian-Nong Cao,
Kishore Kothapalli,
and Sergio Rajsbaum, editors,
15th International Conference on Distributed Computing and Networking (ICDCN),
volume 8314,
Coimbatore, India,
pages 149-164,
January 2014.
Springer.
[WWW
] [PDF
] [bibtex-entry]
-
Bi Li,
Fatima Zahra Moataz,
and Nicolas Nisse.
Minimum Size Tree-Decompositions.
In 9th International colloquium on graph theory and combinatorics (ICGT),
Grenoble, France,
2014.
[WWW
] [PDF
] [bibtex-entry]
-
L. Blin,
J. Burman,
and N. Nisse.
Exclusive Graph Searching.
In 21st European Symposium on Algorithms (ESA 2013),
volume LNCS 8125 of Lecture Notes in Computer Science / ARCoSS,
Sophia Antipolis, France,
pages 181-192,
2013.
Springer.
[WWW
] [PDF
] [bibtex-entry]
-
G. D'Angelo,
G. Di Stefano,
A. Navarra,
N. Nisse,
and K. Suchan.
A unified approach for different tasks on rings in robot-based computing systems.
In 15th Workshop on Advances in Parallel and Distributed Computational Models (IPDPS Workshop),
Boston, United States,
pages 667-676,
2013.
[WWW
] [PDF
] [bibtex-entry]
-
F. Giroire,
D. Mazauric,
N. Nisse,
S. Pérennes,
and R. Soares.
Connected Surveillance Game.
In 20th Colloquium on Structural Information and Communication Complexity (SIROCCO),
volume LNCS 8179 of Lecture Notes in Computer Science (LNCS),
Ischia, Italy,
pages pages 68-79,
2013.
Springer.
[WWW
] [PDF
] [bibtex-entry]
-
F. Giroire,
R. Modrzejewski,
N. Nisse,
and S. Pérennes.
Maintaining Balanced Trees For Structured Distributed Streaming Systems.
In 20th Colloquium on Structural Information and Communication Complexity (SIROCCO),
volume LNCS 8179,
Ischia, Italy,
pages pages 177-188,
2013.
[WWW
] [PDF
] [bibtex-entry]
-
N. Nisse.
Fractional Combinatorial Two-Player Games.
In 26th European Conference on Operational Research (EURO XXVI),
Italy,
2013.
[WWW
] [bibtex-entry]
-
N. Nisse and R. Soares.
On the Monotonicity of Process Number.
In 7th Latin-American Algorithms, Graphs and Optimization Symposium (LAGOS),
volume 44,
Mexico, Mexico,
pages 141-147,
2013.
Elsevier.
[WWW
] [PDF
] [bibtex-entry]
-
F. Becker,
A. Kosowski,
N. Nisse,
I. Rapaport,
and K. Suchan.
Interconnection network with a shared whiteboard: Impact of (a)synchronicity on computing power.
In 24th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA),
pages 11-17,
2012.
ACM.
[WWW
] [PDF
] [Abstract] [bibtex-entry]
-
L. Blin,
J. Burman,
and N. Nisse.
Nettoyage perpétuel de réseaux.
In 14es Rencontres Francophones sur les Aspects Algorithmiques de Télécommunications (AlgoTel),
pages 31-34,
2012.
[WWW
] [PDF
] [Abstract] [bibtex-entry]
-
L. Blin,
J. Burman,
and N. Nisse.
Brief Announcement: Distributed Exclusive and Perpetual Tree Searching.
In 26th International Symposium on Distributed Computing (DISC),
volume 7611,
pages 403-404,
2012.
Springer, LNCS.
[WWW
] [PDF
] [Abstract] [bibtex-entry]
-
F. V. Fomin,
F. Giroire,
A. Jean-Marie,
D. Mazauric,
and N. Nisse.
Satisfaire un internaute impatient est difficile.
In 14es Rencontres Francophones sur les Aspects Algorithmiques de Télécommunications (AlgoTel),
pages 79-82,
2012.
Note: Best paper.
[WWW
] [PDF
] [Abstract] [bibtex-entry]
-
F. V. Fomin,
F. Giroire,
A. Jean-Marie,
D. Mazauric,
and N. Nisse.
To Satisfy Impatient Web surfers is Hard.
In 6th International Conference on FUN with Algorithms (FUN),
volume 7288,
pages 166-176,
2012.
Springer, LNCS.
[WWW
] [PDF
] [Abstract] [bibtex-entry]
-
A. Kosowski,
B. Li,
N. Nisse,
and K. Suchan.
k-Chordal Graphs: from Cops and Robber to Compact Routing via Treewidth.
In 14es Rencontres Francophones sur les Aspects Algorithmiques de Télécommunications (AlgoTel),
pages 83-86,
2012.
[WWW
] [PDF
] [Abstract] [bibtex-entry]
-
A. Kosowski,
B. Li,
N. Nisse,
and K. Suchan.
k-Chordal Graphs: from Cops and Robber to Compact Routing via Treewidth.
In 39th International Colloquium on Automata, Languages and Programming (ICALP, track C),
volume 7392,
pages 610-622,
2012.
Springer, LNCS.
[WWW
] [PDF
] [Abstract] [bibtex-entry]
-
F. Becker,
M. Matamala,
N. Nisse,
I. Rapaport,
K. Suchan,
and I. Todinca.
Adding a referee to an interconnection network: What can(not) be computed in one round.
In 25th IEEE International Parallel & Distributed Processing Symposium (IPDPS),
pages 508-514,
2011.
IEEE.
[WWW
] [PDF
] [Abstract] [bibtex-entry]
-
F. Becker,
M. Matamala,
N. Nisse,
I. Rapaport,
K. Suchan,
and I. Todinca.
Reconstruire un graphe en une ronde.
In Ducourthial,
Bertrand et Felber,
and Pascal, editors,
13es Rencontres Francophones sur les Aspects Algorithmiques de Télécommunications (AlgoTel),
Cap Estérel, France,
2011.
[WWW
] [Abstract] [bibtex-entry]
-
S. Belhareth,
D. Coudert,
D. Mazauric,
N. Nisse,
and I. Tahiri.
Reconfiguration avec contraintes physiques dans les réseaux WDM.
In Ducourthial et Bertrand et Felber et Pascal, editor,
13es Rencontres Francophones sur les Aspects Algorithmiques de Télécommunications (AlgoTel),
Cap Estérel, France,
2011.
[WWW
] [PDF
] [Abstract] [bibtex-entry]
-
C. Caillouet,
F. Huc,
N. Nisse,
S. Pérennes,
and H. Rivano.
Stability of a localized and greedy routing algorithm.
In 12th Workshop on Advances in Parallel and Distributed Computational Models,
pages 8p,
2010.
IEEE.
[WWW
] [PDF
] [Abstract] [bibtex-entry]
-
J. Chalopin,
V. Chepoi,
N. Nisse,
and Y. Vaxes.
Cop and robber games when the robber can hide and ride.
In 8th French Combinatorial Conference,
Orsay,
June 2010.
Note: Selection on abstract.
[Abstract] [bibtex-entry]
-
N. Cohen,
D. Coudert,
D. Mazauric,
N. Nepomuceno,
and N. Nisse.
Tradeoffs in routing reconfiguration problems.
In Maria Gradinariu Potop-Butucaru et Hervé Rivano, editor,
12èmes Rencontres Francophones sur les Aspects Algorithmiques de Télécommunications (AlgoTel),
Belle Dune France,
pages 4p,
2010.
[WWW
] [PDF
] [Abstract] [bibtex-entry]
-
N. Cohen,
D. Coudert,
D. Mazauric,
N. Nepomuceno,
and N. Nisse.
Tradeoffs in process strategy games with application in the WDM reconfiguration problem.
In P. Boldi and L. Gargano, editors,
Fifth International conference on Fun with Algorithms (FUN 2010),
volume 6099 of Lecture Notes in Computer Science,
Ischia Island, Italy,
pages 121-132,
June 2010.
Springer.
Note: Http://hal.inria.fr/inria-00495443.
[WWW
] [PDF
] [Abstract] [bibtex-entry]
-
N. Hanusse,
D. Ilcinkas,
A. Kosowski,
and N. Nisse.
Comment battre la marche aléatoire en comptant ?.
In 12ème Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications (AlgoTel'10),
pages 4p,
2010.
[WWW
] [PDF
] [Abstract] [bibtex-entry]
-
N. Hanusse,
D. Ilcinkas,
A. Kosowski,
and N. Nisse.
Locating a target with an agent guided by unreliable local advice.
In 29th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC'10),
volume XXXX,
pages 10p,
2010.
ACM.
Note: To appear.
[PDF
] [Abstract] [bibtex-entry]
-
N. Nisse.
Graph Searching and Graph Decompositions.
In 24th European Conference on Operational Research (EURO),
Lisbon, Portugal,
pages 1p,
July 2010.
Note: Invited talk.
[WWW
] [Abstract] [bibtex-entry]
-
J-C. Bermond,
N. Nisse,
P. Reyes,
and H. Rivano.
Minimum delay Data Gathering in Radio Networks.
In Proceedings of the 8th international conference on Ad Hoc Networks and Wireless (AdHoc-Now),
volume 5793 of Lecture Notes in Computer Science,
pages 69-82,
2009.
Springer.
[WWW
] [PDF
] [Abstract] [bibtex-entry]
-
J-C. Bermond,
N. Nisse,
P. Reyes,
and H. Rivano.
Fast Data Gathering in Radio Grid Networks.
In 11èmes Rencontres Francophones sur les Aspects Algorithmiques de Télécommunications (AlgoTel'09),
pages 4p,
June 2009.
[WWW
] [PDF
] [Abstract] [bibtex-entry]
-
D. Coudert,
F. Huc,
D. Mazauric,
N. Nisse,
and J-S. Sereni.
Reconfiguration dans les réseaux optiques.
In A. Chaintreau and C. Magnien, editors,
11ème Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications (AlgoTel'09),
Carry le Rouet,
pages 4p,
June 2009.
[WWW
] [PDF
] [Abstract] [bibtex-entry]
-
D. Coudert,
F. Huc,
D. Mazauric,
N. Nisse,
and J-S. Sereni.
Reconfiguration of the Routing in WDM Networks with Two Classes of Services.
In 13th Conference on Optical Network Design and Modeling (ONDM),
Braunschweig, Germany,
pages 6p,
February 2009.
IEEE.
[WWW
] [Abstract] [bibtex-entry]
-
D. Coudert,
D. Mazauric,
and N. Nisse.
On Rerouting Connection Requests in Networks with Shared Bandwidth.
In DIMAP workshop on Algorithmic Graph Theory (AGT09),
volume 32 of Electronic Notes in Discrete Mathematics,
Warwick, UK,
pages 109-116,
March 2009.
Elsevier.
[WWW
] [PDF
] [Abstract] [bibtex-entry]
-
N. Nisse,
I. Rapaport,
and K. Suchan.
Distributed computing of efficient routing schemes in generalized chordal graphs.
In Proceedings of the 16th International Colloquium on Structural Information and Communication Complexity (SIROCCO),
volume 5869 of Lecture Notes in Computer Science,
Piran, Slovenia,
pages 252-265,
2009.
Springer-Verlag.
[PDF
] [Abstract] [bibtex-entry]
-
D. Ilcinkas,
N. Nisse,
and D. Soguet.
Le cout de la monotonie dans les stratégies d'encerclement réparti.
In 10èmes Rencontres Francophones sur les Aspects Algorithmiques de Télécommunications (AlgoTel'08),
pages 4p,
2008.
[WWW
] [PDF
] [Abstract] [bibtex-entry]
-
N. Nisse and K. Suchan.
Fast Robber in Planar Graphs.
In Proceedings of the 34th International Workshop on Graph-Theoretic Concepts in Computer Science (WG),
volume 5344 of Lecture Notes in Computer Science,
pages 33-44,
2008.
[WWW
] [PDF
] [Abstract] [bibtex-entry]
-
N. Nisse and K. Suchan.
Voleur véloce dans un réseau planaire.
In 10èmes Rencontres Francophones sur les Aspects Algorithmiques de Télécommunications (AlgoTel'08),
pages 4p,
2008.
[WWW
] [PDF
] [Abstract] [bibtex-entry]
-
D. Ilcinkas,
N. Nisse,
and D. Soguet.
The Cost of Monotonicity in Distributed Graph Searching.
In OPODIS,
volume 4878 of Lecture Notes in Computer Science,
Guadeloupe, France,
pages 415-428,
December 2007.
Springer.
[WWW
] [PDF
] [Abstract] [bibtex-entry]
-
F. Mazoit and N. Nisse.
Monotonicity of Non-deterministic Graph Searching.
In Proceedings of the 33rd International Workshop on Graph-Theoretic Concepts in Computer Science (WG),
volume 4769 of Lecture Notes in Computer Science,
Dornburg, Germany,
pages 33-44,
June 2007.
Springer.
[WWW
] [PDF
] [Abstract] [bibtex-entry]
-
N. Nisse and D. Soguet.
Stratégies d'encerclement avec information.
In 9èmes Rencontres Francophones sur les Aspects Algorithmiques de Télécommunications (AlgoTel),
pages 49-52,
2007.
[WWW
] [PDF
] [Abstract] [bibtex-entry]
-
N. Nisse and D. Soguet.
Graph Searching with Advice.
In Proceedings of the 14th International Colloquium on Structural Information and Communication Complexity (SIROCCO),
volume 4474 of Lecture Notes in Computer Science,
Castiglioncello, Italy,
pages 51-65,
June 2007.
Springer.
[WWW
] [PDF
] [Abstract] [bibtex-entry]
-
L. Blin,
P. Fraigniaud,
N. Nisse,
and S. Vial.
Distributed Chasing of Network Intruders.
In Proceeding of the 13th International Colloquium on Structural Information and Communication Complexity (SIROCCO),
volume 4056 of Lecture Notes in Computer Science,
Chester, UK,
pages 70-84,
July 2006.
Springer.
[WWW
] [PDF
] [Abstract] [bibtex-entry]
-
L. Blin,
P. Fraigniaud,
N. Nisse,
and S. Vial.
Encerclement réparti d'un fugitif dans un réseau par des agents mobiles..
In 8èmes Rencontres Francophones sur les Aspects Algorithmiques de Télécommunications (AlgoTel),
pages 89-92,
2006.
[WWW
] [Abstract] [bibtex-entry]
-
F. V. Fomin,
P. Fraigniaud,
and N. Nisse.
Strategies d'encerclement non deterministes.
In 8èmes Rencontres Francophones sur les Aspects Algorithmiques de Télécommunications (AlgoTel),
pages 81-84,
2006.
[WWW
] [Abstract] [bibtex-entry]
-
P. Fraigniaud and N. Nisse.
Connected Treewidth and Connected Graph Searching.
In Proceeding of the 7th Latin American Symposium on Theoretical Informatics (LATIN),
pages 479-490,
2006.
[WWW
] [PDF
] [Abstract] [bibtex-entry]
-
P. Fraigniaud and N. Nisse.
Monotony Properties of Connected Visible Graph Searching.
In Proceedings of 32nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG),
volume 5911 of Lecture Notes in Computer Science,
Montpellier, France,
pages 229-240,
June 2006.
Springer.
[Abstract] [bibtex-entry]
-
F. V. Fomin,
P. Fraigniaud,
and N. Nisse.
Nondeterministic Graph Searching: From Pathwidth to Treewidth.
In Proceedings of the 30th International Symposium on Mathematical Foundations of Computer Science (MFCS),
pages 364-375,
2005.
[WWW
] [PDF
] [Abstract] [bibtex-entry]
-
P. Fraigniaud and N. Nisse.
Stratégies d'encerclement connexes dans un réseau.
In 7èmes Rencontres Francophones sur les Aspects Algorithmiques de Télécommunications (AlgoTel),
pages 13-16,
2005.
[WWW
] [PDF
] [Abstract] [bibtex-entry]
-
Ali Al Zoobi,
David Coudert,
and Nicolas Nisse.
Finding the k Shortest Simple Paths: Time and Space trade-offs.
Research Report,
Inria ; I3S, Université Côte d'Azur,
April 2021.
[WWW
] [PDF
]
Keywords:
k shortest simple paths,
graph algorithm,
space-time trade-off.
[bibtex-entry]
-
Ali Al Zoobi,
David Coudert,
and Nicolas Nisse.
On the complexity of finding $k$ shortest dissimilar paths in a graph.
Research Report,
Inria ; CNRS ; I3S ; Université Côte dâAzur,
2021.
[WWW
] [PDF
] [bibtex-entry]
-
Fabricio Benevides,
Jean-Claude Bermond,
Hicham Lesfari,
and Nicolas Nisse.
Minimum lethal sets in grids and tori under 3-neighbour bootstrap percolation.
Research Report,
Université Côte d'Azur,
2021.
[WWW
] [PDF
] [bibtex-entry]
-
Julien Bensmail,
Foivos Fioravantes,
Fionn Mc Inerney,
Nicolas Nisse,
and Nacim Oijid.
The Maker-Breaker Largest Connected Subgraph Game.
Research Report,
Université Côte dâAzur, CNRS, Inria, I3S, Biot, France,
2021.
[WWW
] [PDF
]
Keywords:
Maker-Breaker games,
Largest connected subgraph game,
Connection games,
PSPACE-complete.
[bibtex-entry]
-
Julien Bensmail,
Foivos Fioravantes,
Fionn Mc Inerney,
and Nicolas Nisse.
The Largest Connected Subgraph Game.
Research Report,
Inria & Université Cote d'Azur, CNRS, I3S, Sophia Antipolis, France ; CISPA Helmholtz Center for Information Security, Saarbrücken, Germany,
2021.
[WWW
] [PDF
]
Keywords:
Games on graphs,
Scoring games,
Connection games,
PSPACE-complete,
GI-hard.
[bibtex-entry]
-
Frédéric Giroire,
Nicolas Nisse,
Thibaud Trolliet,
and Malgorzata Sulkowska.
Preferential attachment hypergraph with high modularity.
Research Report,
Université Cote d'Azur,
2021.
[WWW
] [PDF
]
Keywords:
Complex network,
Hypergraph,
Preferential attachment,
Modularity.
[bibtex-entry]
-
Ali Al Zoobi,
David Coudert,
and Nicolas Nisse.
Space and time trade-off for the k shortest simple paths problem.
Research Report,
Inria & Université Cote d'Azur, CNRS, I3S, Sophia Antipolis, France,
February 2020.
[WWW
] [PDF
] [bibtex-entry]
-
Julio Araujo,
Julien Bensmail,
Victor Campos,
Frédéric Havet,
Ana Karolinna Maia De Oliveira,
Nicolas Nisse,
and Ana Silva.
On finding the best and worst orientations for the metric dimension.
Research Report,
Inria,
2020.
[WWW
] [PDF
]
Keywords:
Undirected graphs,
Resolving sets,
Metric dimension,
Digraphs.
[bibtex-entry]
-
Julien Bensmail,
Foivos Fioravantes,
Fionn Mc Inerney,
and Nicolas Nisse.
Further Results on an Equitable 1-2-3 Conjecture.
Research Report,
Université Côte d'Azur, CNRS, I3S, France ; Inria Sophia Antipolis ; Aix-Marseille Université (AMU),
April 2020.
[WWW
] [PDF
]
Keywords:
Proper labellings,
Equitable labellings,
1-2-3 Conjecture.
[bibtex-entry]
-
Julien Bensmail,
Foivos Fioravantes,
and Nicolas Nisse.
On Proper Labellings of Graphs with Minimum Label Sum.
Research Report,
Inria - Sophia antipolis,
2020.
[WWW
] [PDF
] [bibtex-entry]
-
Cláudio Carvalho,
Jonas Costa,
Cláudia Linhares Sales,
Raul Lopes,
Ana Karolinna Maia De Oliveira,
and Nicolas Nisse.
On the characterization of networks with multiple arc-disjoint branching flows.
Research Report,
UFC ; INRIA ; CNRS ; Université Côte dâAzur ; I3S ; LIRMM ; Université de Montpellier,
November 2020.
[WWW
] [PDF
] [bibtex-entry]
-
Thomas Dissaux,
Guillaume Ducoffe,
Nicolas Nisse,
and Simon Nivelle.
Treelength of Series-parallel graphs.
Research Report,
Inria & Université Cote d'Azur, CNRS, I3S, Sophia Antipolis, France,
2020.
[WWW
] [PDF
] [bibtex-entry]
-
Julien Bensmail,
Dorian Mazauric,
Fionn Mc Inerney,
Nicolas Nisse,
and Stéphane Pérennes.
Sequential Metric Dimension.
Research Report,
Inria,
2018.
[WWW
] [PDF
]
Keywords:
complexity,
Metric dimension,
Games in graphs.
[bibtex-entry]
-
Julien Bensmail,
Fionn Mc Inerney,
and Nicolas Nisse.
Metric Dimension: from Graphs to Oriented Graphs.
Research Report,
Inria & Université Cote d'Azur, CNRS, I3S, Sophia Antipolis, France,
November 2018.
[WWW
] [PDF
]
Keywords:
Strongly-connected orientations,
Metric dimension,
Resolving sets.
[bibtex-entry]
-
Frédéric Havet and Nicolas Nisse.
Constrained ear decompositions in graphs and digraphs.
Research Report,
Inria - Sophia Antipolis,
2018.
[WWW
] [PDF
] [bibtex-entry]
-
Fionn Mc Inerney,
Nicolas Nisse,
and Stéphane Pérennes.
Eternal Domination in Grids.
Research Report,
Inria & Université Cote d'Azur, CNRS, I3S, Sophia Antipolis, France,
May 2018.
[WWW
] [PDF
]
Keywords:
Eternal Domination,
Combinatorial Games,
Graphs,
Grids.
[bibtex-entry]
-
Nicolas Nisse.
Network Decontamination.
Research Report,
Inria & Université Nice Sophia Antipolis, CNRS, I3S, Sophia Antipolis, France,
2018.
[WWW
] [PDF
]
Keywords:
Graph Searching,
Computational Complexity,
(Distributed) Graph Algorithms.
[bibtex-entry]
-
Julien Bensmail,
Valentin Garnero,
and Nicolas Nisse.
On improving matchings in trees, via bounded-length augmentations.
Research Report,
Université Côte d'Azur,
July 2017.
[WWW
] [PDF
]
Keywords:
trees,
bounded-length augmentations,
maximum matchings.
[bibtex-entry]
-
Bartlomiej Bosek,
Przemyslaw Gordinowicz,
Jaroslaw Grytczuk,
Nicolas Nisse,
Joanna Sokol,
and Malgorzata Sleszynska-Nowak.
Localization Game on Geometric and Planar Graphs.
Research Report,
Inria,
2017.
[WWW
] [PDF
] [bibtex-entry]
-
Nathann Cohen,
Nìcolas A Martins,
Fionn Mc Inerney,
Nicolas Nisse,
Stéphane Pérennes,
and Rudini Sampaio.
Spy-Game on graphs: complexity and simple topologies.
Research Report,
Inria Sophia Antipolis,
2017.
[WWW
] [PDF
]
Keywords:
PSPACE-hard,
Cops and Robber games,
graphs.
[bibtex-entry]
-
Nathann Cohen,
Fionn Mc Inerney,
Nicolas Nisse,
and Stéphane Pérennes.
Study of a combinatorial game in graphs through Linear Programming.
Research Report,
Inria Sophia Antipolis,
2017.
[WWW
] [PDF
]
Keywords:
Linear Programming,
Cops and Robber games,
Graphs.
[bibtex-entry]
-
Kolja Knauer and Nicolas Nisse.
Computing metric hulls in graphs.
Research Report,
Inria - Sophia Antipolis,
2017.
[WWW
] [PDF
] [bibtex-entry]
-
Julio Araujo,
Guillaume Ducoffe,
Nicolas Nisse,
and Karol Suchan.
On interval number in cycle convexity.
Research Report,
Inria Sophia Antipolis ; I3S,
2016.
[WWW
] [PDF
]
Keywords:
graph,
convexity,
complexity,
dominating set.
[bibtex-entry]
-
Nathann Cohen,
Frédéric Havet,
William Lochet,
and Nicolas Nisse.
Subdivisions of oriented cycles in digraphs with large chromatic number.
Research Report RR-8865,
LRI - CNRS, University Paris-Sud ; LIP - ENS Lyon ; INRIA Sophia Antipolis - I3S,
February 2016.
[WWW
] [PDF
] [bibtex-entry]
-
Nathann Cohen,
Mathieu Hilaire,
Nicolas Martins,
Nicolas Nisse,
and Stéphane Pérennes.
Spy-Game on graphs.
Research Report RR-8869,
Inria,
February 2016.
[WWW
] [PDF
] [bibtex-entry]
-
David Coudert,
Guillaume Ducoffe,
Nicolas Nisse,
and Mauricio Soto.
Distance-preserving orderings in graphs.
Research Report RR-8973,
Inria Sophia Antipolis,
2016.
[WWW
] [PDF
]
Keywords:
bounded treewidth,
distance-preserving elimination ordering,
metric graph theory,
NP-complete,
exact expo- nential algorithm,
integer linear programming.
[bibtex-entry]
-
Guillaume Ducoffe,
Sylvain Legay,
and Nicolas Nisse.
On computing tree and path decompositions with metric constraints on the bags.
Research Report RR-8842,
INRIA Sophia Antipolis - Méditerranée ; LRI - CNRS, University Paris-Sud,
January 2016.
[WWW
] [PDF
]
Keywords:
path-breadth,
k-good tree decompositions,
tree-length,
tree-breadth,
path-length.
[bibtex-entry]
-
Seong-Gyun Jeong,
Yuliya Tarabalka,
Nicolas Nisse,
and Josiane Zerubia.
Inference of Curvilinear Structure based on Learning a Ranking Function and Graph Theory.
Research Report RR-8789,
Inria Sophia Antipolis,
2015.
[WWW
] [PDF
] [Abstract] [bibtex-entry]
-
Mamadou Moustapha Kanté,
Fatima Zahra Moataz,
Benjamin Momège,
and Nicolas Nisse.
Finding Paths in Grids with Forbidden Transitions.
Research Report,
Inria Sophia Antipolis ; Univeristé Nice Sophia Antipolis ; CNRS,
February 2015.
[WWW
] [PDF
]
Keywords:
asymmetric nodes,
grid,
planar graphs,
forbidden transitions.
[Abstract] [bibtex-entry]
-
Nicolas Nisse,
Alexandre Salch,
and Valentin Weber.
Recovery of disrupted airline operations using k-Maximum Matching in Graphs.
Research Report RR-8679,
Inria Sophia Antipolis ; INRIA,
February 2015.
[WWW
] [PDF
] [Abstract] [bibtex-entry]
-
David Coudert,
Guillaume Ducoffe,
and Nicolas Nisse.
Diameter of Minimal Separators in Graphs.
Research Report RR-8639,
Inria Sophia Antipolis ; I3S ; INRIA,
November 2014.
[WWW
] [PDF
] [bibtex-entry]
-
David Coudert,
Dorian Mazauric,
and Nicolas Nisse.
Experimental Evaluation of a Branch and Bound Algorithm for computing Pathwidth.
Research Report RR-8470,
INRIA,
February 2014.
[WWW
] [PDF
]
Keywords:
Pathwidth,
vertex-separation,
branch-and-bound,
Sage.
[bibtex-entry]
-
Gianlorenzo D'Angelo,
Xavier Défago,
and Nicolas Nisse.
Understanding the Power of Stigmergy of Anonymous Agents in Discrete Environments.
Research Report RR-8614,
Inria,
2014.
[WWW
] [PDF
] [bibtex-entry]
-
Bi Li,
Fatima Zahra Moataz,
Nicolas Nisse,
and Karol Suchan.
Size-Constrained Tree Decompositions.
Research Report,
INRIA Sophia-Antipolis,
October 2014.
[WWW
] [PDF
] [bibtex-entry]
-
Euripides Markou,
Nicolas Nisse,
and Stéphane Pérennes.
Exclusive Graph Searching vs. Pathwidth.
Research Report RR-8523,
INRIA,
2014.
[WWW
] [PDF
]
Keywords:
graph searching,
pathwidth,
computational complexity,
monotone strategies,
exclusivity property.
[bibtex-entry]
-
O. Amini,
D. Coudert,
and N. Nisse.
Some Results on Non-deterministic Graph Searching in Trees.
Research Report,
2013.
[WWW
] [PDF
] [bibtex-entry]
-
J. Araujo,
N. Nisse,
and S. Pérennes.
Weighted Coloring in Trees.
Research Report RR-8249,
INRIA,
2013.
[WWW
] [PDF
] [bibtex-entry]
-
J-C. Bermond,
B. Li,
N. Nisse,
H. Rivano,
and M-L. Yu.
Data Gathering and Personalized Broadcasting in Radio Grids with Interferences.
Research Report RR-8218,
INRIA,
2013.
[WWW
] [PDF
] [bibtex-entry]
-
P. Bertomé,
T. Bouvier,
F. Mazoit,
N. Nisse,
and R. Pardo Soares.
An Unified FPT Algorithm for Width of Partition Functions.
Research Report RR-8372,
INRIA,
September 2013.
[WWW
] [PDF
] [bibtex-entry]
-
L. Blin,
J. Burman,
and N. Nisse.
Exclusive Graph Searching.
Report,
June 2013.
[WWW
] [PDF
] [bibtex-entry]
-
G. D'Angelo,
A. Navarra,
and N. Nisse.
Robot Searching and Gathering on Rings under Minimal Assumptions.
Research Report RR-8250,
INRIA,
2013.
[WWW
] [PDF
] [bibtex-entry]
-
F. Giroire,
D. Mazauric,
N. Nisse,
S. Pérennes,
and R. Pardo Soares.
Connected Surveillance Game.
Research Report RR-8297,
INRIA,
May 2013.
[WWW
] [PDF
] [bibtex-entry]
-
F. Giroire,
R. Modrzejewski,
N. Nisse,
and S. Pérennes.
Maintaining Balanced Trees For Structured Distributed Streaming Systems.
Research Report RR-8309,
INRIA,
May 2013.
[WWW
] [PDF
] [bibtex-entry]
-
F. Giroire,
N. Nisse,
S. Pérennes,
and R. Pardo Soares.
Fractional Combinatorial Two-Player Games.
Research Report RR-8371,
INRIA,
September 2013.
[WWW
] [PDF
] [bibtex-entry]
-
L. Blin,
J. Burman,
and N. Nisse.
Perpetual Graph Searching.
Technical report RR-7897,
INRIA,
February 2012.
[WWW
] [PDF
] [Abstract] [bibtex-entry]
-
G. D'Angelo,
G. Di Stefano,
A. Navarra,
N. Nisse,
and K. Suchan.
A unified approach for different tasks on rings in robot-based computing systems.
Technical report RR-8013,
INRIA,
2012.
[WWW
] [PDF
] [Abstract] [bibtex-entry]
-
A. Kosowski,
B. Li,
N. Nisse,
and K. Suchan.
k-Chordal Graphs: from Cops and Robber to Compact Routing via Treewidth.
Technical report RR-7888,
INRIA,
February 2012.
[WWW
] [PDF
] [Abstract] [bibtex-entry]
-
N. Nisse and R. Soares.
On The Monotonicity of Process Number.
Technical report RR-7003,
INRIA,
October 2012.
[WWW
] [PDF
] [Abstract] [bibtex-entry]
-
J. Araujo,
V. Campos,
F. Giroire,
N. Nisse,
L. Sampaio,
and R. Soares.
On the hull number of some graph classes.
Technical report RR-7567,
INRIA,
September 2011.
[WWW
] [PDF
] [Abstract] [bibtex-entry]
-
F. Becker,
A. Kosowski,
N. Nisse,
I. Rapaport,
and K. Suchan.
Interconnection network with a shared whiteboard: Impact of (a)synchronicity on computing power.
Technical report RR-7746,
INRIA,
2011.
[WWW
] [PDF
] [Abstract] [bibtex-entry]
-
S. Belhareth,
D. Coudert,
D. Mazauric,
N. Nisse,
and I. Tahiri.
Reconfiguration with physical constraints in WDM networks.
Research Report RR-7850,
INRIA,
2011.
[WWW
] [PDF
]
Keywords:
Reconfiguration,
WDM,
NP-complete,
Physical Layer Impaiments..
[Abstract] [bibtex-entry]
-
F. Fomin,
F. Giroire,
A. Jean-Marie,
D. Mazauric,
and N. Nisse.
To Satisfy Impatient Web surfers is Hard.
Technical report RR-7740,
INRIA,
September 2011.
[WWW
] [PDF
] [Abstract] [bibtex-entry]
-
L. Barrière,
P. Flocchini,
F. V. Fomin,
P. Fraigniaud,
N. Nisse,
N. Santoro,
and D. Thilikos.
Connected Graph Searching.
Research Report 7363,
INRIA,
August 2010.
[WWW
] [PDF
] [Abstract] [bibtex-entry]
-
F. Becker,
M. Matamala,
N. Nisse,
I. Rapaport,
K. Suchan,
and I. Todinca.
Adding a referee to an interconnection network: What can(not) be computed in one round.
Research Report arXiv:1009.4447,
arXiv,
September 2010.
[WWW
] [PDF
] [Abstract] [bibtex-entry]
-
J. Chalopin,
V. Chepoi,
N. Nisse,
and Y. Vaxès.
Cop and robber games when the robber can hide and ride..
Technical report INRIA-RR7178,
INRIA,
January 2010.
[WWW
] [PDF
] [Abstract] [bibtex-entry]
-
N. Hanusse,
D. Ilcinkas,
A. Kosowski,
and N. Nisse.
How to beat the random walk when you have a clock?.
Research Report RR-7210,
INRIA,
February 2010.
[WWW
] [PDF
] [Abstract] [bibtex-entry]
-
J-C. Bermond,
N. Nisse,
P. Reyes,
and H. Rivano.
Fast Data Gathering in Radio Grid Networks.
Research Report RR-6851,
INRIA,
March 2009.
[WWW
] [PDF
] [Abstract] [bibtex-entry]
-
N. Cohen,
D. Coudert,
D. Mazauric,
N. Nepomuceno,
and N. Nisse.
Tradeoffs when optimizing Lightpaths Reconfiguration in WDM networks..
Technical report RR-7047,
INRIA,
September 2009.
[WWW
] [PDF
] [Abstract] [bibtex-entry]
-
D. Coudert,
D. Mazauric,
and N. Nisse.
Routing Reconfiguration/Process Number: Networks with Shared Bandwidth..
Technical report RR-6790,
INRIA,
January 2009.
[WWW
] [PDF
] [Abstract] [bibtex-entry]
-
F. Huc,
C. Molle,
N. Nisse,
S. Perennes,
and H. Rivano.
Stability of a local greedy distributed routing algorithm.
Technical report RR-6871,
INRIA,
March 2009.
[WWW
] [PDF
] [Abstract] [bibtex-entry]
-
P. Berthomé and N. Nisse.
A unified FPT Algorithm for Width of Partition Functions.
Research Report RR-6646,
INRIA,
September 2008.
[WWW
] [PDF
] [Abstract] [bibtex-entry]
-
D. Coudert,
F. Huc,
D. Mazauric,
N. Nisse,
and J-S. Sereni.
Routing Reconfiguration/Process Number: Coping wih Two Classes of Services.
Research Report RR-6698,
INRIA,
October 2008.
[WWW
] [Abstract] [bibtex-entry]
-
N. Nisse,
K. Suchan,
and I. Rapaport.
Distributed computing of efficient routing schemes in generalized chordal graphs.
Technical report CMM-B-08/10-220,
CMM,
October 2008.
[PDF
] [Abstract] [bibtex-entry]
-
O. Amini,
D. Coudert,
and N. Nisse.
Some Results on Non-deterministic Graph Searching in Trees.
Research Report INRIA-00174965,
INRIA,
September 2007.
[WWW
] [PDF
] [Abstract] [bibtex-entry]
-
O. Amini,
F. Mazoit,
N. Nisse,
and S. Thomassé.
Submodular partition functions.
Technical report RR-1427-07,
LABRI, Univ. Bordeaux,
April 2007.
Note: Submitted in SIAM J. discrete Maths. [PDF
] [Abstract] [bibtex-entry]
-
Ali Al Zoobi,
David Coudert,
and Nicolas Nisse.
k shortest simple paths,
2021.
Note: Software.
[WWW
]
Keywords:
k shortest simple paths,
Graph algorithms,
Space-time trade-off.
[bibtex-entry]
-
Nicolas Nisse.
Posters de médiation scientifique IV : Jeux dans les Graphes,
2017.
Note: Posters de médiation scientifiques.
[WWW
] [PDF
] [bibtex-entry]
-
Nicolas Nisse.
Posters de médiation scientifique II : Tour de Magie et Binaire,
2017.
Note: Posters de médiation scientifiques.
[WWW
] [PDF
] [bibtex-entry]
-
Nicolas Nisse.
Posters de médiation scientifique I : Deux Jeux Combinatoires,
2017.
Note: Poster de médiation scientifique.
[WWW
] [PDF
] [bibtex-entry]
-
Nicolas Nisse.
Posters de médiation scientifique III : Réseaux de Tri,
2017.
Note: Posters de médiation scientifique.
[WWW
] [PDF
] [bibtex-entry]
-
Seong-Gyun Jeong,
Yuliya Tarabalka,
Nicolas Nisse,
and Josiane Zerubia.
Progressive Tree-like Curvilinear Structure Reconstruction with Structured Ranking Learning and Graph Algorithm.
Note: Working paper or preprint,
December 2016.
[WWW
] [PDF
] [bibtex-entry]
BACK TO COATI PUBLICATION INDEX
Last modified: Sat Jan 29 19:00:45 2022
