Publications
2008 Networks become navigable as nodes move and forget Proceedings of ICALP'08, 35th International Colloquium on Automata, Languages and Programming, to appear (2008). Co-authors: Augustin Chaintreau and Pierre Fraigniaud. Recovering the long range links in augmented graphs Proceedings of SIROCCO'08, 15th International Colloquium on Structural Information and Communication Complexity, to appear (2008). Co-authors: Pierre Fraigniaud and Zvi Lotker. Opportunistic spatial gossip over mobile social networks Proceedings of WOSN'08, 1st ACM SIGCOMM Workshop on Online Social Networks, to appear (2008). Co-authors: Augustin Chaintreau and Pierre Fraigniaud. The Inframetric model for the Internet Proceedings of INFOCOM'08, 27th IEEE International Conference on Computer Communications, Joint Conference of the IEEE Computer and Communications societies, to appear (2008). Co-authors: Pierre Fraigniaud and Laurent Viennot. 2007 Universal Augmentation Schemes for Network Navigability: Overcoming the √n-Barrier Proceedings of SPAA'07, 19th ACM Symposium on Parallelism in Algorithms and Architectures, pp 1-7 (2007). Best paper award. Co-authors: Pierre Fraigniaud and Cyril Gavoille and Adrian Kosowski and Zvi Lotker. Local MST Computation with Short Advice Proceedings of SPAA'07, 19th ACM Symposium on Parallelism in Algorithms and Architectures, pp 154-160 (2007). Co-authors: Pierre Fraigniaud and Amos Korman. Can transitive orientation make sandwich problems easier? Discrete Mathematics, 307(16), pp. 230-2041 (2007). Co-authors: Michel Habib and David Kelly and Christophe Paul III ‘'Routage dans les petits mondes'', sur le site internet )i( Interstices en collaboration avec N. Schabanel, 2007. Article de vulgarisation. 2006 Could any graph be turned into a small world? Theoretical Computer Science special issue on Complex Networks 355(1), pp 96 - 103 (2006). Co-authors: Philippe Duchon, Nicolas Hanusse, and Nicolas Schabanel. A doubling dimension threshold Theta(loglog n) for augmented graphs navigability    Proceedings of ESA'06, 14th Annual European Symposium on Algorithm, pp. 376-386 (2006). Co-authors: Pierre Fraigniaud and Zvi Lotker. T TALK Towards small world emergence Proceedings of SPAA'06, 18th ACM Symposium on Parallelism in Algorithms and Architectures, pp. 225-232 (2006). Co-authors: Philippe Duchon, Nicolas Hanusse and Nicolas Schabanel. III ‘'It's a small world after all!'', Poster, joint work with Nicolas Schabanel, 2006. 2005 Close to optimal decentralized routing in long-range contact networks   Invited to Theoretical Computer Science special issue on ICALP'04, vol. 348, issue 2-3, pp 294 - 310 (2005). Co-author: Nicolas Schabanel. Note: valid for any dimension d>1. Could any graph be turned into a small world?   Proceedings of DISC'05, 19th International Symposium on Distributed Computing, LNCS vol. 3724/2005, pp. 511-513 (2005). Co-authors: Philippe Duchon, Nicolas Hanusse and Nicolas Schabanel III Algorithmes de routage et modèles aléatoires pour les graphes petits mondes.  PhD Thesis (2005). 2004 Almost optimal decentralized routing in long-range contact networks   Proceedings of ICALP'04, 31st International Colloquium on Automata, Languages and Programming, LNCS vol. 3142/2004 , pp. 894-905 (2004). Co-author: Nicolas Schabanel. 2003 A note on finding all homogeneous set sandwiches   Information Processing Letters, vol. 87/3, pp 147 - 151 (2003). Co-authors: Michel Habib and Christophe Paul Sandwich Problems for Posets   Proceedings of EuroComb'03, European Conference on Combinatorics, Graph Theory and Applications, pp. 173-177 (2003). Co-authors: Michel Habib, D. Kelly and Christophe Paul. 2002 III Sur quelques problèmes de sandwich de graphes et ordres. Mémoire de DEA (2002).http://www.liafa.jussieu.fr/~elebhar/ICALP08_arxiv.pdfhttp://www.ru.is/icalp08/http://www.thlab.net/spip.php?rubrique31http://www.liafa.jussieu.fr/~pierrefhttp://www.liafa.jussieu.fr/~elebhar/SIROCCO08_full.pdfhttp://www.unine.ch/sirocco08/http://www.liafa.jussieu.fr/~pierrefhttp://www.cse.bgu.ac.il/Articles/article_new.asp?ArticleId=128http://www.liafa.jussieu.fr/~elebhar/wosn08.pdfhttp://www.sigcomm.org/sigcomm2008/workshops/wosn/http://www.thlab.net/spip.php?rubrique31http://www.liafa.jussieu.fr/~pierrefhttp://www.liafa.jussieu.fr/~elebhar/exposes/inframetric.pdfhttp://www.ieee-infocom.org/http://www.liafa.jussieu.fr/~pierrefhttp://gyroweb.inria.fr/~viennot/http://www.liafa.jussieu.fr/~elebhar/SPAA07a.pdfhttp://www.cs.jhu.edu/~spaa/2007/http://www.liafa.jussieu.fr/~pierrefhttp://dept-info.labri.fr/~gavoille/http://sphere.pl/~kosowski/http://www.cse.bgu.ac.il/Articles/article_new.asp?ArticleId=128http://www.liafa.jussieu.fr/~elebhar/SPAA07b.pdfhttp://www.cs.jhu.edu/~spaa/2007/http://www.liafa.jussieu.fr/~pierrefhttp://iew3.technion.ac.il/~pandit/http://www.liafa.jussieu.fr/~elebhar/Full-dmEuro03.pdfhttp://www.liafa.jussieu.fr/~habib/http://www.lirmm.fr/~paulhttp://interstices.info/display.jsp?id=c_15920&qs=id=jalios_5127http://interstices.info/http://www.liafa.jussieu.fr/~elebhar/RR_TCS_special.pdfhttp://dept-info.labri.fr/~duchon/http://www.labri.fr/Perso/~hanusse/http://perso.ens-lyon.fr/nicolas.schabanel/http://www.liafa.jussieu.fr/~elebhar/esa06.pdfhttp://algo06.inf.ethz.ch/esahttp://www.lri.fr/~pierrehttp://www.cse.bgu.ac.il/Articles/article_new.asp?ArticleId=128http://www.liafa.jussieu.fr/~elebhar/exposes/DYNAMOstock.pdfhttp://www.liafa.jussieu.fr/~elebhar/SPAA06.pdfhttp://www.cs.jhu.edu/~spaa/2006/http://dept-info.labri.fr/~duchon/http://www.labri.fr/Perso/~hanusse/http://perso.ens-lyon.fr/nicolas.schabanel/http://www.liafa.jussieu.fr/~elebhar/PosterSmallworld.pdfhttp://www.liafa.jussieu.fr/~elebhar/TCS_ICALPissue05.pdfhttp://perso.ens-lyon.fr/nicolas.schabanel/http://www.liafa.jussieu.fr/~elebhar/disc_HDLS.pdfhttp://www.mimuw.edu.pl/~disc2005/http://dept-info.labri.fr/~duchon/http://www.labri.fr/Perso/~hanusse/http://perso.ens-lyon.fr/nicolas.schabanel/http://www.liafa.jussieu.fr/~elebhar/these_lebhar.pdfhttp://www.liafa.jussieu.fr/~elebhar/ICALP04.pdfhttp://www.math.utu.fi/ICALP04http://perso.ens-lyon.fr/nicolas.schabanel/http://www.liafa.jussieu.fr/~elebhar/rr-02141.pshttp://www.liafa.jussieu.fr/~habib/http://www.lirmm.fr/~paulhttp://www.liafa.jussieu.fr/~elebhar/Euro.pdfhttp://www.liafa.jussieu.fr/~habib/http://www.lirmm.fr/~paulhttp://www.liafa.jussieu.fr/~elebhar/memoireDEA.pdfshapeimage_2_link_0shapeimage_2_link_1shapeimage_2_link_2shapeimage_2_link_3shapeimage_2_link_4shapeimage_2_link_5shapeimage_2_link_6shapeimage_2_link_7shapeimage_2_link_8shapeimage_2_link_9shapeimage_2_link_10shapeimage_2_link_11shapeimage_2_link_12shapeimage_2_link_13shapeimage_2_link_14shapeimage_2_link_15shapeimage_2_link_16shapeimage_2_link_17shapeimage_2_link_18shapeimage_2_link_19shapeimage_2_link_20shapeimage_2_link_21shapeimage_2_link_22shapeimage_2_link_23shapeimage_2_link_24shapeimage_2_link_25shapeimage_2_link_26shapeimage_2_link_27shapeimage_2_link_28shapeimage_2_link_29shapeimage_2_link_30shapeimage_2_link_31shapeimage_2_link_32shapeimage_2_link_33shapeimage_2_link_34shapeimage_2_link_35shapeimage_2_link_36shapeimage_2_link_37shapeimage_2_link_38shapeimage_2_link_39shapeimage_2_link_40shapeimage_2_link_41shapeimage_2_link_42shapeimage_2_link_43shapeimage_2_link_44shapeimage_2_link_45shapeimage_2_link_46shapeimage_2_link_47shapeimage_2_link_48shapeimage_2_link_49shapeimage_2_link_50shapeimage_2_link_51shapeimage_2_link_52shapeimage_2_link_53shapeimage_2_link_54shapeimage_2_link_55shapeimage_2_link_56shapeimage_2_link_57shapeimage_2_link_58shapeimage_2_link_59shapeimage_2_link_60shapeimage_2_link_61shapeimage_2_link_62shapeimage_2_link_63