EN FR
EN FR


previous Previous | up Home


Bibliography

Publications of the year

Doctoral Dissertations and Habilitation Theses

Articles in International Peer-Reviewed Journals

  • 2E. Bampas, L. Gąsieniec, N. Hanusse, D. Ilcinkas, R. Klasing, A. Kosowski, T. Radzik.

    Robustness of the Rotor–Router Mechanism, in: Algorithmica, June 2016. [ DOI : 10.1007/s00453-016-0179-y ]

    https://hal.inria.fr/hal-01416012
  • 3M. Borassi, P. Crescenzi, M. Habib.

    Into the Square: On the Complexity of Some Quadratic-time Solvable Problems, in: Electronic Notes in Theoretical Computer Science, 2016, vol. 322, pp. 51-67.

    https://hal.inria.fr/hal-01422030
  • 4P. Charbit, I. Penev, S. Thomassé, N. Trotignon.

    Perfect graphs of arbitrarily large clique-chromatic number, in: Journal of Combinatorial Theory, Series B, January 2016, vol. 116, pp. 456-464. [ DOI : 10.1016/j.jctb.2015.09.008 ]

    https://hal.archives-ouvertes.fr/hal-01324052
  • 5V. Cohen-Addad, M. Habib, F. de Montgolfier.

    Algorithmic aspects of switch cographs, in: Discrete Applied Mathematics, 2016, vol. 200, pp. 23 - 42. [ DOI : 10.1016/j.dam.2015.07.008 ]

    https://hal.inria.fr/hal-01423053
  • 6D. G. Corneil, J. Dusart, M. Habib, E. Köhler.

    On the power of graph searching for cocomparability graphs, in: Siam Journal on Discrete Mathematics, 2016.

    https://hal.inria.fr/hal-01273687
  • 7D. G. Corneil, J. Dusart, M. Habib, A. Mamcarz, F. de Montgolfier.

    A tie-break model for graph search, in: Discrete Applied Mathematics, January 2016, vol. 199, pp. 89–100. [ DOI : 10.1016/j.dam.2015.06.011 ]

    https://hal.inria.fr/hal-01255055
  • 8P. Crescenzi, P. Fraigniaud, M. M. Halldorsson, H. Harutyunyan, C. Pierucci, A. Pietracaprina, G. Pucci.

    On the complexity of the shortest-path broadcast problem, in: Discrete Applied Mathematics, 2016, vol. 199, pp. 101-109. [ DOI : 10.1016/j.dam.2015.05.004 ]

    https://hal.inria.fr/hal-01255198
  • 9J. Czyzowicz, D. Dereniowski, L. Gąsieniec, R. Klasing, A. Kosowski, D. Pająk.

    Collision-Free Network Exploration, in: Journal of Computer and System Sciences, December 2016. [ DOI : 10.1016/j.jcss.2016.11.008 ]

    https://hal.inria.fr/hal-01416026
  • 10J. Czyzowicz, L. Gąsieniec, A. Kosowski, E. Kranakis, D. Krizanc, N. Taleb.

    When Patrolmen Become Corrupted: Monitoring a Graph Using Faulty Mobile Robots, in: Algorithmica, October 2016. [ DOI : 10.1007/s00453-016-0233-9 ]

    https://hal.inria.fr/hal-01416010
  • 11C. Delporte-Gallet, H. Fauconnier.

    Asynchronous Consensus with Bounded Memory, in: Lecture notes in computer science, May 2016, vol. 9944, 15 p. [ DOI : 10.1007/978-3-319-46140-3_12 ]

    https://hal.inria.fr/hal-01416509
  • 12D. Dereniowski, A. Kosowski, D. Pająk, P. Uznanski.

    Bounds on the cover time of parallel rotor walks, in: Journal of Computer and System Sciences, August 2016, vol. 82, no 5, pp. 802 - 816. [ DOI : 10.1016/j.jcss.2016.01.004 ]

    https://hal.archives-ouvertes.fr/hal-01415102
  • 13J. Dusart, M. Habib.

    A new LBFS-based algorithm for cocomparability graph recognition, in: Discrete Mathematics, 2016. [ DOI : 10.1016/j.dam.2015.07.016 ]

    https://hal.inria.fr/hal-01274023
  • 14E. Fonio, Y. Heyman, L. Boczkowski, A. Gelblum, A. Kosowski, A. Korman, O. Feinerman.

    A locally-blazed ant trail achieves efficient collective navigation despite limited information, in: eLife, November 2016, vol. 2016;5:e20185. [ DOI : 10.7554/eLife.20185 ]

    https://hal.inria.fr/hal-01413748
  • 15P. Fraigniaud, A. Clementi, P. Crescenzi, C. Doerr, F. Pasquale, R. Silvestri.

    Rumor spreading in random evolving graphs, in: Random Structures and Algorithms, 2016, vol. 48, no 2, pp. 290-312.

    https://hal.inria.fr/hal-01423643
  • 16P. Fraigniaud, M. M. Halldorsson, B. Patt-Shamir, D. Rawitz, A. Rosén.

    Shrinking Maxima, Decreasing Costs: New Online Packing and Covering Problems, in: Algorithmica, 2016, vol. 74, no 4, pp. 1205-1223.

    https://hal.inria.fr/hal-01423640
  • 17P. Fraigniaud, A. Korman.

    An Optimal Ancestry Labeling Scheme with Applications to XML Trees and Universal Posets, in: Journal of the ACM, 2016, vol. 63, pp. 1 - 31. [ DOI : 10.1145/2794076 ]

    https://hal.inria.fr/hal-01393643
  • 18R. Klasing, A. Kosowski, D. Pająk, T. Sauerwald.

    The multi-agent rotor-router on the ring: a deterministic alternative to parallel random walks, in: Distributed Computing, September 2016. [ DOI : 10.1007/s00446-016-0282-y ]

    https://hal.inria.fr/hal-01416011

