List of Publications (dblp) (pdf) (HAL)


Proceedings Edition         International Journals         Int. Conferences         National Conf.          Int. Conf. without Proceedings         Submitted         Theses


Conference Proceedings

  • Roberto Baldoni, Nicolas Nisse and Maarten van Steen (Eds.). Proc. of 17th Int. Conference On Principles Of DIstributed Systems (OPODIS), Springer, LNCS 8304, Nice, Dec. 2013.
  • Yann Busnel, Nicolas Nisse and Franck Rousseau (Eds.). Actes des 15es Rencontres Francophones sur les aspects Algorithmiques des Télécommunications (AlgoTel), Pornic, May 2013.

  • International Journals

  • [J19] Julio Araujo, Nicolas Nisse and Stéphane Pérennes. Weighted Coloring in Trees.
    To appear in SIAM Journal of Discrete Maths.
  • [J18] 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.
    To appear in Algorithmica.
  • [J17] 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.
    To appear in Distributed Computing.
  • [J16] Adrian Kosowski, Bi Li, Nicolas Nisse and Karol Suchan. k-Chordal Graphs: from Cops and Robber to Compact Routing via Treewidth.
    To appear in Algorithmica.
  • [J15] Fedor V. Fomin, Frédéric Giroire, Alain Jean-Marie, Dorian Mazauric and Nicolas Nisse, To satisfy Impatient Web surfers is Hard.
    Theoretical Computer Science, Volume 526, pages 1-17, 2014.
  • [J14] Julio Araujo, Victor Campos, Frédéric Giroire, Nicolas Nisse, Leonardo Sampaio and Ronan Soares, On the hull number of some graph classes
    Theoretical Computer Science, Volume 475, pages 1-12, 2013.
  • [J13] Lali Barrière, Paola Flocchini, Fedor V. Fomin, Pierre Fraigniaud, Nicolas Nisse, Nicola Santoro and Dimitrios M. Thilikos, Connected Graph Searching
    Information and Computation, Volume 219, pages 1-16, 2012.
  • [J12] Nicolas Nisse, Ivan Rapaport and Karol Suchan, Distributed computing of efficient routing schemes in generalized chordal graphs.
    Theoretical Computer Science, Volume 444(27), pages 17-27, 2012. (.bib)
  • [J11] Nathann Cohen, David Coudert, Dorian Mazauric, Napoleao Nepomuceno and Nicolas Nisse, Tradeoffs in process strategy games with application in the WDM reconfiguration problem.
    Theoretical Computer Science, Volume 412(35), pages 4675-4687, 2011. (.bib)
  • [J10] Jérémie Chalopin, Victor Chepoi, Nicolas Nisse and Yann Vaxès, Cop and robber games when the robber can hide and ride.
    SIAM Journal of Discrete Maths, Volume 25(1), pages 333-359, 2011. (.bib)
  • [J9] Fedor V. Fomin, Petr Golovach, Jan Kratochvil, Nicolas Nisse and Karol Suchan, Pursuing a fast robber on a graph.
    Theoretical Computer Science, Volume 411(7-9), pages 1167-1181, 2010. (.bib)
  • [J8] Omid Amini, Frédéric Mazoit, Nicolas Nisse and Stéphan Thomassé, Submodular Partition Functions.
    Discrete Maths, Volume 309(20), pages 6000-6008, 2009.(.bib)
  • [J7] David Ilcinkas, Nicolas Nisse and David Soguet, The Cost of Monotonicity in Distributed Graph Searching.
    Distributed Computing, Volume 22(2), pages 117-127, 2009. (.bib)
  • [J6] Nicolas Nisse, Connected Graph Searching in Chordal Graphs.
    Discrete Applied Maths, Volume 157(12), pages 2603-2610, 2009.(.bib)
  • [J5] Nicolas Nisse and David Soguet, Graph Searching with Advice.
    Theoretical Computer Science, Volume 410(14), pages 1307-1318, 2009. (.bib)
  • [J4] Fedor V. Fomin, Pierre Fraigniaud and Nicolas Nisse, Non-Deterministic Graph Searching: From Pathwidth to Treewidth.
    Algorithmica, Volume 53(3), pages 358-373, 2009. (.bib)
  • [J3] Pierre Fraigniaud and Nicolas Nisse, Monotony Properties of Connected Visible Graph Searching.
    Information and Computation, Volume 206 (12), pages 1383-1393, 2008. (.bib)
  • [J2] Frédéric Mazoit and Nicolas Nisse, Monotonicity Property of Non-Deterministic Graph Searching.
    Theoretical Computer Science, Volume 399 (3), pages 169-178, 2008. (.bib)
  • [J1] Lélia Blin, Pierre Fraigniaud, Nicolas Nisse and Sandrine Vial, Distributed Chasing of Network Intruders by Mobile Agents.
    Theoretical Computer Science, Volume 399 (1-2), pages 12-37, 2008. (.bib)

  • International Conferences

  • [Ci30] Gianlorenzo D'Angelo, Xavier Défago and Nicolas Nisse. Understanding the Power of Stigmergy of Anonymous Agents in Discrete Environments.
    To appear in Proceedings of the Second International Symposium on Computing and Networking (CANDAR), 2014.
  • [Ci29] David Coudert, Dorian Mazauric and Nicolas Nisse. Experimental Evaluation of a Branch and Bound Algorithm for computing Pathwidth.
    To appear in Proceedings of the 13rd Symposium on Experimental Algorithms (SEA), 2014.
  • [Ci28] Julio Araujo, Nicolas Nisse and Stéphane Pérennes. Weighted Coloring in Trees.
    In Proceedings of the 31st Symposium on Theoretical Aspects of Computer Science (STACS), Schloss Dagstuhl, pages 75-86, 2014.
  • [Ci27] Gianlorenzo D'Angelo, Alfredo Navarra and Nicolas Nisse. Gathering and Exclusive Searching on Rings under Minimal Assumptions.
    In Proceedings of the 15th International Conference on Distributed Computing and Networking (ICDCN), LNCS, Springer, pages 149-164, 2014.
  • [Ci26] Lélia Blin, Janna Burman and Nicolas Nisse. Exclusive Graph Searching.
    In Proceedings of 21st European Symposium on Algorithms (ESA), Springer LNCS 8125, pages 181-192, 2013.
  • [Ci25] Frédéric Giroire, Dorian Mazauric, Nicolas Nisse, Stéphane Pérennes and Ronan Pardo Soares. Connected Surveillance Game.
    In Proceedings of the 20th Colloquium on Structural Information and Communication Complexity (SIROCCO), Springer LNCS 8179, pages 68-79, 2013.
  • [Ci24] Frédéric Giroire, Remigiusz Modrzejewski, Nicolas Nisse and Stéphane Pérennes, Maintaining Balanced Trees For Structured Distributed Streaming Systems.
    In Proceedings of the 20th Colloquium on Structural Information and Communication Complexity (SIROCCO), Springer LNCS 8179, pages 177-188, 2013.
  • [Ci23] Gianlorenzo D'Angelo, Gabriele Di Stefano, Alfredo Navarra, Nicolas Nisse and Karol Suchan. A unified approach for different tasks on rings in robot-based computing systems.
    In Proceedings of the 15th Workshop on Advances in Parallel and Distributed Computational Models (APDCM), IEEE, IPDPS Workshop, pages 667-676, 2013.
  • [Ci22] Nicolas Nisse and Ronan Pardo Soares. On the monotonicity of Process Number.
    In Proceedings of 7th Latin-American Algorithms, Graphs and Optimization Symposium (LAGOS), Elsevier, Electronic Note Discrete Maths 44, pages 141-147, 2013.
  • [Ci21] Lélia Blin, Janna Burman and Nicolas Nisse. Distributed Exclusive and Perpetual Tree Searching.
    Brief Announcement in Proceedings of 26th International Symposium on DIStributed Computing (DISC), Springer LNCS 7611, pages 407-408, 2012.
  • [Ci20] Adrian Kosowski, Bi Li, Nicolas Nisse and Karol Suchan. k-Chordal Graphs: from Cops and Robber to Compact Routing via Treewidth.
    In Proceedings of 39th International Colloquium on Automata, Languages and Programming (ICALP), track C, Springer LNCS 7392, pages 610-622, 2012.
  • [Ci19] Florent Becker, Adrian Kosowski, Nicolas Nisse, Ivan Rapaport and Karol Suchan. Allowing each node to communicate only once in a distributed system: shared whiteboard models.
    In Proceedings of 24th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 11-17, 2012.
  • [Ci18] Fedor V. Fomin, Frédéric Giroire, Alain Jean-Marie, Dorian Mazauric and Nicolas Nisse, To satisfy Impatient Web surfers is Hard.
    In Proceedings of 6th International Conference on FUN with Algorithms (FUN), Springer LNCS 7288, pages 166-176, 2012.
  • [Ci17] Sonia Belhareth, David Coudert, Dorian Mazauric, Nicolas Nisse and Issam Tahiri. Reconfiguration with physical constraints in WDM networks.
    In Proceedings of Workshop on New Trends in Optical Networks Survivability (Netsurviv), IEEE, colocated with ICC, pages 6257-6261, 2012.
  • [Ci16] Florent Becker, Martin Matamala, Nicolas Nisse, Ivan Rapaport, Karol Suchan, and Ioan Todinca. Adding a referee to an interconnection network: What can(not) be computed in one round.
    In Proceedings of the 25th IEEE International Parallel & Distributed Processing Symposium (IPDPS), IEEE, pages 508-514, 2011. (.bib)
  • [Ci15] Nicolas Hanusse, David Ilcinkas, Adrian Kosowski and Nicolas Nisse, Locating a target with an agent guided by unreliable local advice.
    In Proceedings of 29th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC), pages 355-364, 2010. (.bib)
  • [Ci14] Nathann Cohen, David Coudert, Dorian Mazauric, Napoleao Nepomuceno and Nicolas Nisse, Tradeoffs in process strategy games with application in the WDM reconfiguration problem.
    In Proceedings of 5th International Conference on FUN with Algorithms (FUN), Springer LNCS 6099, pages 121-132, 2010. (.bib)
  • [Ci13] Florian Huc, Christelle Molle-Caillouet, Nicolas Nisse, Stéphane Pérennes and Hervé Rivano, Stability of a local greedy distributed routing algorithm.
    In Proceedings of the 12th Workshop on Advances in Parallel and Distributed Computational Models (APDCM), IEEE, 2010. (.bib)
  • [Ci12] Nicolas Nisse, Ivan Rapaport and Karol Suchan, Distributed computing of efficient routing schemes in generalized chordal graphs.
    In Proceedings of the 16th Colloquium on Structural Information and Communication Complexity (SIROCCO), Springer LNCS 5869, pages 252-265, 2009. (.bib)
  • [Ci11] David Coudert, Florian Huc, Dorian Mazauric, Nicolas Nisse and Jean Sébastien Sereni, Routing Reconfiguration/Process Number: Coping wih Two Classes of Services.
    In Proceedings of the 13th Conference on Optical Network Design and Modeling (ONDM), IEEE, 2009. (slides) (.bib)
  • [Ci10] Jean-Claude.Bermond, Nicolas Nisse, Patricio Reyes and Hervé Rivano, Minimum delay Data Gathering in Radio Networks.
    In Proceedings of the 8th international conference on Ad Hoc Networks and Wireless (AdHoc-NOW), Springer LNCS 5793, pages  69-82, 2009. (.bib)
  • [Ci9] David Coudert, Dorian Mazauric and Nicolas Nisse, On Rerouting Connection Requests in Networks with Shared Bandwidth.
    In Proceedings of the DIMAP Workshop on Algorithmic Graph Theory (AGT), Elsevier, Electronic Note Discrete Maths., Volume 32, pages 109-116, 2009. (slides) (.bib)
  • [Ci8] Nicolas Nisse and Karol Suchan, Fast Robber in Planar Graphs.
    In Proceedings of the 34th International Workshop on Graph-Theoretic Concepts in Computer Science (WG),  Springer LNCS 5344, pages  312-323, 2008. (.bib)
  • [Ci7] David Ilcinkas, Nicolas Nisse and David Soguet, The Cost of Monotonicity in Distributed Graph Searching.
    In Proceedings to the 11th International Conference On Principles Of Distributed Systems (OPODIS),  Springer LNCS 4878, pages  415-428, 2007. (slides) (.bib)
  • [Ci6] Frédéric Mazoit and Nicolas Nisse, Monotonicity Property of Non-Deterministic Graph Searching.
    In Proceedings of the 33rd International Workshop on Graph-Theoretic Concepts in Computer Science (WG),  Springer LNCS 4769, pages  33-44, 2007. (slides) (.bib)
  • [Ci5] Nicolas Nisse and David Soguet, Graph Searching with advice.
    In Proceedings of the 14th Colloquium on Structural Information and Communication Complexity (SIROCCO),  Springer LNCS 4474, pages  51-65, 2007. (slides) (.bib)
  • [Ci4] Lélia Blin, Pierre Fraigniaud, Nicolas Nisse and Sandrine Vial, Distributed Chasing of Network Intruders by Mobile Agents.
    In Proceedings of the 13th Colloquium on Structural Information and Communication Complexity (SIROCCO), Springer LNCS 4056, pages  70-84, 2006. (slides) (.bib)
  • [Ci3] Pierre Fraigniaud and Nicolas Nisse, Monotony Properties of Connected Visible Graph Searching.
    In Proceedings of the 32nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG), Springer LNCS 4271, pages 229-240, 2006. (slides) (.bib)
  • [Ci2] Pierre Fraigniaud and Nicolas Nisse, Connected Treewidth and Connected Graph Searching.
    In Proceedings of the 7th Latin American Theoretical Informatics Symposium (LATIN), Springer LNCS 3887, pages  479-490, 2006. (slides) (.bib)
  • [Ci1] Fedor V. Fomin, Pierre Fraigniaud and Nicolas Nisse, Non-Deterministic Graph Searching: From Pathwidth to Treewidth.
    In Proceedings of the 30th International Symposium on Mathematical Foundations of Computer Science (MFCS), Springer LNCS 3618, pages 364-375, 2005. (slides) (.bib)


  • National Conferences
  • [Cn15] Adrian Kosowski, Bi Li, Nicolas Nisse and Karol Suchan. k-Chordal Graphs: from Cops and Robber to Compact Routing via Treewidth.
    In 14es Rencontres Francophones sur les aspects Algorithmiques des Télécommunications (AlgoTel), pages 83-86, 2012.
  • [Cn14] Fedor V. Fomin, Frédéric Giroire, Alain Jean-Marie, Dorian Mazauric and Nicolas Nisse, Satisfaire un internaute impatient est difficile.
    In 14es Rencontres Francophones sur les aspects Algorithmiques des Télécommunications (AlgoTel), pages 79-82, 2012. (best paper award)
  • [Cn13] Lélia Blin, Janna Burman and Nicolas Nisse, Nettoyage perpétuel de réseaux.
    In 14es Rencontres Francophones sur les aspects Algorithmiques des Télécommunications (AlgoTel), pages 31-34, 2012.
  • [Cn12] Sonia Belhareth, David Coudert, Dorian Mazauric, Nicolas Nisse and Issam Tahiri. Reconfiguration avec contraintes physiques dans les réseaux WDM.
    In 13es Rencontres Francophones sur les aspects Algorithmiques des Télécommunications (AlgoTel), pages 17-20, 2011.
  • [Cn11] Florent Becker, Martin Matamala, Nicolas Nisse, Ivan Rapaport, Karol Suchan, and Ioan Todinca. Reconstruire un graphe en une ronde.
    In 13es Rencontres Francophones sur les aspects Algorithmiques des Télécommunications (AlgoTel), pages 31-34, 2011.
  • [Cn10] Nathann Cohen, David Coudert, Dorian Mazauric, Napoleao Nepomuceno and Nicolas Nisse, Tradeoffs in routing reconfiguration problems.
    In 12es Rencontres Francophones sur les aspects Algorithmiques des Télécommunications (AlgoTel), pages 119-122, 2010. (slides) (.bib)
  • [Cn9] Nicolas Hanusse, David Ilcinkas, Adrian Kosowski and Nicolas Nisse, Comment battre la marche aléatoire en comptant ?.
    In 12es Rencontres Francophones sur les aspects Algorithmiques des Télécommunications (AlgoTel), pages 27-30, 2010. (slides) (.bib)
  • [Cn8] Jean-Claude Bermond, Nicolas Nisse, Patricio Reyes and Hervé Rivano, Fast Data Gathering in Radio Grid Networks.
    In 11es Rencontres Francophones sur les aspects Algorithmiques des Télécommunications (AlgoTel), pages 53-56, 2009. (slides) (.bib)
  • [Cn7] David Coudert, Florian Huc, Dorian Mazauric, Nicolas Nisse and Jean Sébastien Sereni, Reconfiguration dans les réseaux optiques.
    In 11es Rencontres Francophones sur les aspects Algorithmiques des Télécommunications (AlgoTel), pages 25-28, 2009. (slides) (.bib)
  • [Cn6] Nicolas Nisse and Karol Suchan, Voleur véloce dans un réseau planaire.
    In 10es Rencontres Francophones sur les aspects Algorithmiques des Télécommunications (AlgoTel), pages 29-32, 2008. (slides) (.bib)
  • [Cn5] David Ilcinkas, Nicolas Nisse and David Soguet, Le coût de la monotonie dans les stratégies d'encerclement réparti.
    In 10es Rencontres Francophones sur les aspects Algorithmiques des Télécommunications (AlgoTel), pages 33-36, 2008. (best student paper award) (.bib)
  • [Cn4] Nicolas Nisse and David Soguet, Stratégies d'encerclement avec information.
    In 9es Rencontres Francophones sur les aspects Algorithmiques des Télécommunications (AlgoTel),  pages 49-52, 2007. (slides). (.bib)
  • [Cn3] Lélia Blin, Pierre Fraigniaud, Nicolas Nisse and Sandrine Vial, Encerclement réparti d'un fugitif dans un réseau par des agents mobiles.
    In 8es Rencontres Francophones sur les aspects Algorithmiques des Télécommunications (AlgoTel), pages 89-92, 2006. (slides) (.bib)
  • [Cn2] Fedor V. Fomin, Pierre Fraigniaud and Nicolas Nisse, Strategies d'encerclement non deterministes.
    In 8es Rencontres Francophones sur les aspects Algorithmiques des Télécommunications (AlgoTel), pages 81-84, 2006. (slides)(.bib)
  • [Cn1] Pierre Fraigniaud and Nicolas Nisse, Stratégies d'encerclement connexes dans un réseau.
    In 7es Rencontres Francophones sur les aspects Algorithmiques des Télécommunications (AlgoTel), pages 13-16, 2005. (slides)(.bib)

  • International Conferences without Proceedings
  • Bi Li, Fatima Zahra Moataz and Nicolas Nisse, Minimum Size Tree-Decompositions.
    9th International colloquium on graph theory and combinatorics (ICGT), 2014
  • Nicolas Nisse, Fractional Combinatorial Games.
    27th European Conference on Operational Research (EURO), 2013
  • Jérémie Chalopin, Victor Chepoi, Nicolas Nisse and Yann Vaxès, Cop and robber games when the robber can hide and ride (abstract).
    8th French Combinatorial Conference (FCC), 2010.(.bib)
  • Nicolas Nisse, Graph Searching and Graph Decompositions.
    24th European Conference on Operational Research (EURO), 2010


  • Submitted papers
    to International Revues
  • Euripides Markou, Nicolas Nisse and Stéphane Pérennes. Exclusive Graph Searching vs. Pathwidth.
    Research Report, INRIA-RR8523, Sophia Antipolis, France, 2014.
  • Frédéric Giroire, Dorian Mazauric, Nicolas Nisse, Stéphane Pérennes and Ronan Pardo Soares. Connected Surveillance Game.
    Research Report, INRIA-RR8297, Sophia Antipolis, France, 2013.
  • Frédéric Giroire, Remigiusz Modrzejewski, Nicolas Nisse and Stéphane Pérennes, Maintaining Balanced Trees For Structured Distributed Streaming Systems.
    Research Report, INRIA-RR8309, Sophia Antipolis, France, 2013.
  • Jean-Claude Bermond, Bi Li, Nicolas Nisse, Hervé Rivano and Min-Li Yu. Data Gathering and Personalized Broadcasting in Radio Grids with Interferences
    Research Report, INRIA-RR8218, Sophia Antipolis, France, Jan. 2013.
  • Nicolas Nisse and Ronan Pardo Soares. On the monotonicity of Process Number.
    Research Report, INRIA-RR8132, Sophia Antipolis, France, 2012.
  • Omid Amini, David Coudert, and Nicolas Nisse, Some Results on Non-deterministic Graph Searching in Trees.
    Research Report, INRIA-00174965, HAL, Sophia Antipolis, France, Sept. 2007.

  • to be Submitted
  • Frédéric Giroire, Nicolas Nisse, Stéphane Pérennes and Ronan Pardo Soares. Fractional Combinatorial Games.
    Research Report, INRIA-RR8371, Sophia Antipolis, France, 2013.
  • Lélia Blin, Janna Burman and Nicolas Nisse. Exclusive Graph Searching.
    Research Report, HAL, France, 2013.
  • Nicolas Hanusse, David Ilcinkas, Adrian Kosowski and Nicolas Nisse, How to beat the random walk when you have a clock?
    Research Report, INRIA-RR7210, Sophia Antipolis, France, Feb. 2010.
  • Pascal Berthomé, Tom Bouvier, Frédéric Mazoit, Nicolas Nisse and Ronan Pardo Soares A unified FPT Algorithm for Width of Partition Functions.
    Research Report, INRIA-RR8372, HAL, Sophia Antipolis, France, 2013.

  • Theses
    HDR (Habilitation à Diriger le Recherches) (in english): Algorithmic complexity Between Structure and Knowledge. How Pursuit-evasion Games help .pdf
    Ph.D. Thesis (in french): Les jeux des gendarmes et du voleur dans les graphes. Mineurs de graphes, stratégies connexes et approche distribuée. .pdf, .ps (.bib)
    Master Thesis (in french): Expansion connexe dans les réseaux (2004) (.bib)