Invited Conferences

  • 19A. Kosowski.

    What Makes a Distributed Problem Truly Local?, in: SIROCCO 2016 - 23rd International Colloquium on Structural Information and Communication Complexity, Helsinki, Finland, J. Suomela (editor), Lecture Notes in Computer Science, Springer, July 2016, vol. 9988, 3 p. [ DOI : 10.1007/978-3-319-48314-6 ]

    https://hal.inria.fr/hal-01415090

International Conferences with Proceedings

  • 20É. Birmelé, F. de Montgolfier, L. Planche.

    Minimum Eccentricity Shortest Path Problem: An Approximation Algorithm and Relation with the k-Laminarity Problem, in: COCOA 2016, Combinatorial Optimization and Applications - 10th International Conference, Hong Kong, China, December 2016, pp. 216 - 229. [ DOI : 10.1007/978-3-319-48749-6_16 ]

    https://hal.inria.fr/hal-01424469
  • 21A. Castañeda, C. Delporte-Gallet, H. Fauconnier, S. Rajsbaum, M. Raynal.

    Making Local Algorithms Wait-Free: The Case of Ring Coloring, in: SSS, Lyon, France, Stabilization, Safety, and Security of Distributed Systems, November 2016, vol. 10083, 16 p.

    https://hal.inria.fr/hal-01416522
  • 22A. Castañeda, P. Fraigniaud, E. Gafni, S. Rajsbaum, M. Roy.

    Asynchronous Coordination Under Preferences and Constraints, in: 23rd International Colloquium on Structural Information and Communication Complexity, Helsinki, Finland, SIROCCO 2016 pre-proceedings, July 2016.

    https://hal.archives-ouvertes.fr/hal-01341710
  • 23C. Delporte-Gallet, H. Fauconnier, E. Gafni, P. Kuznetsov.

    Set-Consensus Collections are Decidable, in: OPODIS, MADRID, Spain, LNCS, December 2016.

    https://hal.inria.fr/hal-01416981
  • 24C. Delporte-Gallet, H. Fauconnier, M. Raynal, S. Rajsbaum.

    Implementing Snapshot Objects on Top of Crash-Prone Asynchronous Message-Passing Systems, in: Algorithms and Architectures for Parallel Processing ( ICA3PP), Granada, France, Algorithms and Architectures for Parallel Processing Volume 10048 of the series Lecture Notes in Computer Science pp 341-355, Springer, December 2016, vol. 10048, 15 p.

    https://hal.inria.fr/hal-01416498
  • 25C. Delporte-Gallet, H. Fauconnier, M. Raynal, S. Rajsbaum.

    t-Resilient Immediate Snapshot Is Impossible, in: SIROCCO, Helsiinki, France, Structural Information and Communication Complexity, July 2016, vol. 9988, 15 p.

    https://hal.inria.fr/hal-01416515
  • 26P. Fraigniaud, B. Alkida, Z. Lotker, O. Dennis.

    Sparsifying Congested Cliques and Core-Periphery Networks, in: 23rd International Colloquium on Structural Information and Communication Complexity (SIROCCO), Helsinki, Finland, 2016.

    https://hal.inria.fr/hal-01423688
  • 27P. Fraigniaud, B. Bonakdarpour, S. Rajsbaum, D. Rosenblueth, C. Travers.

    Decentralized Asynchronous Crash-Resilient Runtime Verification, in: 27th International Conference on Concurrency Theory (CONCUR), Québec, Canada, 2016.

    https://hal.inria.fr/hal-01423646
  • 28P. Fraigniaud, P. Crescenzi, Z. Lotker, P. Penna.

    Core-periphery clustering and collaboration networks, in: IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM), San Francisco, United States, 2016.

    https://hal.inria.fr/hal-01423645
  • 29P. Fraigniaud, L. Feuilloley, J. Hirvonen.

    A Hierarchy of Local Decision, in: 43rd International Colloquium on Automata, Languages, and Programming (ICALP), Roma, Italy, 2016.

    https://hal.inria.fr/hal-01423644
  • 30P. Fraigniaud, M. Heinrich, A. Kosowski.

    Local Conflict Coloring, in: FOCS 2016 - 57th Annual IEEE Symposium on Foundations of Computer Science, New Brunswick, NJ, United States, October 2016.

    https://hal.inria.fr/hal-01223494
  • 31P. Fraigniaud, A. Korman, R. Yoav.

    Parallel exhaustive search without coordination, in: 48th ACM Symposium on Theory of Computing (STOC), Cambridge, MA, USA, France, 2016.

    https://hal.inria.fr/hal-01423634
  • 32P. Fraigniaud, E. Natale.

    Noisy Rumor Spreading and Plurality Consensus, in: ACM Symposium on Principles of Distributed Computing (PODC), Chicago, United States, 2016.

    https://hal.inria.fr/hal-01423686
  • 33P. Fraigniaud, S. Rajsbaum, C. Travers.

    Minimizing the Number of Opinions for Fault-Tolerant Distributed Decision Using Well-Quasi Orderings, in: 12th Latin American Symposium on Theoretical Informatics (LATIN), Ensenada, Mexico, 2016.

    https://hal.inria.fr/hal-01423679
  • 34P. Fraigniaud, S. Rajsbaum, C. Travers, P. Kuznetsov, T. Rieutord.

    Perfect Failure Detection with Very Few Bits, in: 18th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), Lyon, France, 2016.

    https://hal.inria.fr/hal-01423637
  • 35P. Fraigniaud, I. Rapaport, V. Salo, I. Todinca.

    Distributed Testing of Excluded Subgraphs, in: 30th International Symposium on Distributed Computing (DISC 2016), Paris, France, C. Gavoille, D. Ilcinkas (editors), Lecture Notes in Computer Science, Springer, September 2016, vol. LNCS 9888, pp. 342 - 356. [ DOI : 10.1007/978-3-662-53426-7_25 ]

    https://hal.inria.fr/hal-01423633
  • 36P. Gawrychowski, A. Kosowski, P. Uznanski.

    Sublinear-Space Distance Labeling Using Hubs, in: DISC 2016 - 30th International Symposium on DIStributed Computing, Paris, France, C. Gavoille, D. Ilcinkas (editors), Distributed Computing, Springer, September 2016, vol. 9888, pp. 230-242. [ DOI : 10.1007/978-3-662-53426-7_17 ]

    https://hal.inria.fr/hal-01415064
  • 37R. Klasing, A. Kosowski, D. Pająk.

    Setting Ports in an Anonymous Network: How to Reduce the Level of Symmetry?, in: SIROCCO 2016 - 23rd International Colloquium on Structural Information and Communication Complexity, Helsinki, Finland, J. Suomela (editor), Structural Information and Communication Complexity, Springer, July 2016, vol. 9988, pp. 35-48. [ DOI : 10.1007/978-3-319-48314-6_3 ]

    https://hal.inria.fr/hal-01415079
  • 38A. Kosowski, L. Viennot.

    Beyond Highway Dimension: Small Distance Labels Using Tree Skeletons, in: SODA 2017 - 28th ACM-SIAM Symposium on Discrete Algorithms, Barcelona, Spain, January 2017.

    https://hal.inria.fr/hal-01359084

Conferences without Proceedings

  • 39P. Gawrychowski, A. Kosowski, P. Uznanski.

    Brief Announcement: Sublinear-Space Distance Labeling Using Hubs, in: PODC 2016 - 35th ACM Symposium on Principles of Distributed Computing, Chicago, IL, United States, July 2016, pp. 43-45. [ DOI : 10.1145/2933057.2933077 ]

    https://hal.inria.fr/hal-01415072

Scientific Books (or Scientific Book chapters)

  • 40C. Delporte-Gallet, P. A. Abdulla (editors)

    Networked Systems - 4th International Conference, NETYS 2016, Marrakech, Morocco, May 18-20, 2016, Revised Selected Papers, LNCS, May 2016, vol. 9944.

    https://hal.inria.fr/hal-01416966
  • 41P. Fraigniaud.

    Locality in Distributed Graph Algorithms, in: Encyclopedia of Algorithms, Springer, 2016, pp. 1143-1148. [ DOI : 10.1007/978-1-4939-2864-4_608 ]

    https://hal.inria.fr/hal-01423632

Internal Reports

  • 42Y. Boufkhad, R. De La Paz, L. Linguaglossa, F. Mathieu, D. Perino, L. Viennot.

    Forwarding Tables Verification through Representative Header Sets, Inria Paris Rocquencourt, January 2016.

    https://hal.inria.fr/hal-01262130
  • 43P. Penna, L. Viennot.

    Independent lazy better-response dynamics on network games, ETH Zurich ; Inria ; Universite Paris Diderot-Paris VII, September 2016.

    https://hal.inria.fr/hal-01373411

Scientific Popularization

  • 44D. G. Corneil, M. Habib.

    Unified View of Graph Searching and LDFS-Based Certifying Algorithms, in: Encyclopedia of Algorithms, Springer-verlag, 2016. [ DOI : 10.1007/978-3-642-27848-8_685-1 ]

    https://hal.inria.fr/hal-01255083

Other Publications

  • 45A. Castañeda, C. Delporte, H. Fauconnier, S. Rajsbaum, M. Raynal.

    Wait-freedom and Locality are not Incompatible (with Distributed Ring Coloring as an Example), January 2016, working paper or preprint.

    https://hal.inria.fr/hal-01265958
  • 46C. Delporte, H. Fauconnier, S. Rajsbaum, M. Raynal.

    Implementing Snapshot Objects on Top of Crash-Prone Asynchronous Message-Passing Systems, May 2016, working paper or preprint.

    https://hal.inria.fr/hal-01313584
  • 47C. Delporte, H. Fauconnier, S. Rajsbaum, M. Raynal.

    t-Resilient Immediate Snapshot is Impossible, May 2016, working paper or preprint.

    https://hal.inria.fr/hal-01315342
  • 48J. Dusart, M. Habib, D. G. Corneil.

    Maximal cliques structure for cocomparability graphs and applications, November 2016, Il s'agit d'une recherche sur les relations entre les graphes d'intervalles et les graphes de cocomparabilité.

    https://hal.inria.fr/hal-01393927
  • 49L. Feuilloley, P. Fraigniaud.

    Survey of Distributed Decision, June 2016, working paper or preprint.

    https://hal.archives-ouvertes.fr/hal-01331880
  • 50F. Völkel, E. Bapteste, M. Habib, P. Lopez, C. Vigliotti.

    Read networks and k-laminar graphs, March 2016, working paper or preprint.

    https://hal.inria.fr/hal-01282715


previous Previous | up Home