MASCOTTE Project

MASCOTTE no longer exists => visit the new COATI project-team

Publications of year 2011
BACK TO MASCOTTE PUBLICATION INDEX

Publications of year 2011

N. Cohen. Some results in graph theory and its applications. PhD thesis, Ecole doctorale STIC, Université de Nice-Sophia Antipolis, October 2011. [WWW ]

Abstract:

This thesis consists in successive glimpses of different problems in discrete mathematics related to graph theory. Its mains focus is on graph colouring, i.e. on assignments of integer values to the vertices (or edges) of a graph satisfying a set of local constraints, most of the time the exclusion of specific patterns in the coloured graph. For several different types of colouring (vertex and edge choosability, acyclic or linear colouring, ...) a state of the art is provided, along with results ensuring the existence of such colourings on planar graphs or subclasses of them -- with the aim of minimising the number of colours used for a given Maximum Degree, or Maximum Average Degree. This thesis also deals with decompositions of graphs into induced subgraphs, and asserts that similarly to what Wilson's theorem implies for non-induced graph decomposition, there exists for any graph $H$ an infinite sequence of dense graph whose edge set can be partitioned in induced copies of $H$. The proof methodology involves hypergraphs, for which a decomposition result is presented, i.e. that the complete 3-uniform hypergraph can be partitioned into $\lceil \frac {n(n-1)} 6\rceil$ $\alpha$-acyclic hypergraphs as conjectured. In a third part are gathered algorithmic questions. Those are problems of optimisation or existence motivated by telecommunications in networks, studied with the classical framework of computational complexity, or the search of subgraphs through parametrised complexity. In a fourth part it, considers counting problems belonging to the study of chemical graphs, and finally details some Integer LinearPrograms used in the Mathematics software Sage.

@phdthesis{Coh11,

 author = {N. Cohen},

 title = {Some results in graph theory and its applications},

 school = {Ecole doctorale {STIC}, Universit\'e de Nice-Sophia Antipolis},

 day = {20},

 month = oct,

 year = {2011},

 url = {http://tel.archives-ouvertes.fr/tel-00645151/fr/},

 ftp = {http://tel.archives-ouvertes.fr/docs/00/64/51/51/PDF/Nathann_Cohen_-_Thesis.pdf},

 abstract = {This thesis consists in successive glimpses of different
 problems in discrete mathematics related to graph theory. Its mains
 focus is on graph colouring, i.e. on assignments of integer values to
 the vertices (or edges) of a graph satisfying a set of local
 constraints, most of the time the exclusion of specific patterns in
 the coloured graph. For several different types of colouring (vertex
 and edge choosability, acyclic or linear colouring, ...) a state of
 the art is provided, along with results ensuring the existence of such
 colourings on planar graphs or subclasses of them -- with the aim of
 minimising the number of colours used for a given Maximum Degree, or
 Maximum Average Degree. This thesis also deals with decompositions of
 graphs into induced subgraphs, and asserts that similarly to what
 Wilson's theorem implies for non-induced graph decomposition, there
 exists for any graph $H$ an infinite sequence of dense graph whose
 edge set can be partitioned in induced copies of $H$. The proof
 methodology involves hypergraphs, for which a decomposition result is
 presented, i.e. that the complete 3-uniform hypergraph can be
 partitioned into $\lceil \frac {n(n-1)} 6\rceil$ $\alpha$-acyclic
 hypergraphs as conjectured. In a third part are gathered algorithmic
 questions. Those are problems of optimisation or existence motivated
 by telecommunications in networks, studied with the classical
 framework of computational complexity, or the search of subgraphs
 through parametrised complexity. In a fourth part it, considers
 counting problems belonging to the study of chemical graphs, and
 finally details some Integer LinearPrograms used in the Mathematics
 software Sage.},

 x-pays = {FR},

 OPTx-editorial-board={no},

 OPTx-proceedings={no},

 OPTx-international-audience={yes},

 sorte = "these"
 
}

J-C Maureira Bravo. Internet on Rails. THESE, Ecole doctorale STIC, Université de Nice Sophia-Antipolis, January 2011. [WWW ] [PDF ]
Keywords: Train communications, WiFi, horizontal handover, layer 2 routes update, infrastructure network, combined chordal topologies, simulations..

Abstract:

This thesis proposes a new method for providing network connectivity to vehicles over a predefined trajectory (trains, metros, urban buses, etc.). The communication between the vehicle and the infrastructure network is based only on WiFi technology. The contributions of this work are two-fold: 1) the horizontal handover (between WiFi access points) and 2) the design and analysis of an infrastructure network (backbone network plus WiFi access network) deployed along the trajectory of the vehicle. In the first contribution, we propose a handover scheme, called Spiderman Handover, which describes the horizontal handover for an in-motion network (on-board the vehicle) considering a procedure to update the routing information of a bridged infrastructure network (OSI layer 2). We evaluate our proposal by means of simulation and we validate our results by experimental measurements. In the second contribution, we study theoretically the parameters of several chordal like topologies in order to build a backbone network for a linear access network. By comparing these parameters, we propose a backbone network composed by a combination of two chordal topologies. This backbone network provides a good balance between their deployment cost, number of hops to the gateway of the network and a reasonable resilience. Finally, we evaluate the integration of this infrastructure network and the handover scheme by means of simulations. Results showed that the proposed handover scheme works properly on the proposed infrastructure network, allowing the provision of a continuous network connectivity to passengers on-board trains, metros or urban buses.

@phdthesis{Mau11,

 author = {Maureira Bravo, J-C},

 title = {{Internet on Rails}},

 year = {2011},

 month = Jan,

 school = {Ecole doctorale {STIC}, Universit\'e de Nice Sophia-Antipolis},

 keywords = {Train communications; WiFi; horizontal handover; layer 2 routes update; infrastructure network; combined chordal topologies; simulations.},

 type = {THESE},

 url = {http://hal.inria.fr/tel-00594951/en},

 pdf = {http://tel.archives-ouvertes.fr/docs/00/59/49/51/PDF/thesis-JcM-final.pdf},

 abstract = {This thesis proposes a new method for providing network connectivity to vehicles over a predefined trajectory (trains, metros, urban buses, etc.). The communication between the vehicle and the infrastructure network is based only on WiFi technology. The contributions of this work are two-fold: 1) the horizontal handover (between WiFi access points) and 2) the design and analysis of an infrastructure network (backbone network plus WiFi access network) deployed along the trajectory of the vehicle. In the first contribution, we propose a handover scheme, called Spiderman Handover, which describes the horizontal handover for an in-motion network (on-board the vehicle) considering a procedure to update the routing information of a bridged infrastructure network (OSI layer 2). We evaluate our proposal by means of simulation and we validate our results by experimental measurements. In the second contribution, we study theoretically the parameters of several chordal like topologies in order to build a 
 backbone network for a linear access network. By comparing these parameters, we propose a backbone network composed by a combination of two chordal topologies. This backbone network provides a good balance between their deployment cost, number of hops to the gateway of the network and a reasonable resilience. Finally, we evaluate the integration of this infrastructure network and the handover scheme by means of simulations. Results showed that the proposed handover scheme works properly on the proposed infrastructure network, allowing the provision of a continuous network connectivity to passengers on-board trains, metros or urban buses.},

 x-editorial-board={yes},

 x-proceedings={yes},

 x-international-audience={yes},

 sorte = "these",

 
}

D. Mazauric. Optimisation discrète dans les réseaux de télécommunication: reconfiguration du routage, routage efficace en énergie, ordonnancement de liens et placement de données. PhD thesis, Ecole doctorale STIC, Université de Nice Sophia-Antipolis, November 2011. [WWW ] [PDF ]

Abstract:

Nous nous intÃ©ressons dans cette thÃ¨se Ã diffÃ©rents types de rÃ©seaux (optiques, sans-fil, pair-Ã -pair) ayant chacun leurs spÃ©cificitÃ©s mais partageant des problÃ©matiques communes : assurer la meilleure qualitÃ© de services possible, garantir la stabilitÃ© du systÃ¨me, minimiser les ressources et donc le coÃ»t de fonctionnement. Tout d'abord, nous Ã©tudions le problÃ¨me de la reconfiguration du routage dans les rÃ©seaux optiques consistant Ã rerouter les requÃªtes de connexion en minimisant les perturbations pour les utilisateurs. Puis, nous nous intÃ©ressons au problÃ¨me de la dÃ©termination de routages efficaces en Ã©nergie dans les rÃ©seaux coeur. Pour ce faire, nous Ã©tudions le problÃ¨me de trouver des routages minimisant le nombre d'Ã©quipements utilisÃ©s. Ensuite, nous nous intÃ©ressons aux algorithmes d'ordonnancement des liens dans les rÃ©seaux sans-fil en prÃ©sence d'interfÃ©rence. Enfin, nous considÃ©rons le problÃ¨me de stockage de donnÃ©es dans les rÃ©seaux pair-Ã -pair. Nous Ã©tudions l'impact de diffÃ©rentes politiques de placement sur la durÃ©e de vie des donnÃ©es et nous dÃ©terminons un choix de placement optimal. Pour rÃ©soudre ces problÃ¨mes, nous utilisons les outils thÃ©oriques des mathÃ©matiques discrÃ¨tes (graphes, configurations, optimisation combinatoire), d'algorithmique (complexitÃ©, algorithmique distribuÃ©e) et de probabilitÃ©s.

@phdthesis{Maz11,

 author = {Mazauric, D.},

 title = {Optimisation discr{\`e}te dans les r{\'e}seaux de t{\'e}l{\'e}communication: reconfiguration du routage, routage efficace en {\'e}nergie, ordonnancement de liens et placement de donn{\'e}es},

 year = {2011},

 month = Nov,

 school = {Ecole doctorale {STIC}, Universit\'e de Nice Sophia-Antipolis},

 abstract = {Nous nous intÃ©ressons dans cette thÃ¨se Ã diffÃ©rents types de rÃ©seaux 
 (optiques, sans-fil, pair-Ã -pair) ayant chacun leurs spÃ©cificitÃ©s mais 
 partageant des problÃ©matiques communes : assurer la meilleure qualitÃ© de
 services possible, garantir la stabilitÃ© du systÃ¨me, minimiser les 
 ressources et donc le coÃ»t de fonctionnement. Tout d'abord, nous 
 Ã©tudions le problÃ¨me de la reconfiguration du routage dans les rÃ©seaux 
 optiques consistant Ã rerouter les requÃªtes de connexion en minimisant 
 les perturbations pour les utilisateurs. Puis, nous nous intÃ©ressons au 
 problÃ¨me de la dÃ©termination de routages efficaces en Ã©nergie dans les 
 rÃ©seaux coeur. Pour ce faire, nous Ã©tudions le problÃ¨me de trouver des 
 routages minimisant le nombre d'Ã©quipements utilisÃ©s. Ensuite, nous nous
 intÃ©ressons aux algorithmes d'ordonnancement des liens dans les rÃ©seaux
 sans-fil en prÃ©sence d'interfÃ©rence. Enfin, nous considÃ©rons le 
 problÃ¨me de stockage de donnÃ©es dans les rÃ©seaux pair-Ã -pair. Nous 
 Ã©tudions l'impact de diffÃ©rentes politiques de placement sur la durÃ©e de
 vie des donnÃ©es et nous dÃ©terminons un choix de placement optimal. Pour
 rÃ©soudre ces problÃ¨mes, nous utilisons les outils thÃ©oriques des 
 mathÃ©matiques discrÃ¨tes (graphes, configurations, optimisation 
 combinatoire), d'algorithmique (complexitÃ©, algorithmique distribuÃ©e) et
 de probabilitÃ©s.},

 url = {http://tel.archives-ouvertes.fr/tel-00643513/fr/},

 pdf = {http://tel.archives-ouvertes.fr/docs/00/64/35/13/PDF/These-Dorian-Mazauric.pdf},

 x-editorial-board={no},

 x-proceedings={no},

 x-international-audience={no},

 sorte = "these",

 
}

J. Ribault. Reuse and Scalability in Modeling and Simulation Software Engineering. THESE, Ecole doctorale STIC, Université de Nice Sophia-Antipolis, January 2011. [WWW ] [PDF ]
Keywords: simulation, évènements discrets, aspects, séparation des préoccupations, instrumentation, modélisation, composant, simulation distribuée, réutilisation.

Abstract:

L'{\'e}tude d'un syst{\`e}me {\`a} l'aide de simulations informatiques {\`a} {\'e}v{\'e}nements discrets implique plusieurs activit{\'e}s: sp{\'e}ci cation du mod{\`e}le conceptuel, description de l'architecture logicielle du mod{\`e}le, d{\'e}veloppement des logiciels, sc{\'e}narisation de la simulation, instrumentation, plani cation d'exp{\'e}rimentation, con guration des ressources de calcul, ex{\'e}cution, post-traitement et analyse, validation et de v{\'e}ri cation (V\&V). De nombreux {\'e}l{\'e}ments logiciels sont requis pour remplir toutes ces activit{\'e}s. Toutefois, il est fr{\'e}quent de cr{\'e}er un nouveau simulateur {\`a} partir de rien quand on commence une {\'e}tude {\`a} l'aide de simulation. Dans ce cas il est n{\'e}cessaire de d{\'e}velopper de multiples outils prenant en charge les activit{\'e}s de la simulation. Cette th{\`e}se aborde le d{\'e} de la cr{\'e}ation de nouveaux simulateurs tout en r{\'e}utilisant des mod{\`e}les et des outils provenant d'autres simulateurs. En e et, la r{\'e}utilisation de logiciel augmente la abilit{\'e}, est moins sujette aux erreurs, permet une meilleure utilisation des expertises compl{\'e}mentaires, am{\'e}liore la conformit{\'e} aux normes, et acc{\'e}l{\`e}re le d{\'e}veloppement. La r{\'e}utilisation de logiciels peut {\^e}tre appliqu{\'e}e {\`a} toutes les activit{\'e}s de la simulation. Plusieurs probl{\`e}mes doivent {\^e}tre r{\'e}solus pour tirer pleinement pro t de la r{\'e}utilisation. Dans cette th{\`e}se, nous abordons trois questions principales: Tout d'abord, nous {\'e}tudions les solutions pratiques de r{\'e}utilisation permettant de combiner un ensemble choisi d'{\'e}l{\'e}ments logiciels utiles pour la mod{\'e}lisation et la simulation, en incluant aussi bien les mod{\`e}les, les moteurs de simulation, les algorithmes et les outils; Deuxi{\`e}mement, nous nous concentrons sur les questions li{\'e}es {\`a} l'instrumentation; Troisi{\`e}mement, nous {\'e}tudions le probl{\`e}me de l'int{\'e}gration d'{\'e}l{\'e}ments logiciels provenant d'autres simulateurs dans un nouveau simulateur. Pour atteindre ces objectifs, nous {\'e}tudions des techniques avanc{\'e}es de du g{\'e}nie logiciel, tels que le g{\'e}nie logiciel {\`a} base de composants (CBSE) et la programmation orient{\'e}e aspect, sur lesquels nous construisons une solution originale pour la mod{\'e}lisation et la simulation {\`a} l'aide de multiples couches r{\'e}utilisables. Nous avons d{\'e}velopp{\'e} un prototype d'architecture logicielle qui prouve la faisabilit{\'e} de cette solution.

@phdthesis{Rib11,

 hal_id = {tel-00604014},

 url = {http://tel.archives-ouvertes.fr/tel-00604014/en/},

 title = {{Reuse and Scalability in Modeling and Simulation Software Engineering}},

 author = {Ribault, J.},

 abstract = {{L'{\'e}tude d'un syst{\`e}me {\`a} l'aide de simulations informatiques {\`a} {\'e}v{\'e}nements discrets implique plusieurs activit{\'e}s: sp{\'e}ci cation du mod{\`e}le conceptuel, description de l'architecture logicielle du mod{\`e}le, d{\'e}veloppement des logiciels, sc{\'e}narisation de la simulation, instrumentation, plani cation d'exp{\'e}rimentation, con guration des ressources de calcul, ex{\'e}cution, post-traitement et analyse, validation et de v{\'e}ri cation (V\&V). De nombreux {\'e}l{\'e}ments logiciels sont requis pour remplir toutes ces activit{\'e}s. Toutefois, il est fr{\'e}quent de cr{\'e}er un nouveau simulateur {\`a} partir de rien quand on commence une {\'e}tude {\`a} l'aide de simulation. Dans ce cas il est n{\'e}cessaire de d{\'e}velopper de multiples outils prenant en charge les activit{\'e}s de la simulation. Cette th{\`e}se aborde le d{\'e} de la cr{\'e}ation de nouveaux simulateurs tout en r{\'e}utilisant des mod{\`e}les et des outils provenant d'autres simulateurs. En 
 e et, la r{\'e}utilisation de logiciel augmente la abilit{\'e}, est moins sujette aux erreurs, permet une meilleure utilisation des expertises compl{\'e}mentaires, am{\'e}liore la conformit{\'e} aux normes, et acc{\'e}l{\`e}re le d{\'e}veloppement. La r{\'e}utilisation de logiciels peut {\^e}tre appliqu{\'e}e {\`a} toutes les activit{\'e}s de la simulation. Plusieurs probl{\`e}mes doivent {\^e}tre r{\'e}solus pour tirer pleinement pro t de la r{\'e}utilisation. Dans cette th{\`e}se, nous abordons trois questions principales: Tout d'abord, nous {\'e}tudions les solutions pratiques de r{\'e}utilisation permettant de combiner un ensemble choisi d'{\'e}l{\'e}ments logiciels utiles pour la mod{\'e}lisation et la simulation, en incluant aussi bien les mod{\`e}les, les moteurs de simulation, les algorithmes et les outils; Deuxi{\`e}mement, nous nous concentrons sur les questions li{\'e}es {\`a} l'instrumentation; Troisi{\`e}mement, nous {\'e}tudions le probl{\`e}me de l'int{\'e}gration d'{\'e}l{\'e}ments logiciels 
 provenant d'autres simulateurs dans un nouveau simulateur. Pour atteindre ces objectifs, nous {\'e}tudions des techniques avanc{\'e}es de du g{\'e}nie logiciel, tels que le g{\'e}nie logiciel {\`a} base de composants (CBSE) et la programmation orient{\'e}e aspect, sur lesquels nous construisons une solution originale pour la mod{\'e}lisation et la simulation {\`a} l'aide de multiples couches r{\'e}utilisables. Nous avons d{\'e}velopp{\'e} un prototype d'architecture logicielle qui prouve la faisabilit{\'e} de cette solution.}},

 keywords = {simulation; {\'e}v{\`e}nements discrets; aspects; s{\'e}paration des pr{\'e}occupations; instrumentation; mod{\'e}lisation; composant; simulation distribu{\'e}e; r{\'e}utilisation},

 language = {French},

 affiliation = {MASCOTTE - INRIA Sophia Antipolis / Laboratoire I3S - INRIA - Universit{\'e} de Nice Sophia-Antipolis - CNRS : UMR6070},

 school = {Ecole doctorale {STIC}, Universit{\'e} de Nice Sophia-Antipolis},

 type = {THESE},

 year = {2011},

 month = Jan,

 pdf = {http://tel.archives-ouvertes.fr/tel-00604014/PDF/ThesisJudicaelRibaultV4.pdf},

 x-pays = {FR},

 x-editorial-board={no},

 x-proceedings={no},

 x-international-audience={yes} 
 
}

Articles in journal or book chapters

J-C. Bermond, F. Ergincan, and M. Syska. Quisquater Festschrift, volume 6805 of Lecture Notes in Computer Science, chapter Line Directed Hypergraphs, pages 25-34. Springer-Verlag, Berlin Heidelberg, 2011. [PDF ]

Abstract:

In this article we generalize the concept of line digraphs to line dihypergraphs. We give some general properties in particular concerning connectivity parameters of dihypergraphs and their line dihypergraphs, like the fact that the arc connectivity of a line dihypergraph is greater than or equal to that of the original dihypergraph. Then we show that the De Bruijn and Kautz dihypergraphs (which are among the best known bus networks) are iterated line digraphs. Finally we give short proofs that they are highly connected.

@inBook{BES11,

 author= {J-C. Bermond and F. Ergincan and M. Syska},

 chapter = { Line Directed Hypergraphs},

 title={ Quisquater Festschrift},

 publisher= { Springer-Verlag },

 address={Berlin Heidelberg},

 series= {Lecture Notes in Computer Science},

 editor={D. Naccache},

 volume={6805},

 pages={25-34},

 year = {2011},

 PDF={ftp://ftp-sop.inria.fr/mascotte/personnel/Jean-Claude.Bermond/PUBLIS/BES11.pdf},

 abstract={In this article we generalize the concept of line digraphs to line
 dihypergraphs. We give some general properties in particular
 concerning connectivity parameters of dihypergraphs and their line
 dihypergraphs, like the fact that the arc connectivity of a
 line dihypergraph is greater than or equal to that of the original
 dihypergraph. Then we show that the De Bruijn and Kautz dihypergraphs
 (which are among the best known bus networks) are iterated line
 digraphs. Finally we give short proofs that they are
 highly connected.},

 x-editorial-board={yes},

 x-proceedings={yes},

 x-international-audience={yes},

 sorte = "book",

 x-pays = {CA},

 
}

G. A. Wainer, K. Al-Zoubi, O. Dalle, R.C. Hill, S. Mittal, J. L. R. Martin, H. Sarjoughian, L. Touraille, M. K. Traoré, and B. P. Zeigler. Discrete-Event Modeling and Simulation: Theory and Applications, chapter 18 - Standardizing DEVS Simulation Middleware, pages 459-494. Taylor and Francis, 2011. [WWW ]

@inbook{WAD+11a,

 chapter = {18 - Standardizing DEVS Simulation Middleware},

 title = {Discrete-Event Modeling and Simulation: Theory and Applications},

 publisher = {Taylor and Francis},

 year = {2011},

 pages = {459-494},

 editor = {G. Wainer and P. Mosterman},

 author = {G. A. Wainer and K. Al-Zoubi and O. Dalle and R.C. Hill and S. Mittal and J. L. R. Mart\`in and H. Sarjoughian and L. Touraille and M. K. Traor\'e and B. P. Zeigler},

 category = {Multi Modeling and Modeling Formalisms},

 url = {http://cell-devs.sce.carleton.ca/publications/2010/WADHMMSTTZ10},

 x-editorial-board={yes},

 x-proceedings={no},

 x-international-audience={yes},

 sorte = "livres-chap",

 
}

G . Wainer, K. Al-Zoubi, O. Dalle, R. C. Hill, S. Mittal, J. L. R. Martin, H. Sarjoughian, L. Touraille, M. K. Traoré, and B. P. Zeigler. Discrete-Event Modeling and Simulation: Theory and Applications, chapter 17 - Standardizing DEVS model representation, pages 427-458. Taylor and Francis, 2011. [WWW ]

@inbook{WAD+11b,

 chapter = {17 - Standardizing DEVS model representation},

 title = {Discrete-Event Modeling and Simulation: Theory and Applications},

 publisher = {Taylor and Francis},

 year = {2011},

 pages = {427-458},

 editor = {Wainer, G. and Mosterman, P.},

 author = {G . Wainer and K. Al-Zoubi and O. Dalle and R. C. Hill and S. Mittal and J. L. R. Mart\`in and H. Sarjoughian and L. Touraille and M. K. Traor\'e and B. P. Zeigler},

 url = {http://cell-devs.sce.carleton.ca/publications/2010/WADHMMSTTZ10},

 x-editorial-board={yes},

 x-proceedings={no},

 x-international-audience={yes},

 sorte = "livres-chap",

 
}

V. Andova, N. Cohen, and R. Skrekovski. Graph Classes (Dis)satisfying the Zagreb Indices Inequality. MATCH Commun. Math. Comput. Chem., 65(3):647-658, 2011. [PDF ]

Abstract:

Recently Hansen and Vuki\^cevi\'c proved that the inequality $M_1/n \leq M_2/m$, where $M_1$ and $M_2$ are the first and second Zagreb indices, holds for chemical graphs, and Vuki\^cevi\'c and Graovac proved that this also holds for trees. In both works is given a distinct counterexample for which this inequality is false in general. Here, we present some classes of graphs with prescribed degrees, that satisfy $M_1/n \leq M_2/m$: Namely every graph $G$ whose degrees of vertices are in the interval $[c; c + \sqrt c]$ for some integer $c$ satisies this inequality. In addition, we prove that for any $\Delta \geq 5$, there is an infinite family of graphs of maximum degree $\Delta$ such that the inequality is false. Moreover, an alternative and slightly shorter proof for trees is presented, as well as for unicyclic graphs.

@article{ACS11,

 author = {V. Andova and N. Cohen and R. {\v{S}}krekovski},

 title = {Graph Classes (Dis)satisfying the Zagreb Indices Inequality},

 journal = {MATCH Commun. Math. Comput. Chem.},

 year = {2011},

 volume = {65},

 number = {3},

 pages = {647-658},

 abstract = {Recently Hansen and Vuki\^cevi\'c proved that the
 inequality $M_1/n \leq M_2/m$, where $M_1$ and $M_2$ are the first and
 second Zagreb indices, holds for chemical graphs, and Vuki\^cevi\'c
 and Graovac proved that this also holds for trees. In both works is
 given a distinct counterexample for which this inequality is false in
 general. Here, we present some classes of graphs with prescribed
 degrees, that satisfy $M_1/n \leq M_2/m$: Namely every graph $G$ whose
 degrees of vertices are in the interval $[c; c + \sqrt c]$ for some integer $c$ satisies this inequality. In addition, we prove that for
 any $\Delta \geq 5$, there is an infinite family of graphs of maximum
 degree $\Delta$ such that the inequality is false. Moreover, an
 alternative and slightly shorter proof for trees is presented, as
 well as for unicyclic graphs.},

 pdf = {http://www.imfm.si/preprinti/PDF/01108.pdf},

 x-editorial-board={yes},

 x-proceedings={no},

 x-international-audience={yes},

 x-pays = {FR, SI, MK},

 sorte = "rev-int",

 
}

M. Basavaraju, L. S. Chandran, N. Cohen, F. Havet, and T. Müller. Acyclic edge-coloring of planar graphs. SIAM Journal of Discrete Mathematics, 25(2):463--478, 2011. [PDF ]

Abstract:

A proper edge-coloring with the property that every cycle contains edges of at least three distinct colors is called an {\it acyclic edge-coloring}. The {\it acyclic chromatic index} of a graph $G$, denoted $\chi'_a(G)$ is the minimum $k$ such that $G$ admits an {\it acyclic edge-coloring} with $k$ colors. We conjecture that if $G$ is planar and $\Delta(G)$ is large enough then $\chi'_a(G)=\Delta(G)$. We settle this conjecture for planar graphs with girth at least $5$. We also show that $\chi'_a(G)\leq \Delta(G) + 12$ for all planar $G$, which improves a previous result by Fiedorowicz et al.

@article{BCC+11b,

 author = {M. Basavaraju and L. S. Chandran and N. Cohen and F. Havet and T. M\"uller},

 title = {Acyclic edge-coloring of planar graphs },

 journal = {SIAM Journal of Discrete Mathematics},

 volume = {25},

 number = {2},

 year = {2011},

 pages = {463--478},

 abstract = {A proper edge-coloring with the property that every cycle contains edges of
 at least three distinct colors is called an {\it acyclic
 edge-coloring}. The {\it acyclic chromatic index} of a graph $G$,
 denoted $\chi'_a(G)$ is the minimum $k$ such that $G$ admits an {\it
 acyclic edge-coloring} with $k$ colors.
 We conjecture that if $G$ is planar and $\Delta(G)$ is large enough then $\chi'_a(G)=\Delta(G)$.
 We settle this conjecture for planar graphs with girth at least $5$.
 We also show that $\chi'_a(G)\leq \Delta(G) + 12$ for all planar $G$, which improves a previous result by Fiedorowicz et al.},

 pdf = {ftp://ftp-sop.inria.fr/mascotte/Publications/BCC+11.pdf},

 x-editorial-board = {yes},

 x-proceedings = {no},

 x-international-audience = {yes},

 x-pays = {IN},

 
}

J. Beauquier, J. Burman, and S. Kutten. A self-stabilizing Transformer for Population Protocols with Covering. Theoretical Computer Science, 412(33):4247-4259, 2011. [WWW ]

Abstract:

Developing \emph{self-stabilizing} solutions is considered to be more challenging and complicated than developing classical solutions, where a proper initialization of the variables can be assumed. Hence, to ease the task of the developers, some automatic techniques have been proposed to design self-stabilizing algorithms. In this paper, we propose an \emph{automatic transformer} for algorithms in an extended \emph{population protocol model}. Population protocols is a model that was introduced recently for networks with a large number of resource-limited mobile agents. We use a variant of this model. First, we assume agents having characteristics (e.g., moving speed, communication radius) affecting their intercommunication ``speed'', which is reflected by their \emph{cover times}. Second, we assume the existence of a special agent with an unbounded memory, the \emph{base station}. The automatic transformer takes as an input an algorithm solving a \emph{static problem} (and meeting some additional rather natural requirements) and outputs a self-stabilizing algorithm for the same problem. The transformer is built using a \emph{re-execution approach} (the technique consisting of executing an algorithm repeatedly in order to obtain its self-stabilizing version). We show that in the model we use, a transformer based on such an approach is impossible without the assumption of an unbounded memory agent.

@article{BBK11,

 author = {Beauquier, J. and Burman, J. and Kutten, S.},

 title = {A self-stabilizing Transformer for Population Protocols with Covering},

 journal = {Theoretical Computer Science},

 volume = {412},

 number = {33},

 year = {2011},

 pages = {4247-4259},

 abstract = {Developing \emph{self-stabilizing} solutions is considered to be more challenging and complicated than developing classical solutions, where a proper initialization of the variables can be assumed. Hence, to ease the task of the developers, some automatic techniques have been proposed to design self-stabilizing algorithms. In this paper, we propose an \emph{automatic transformer} for algorithms in an extended \emph{population protocol model}. Population protocols is a model that was introduced recently for networks with a large number of resource-limited mobile agents. We use a variant of this model. First, we assume agents having characteristics (e.g., moving speed, communication radius) affecting their intercommunication ``speed'', which is reflected by their \emph{cover times}. Second, we assume the existence of a special agent with an unbounded memory, the \emph{base station}. The automatic transformer takes as an input an algorithm solving a \emph{static problem} (and meeting some additional 
 rather natural requirements) and outputs a self-stabilizing algorithm for the same problem. The transformer is built using a \emph{re-execution approach} (the technique consisting of executing an algorithm repeatedly in order to obtain its self-stabilizing version). We show that in the model we use, a transformer based on such an approach is impossible without the assumption of an unbounded memory agent.},

 url = {http://dx.doi.org/10.1016/j.tcs.2010.09.016},

 x-editorial-board={yes},

 x-proceedings={no},

 x-international-audience={yes},

 x-pays = {IL},

 sorte = "rev-int",

 
}

J.-C. Bermond, Y. M. Chee, N. Cohen, and X. Zhang. The $\alpha$-Arboricity of Complete Uniform Hypergraphs. SIAM Journal on Discrete Mathematics, 25(2):600-610, 2011. [PDF ]

Abstract:

The $\alpha$-arboricity of the complete 3-uniform hypergraph is determined completely.$\alpha$-Acyclicity is an important notion in database theory. The $\alpha$-arboricity of a hypergraph H is the minimum number of $\alpha$-acyclic hypergraphs that partition the edge set of H.

@article{BCC+11a,

 author = {J.-C. Bermond and Y. M. Chee and N. Cohen and X. Zhang},

 title = {The $\alpha$-Arboricity of Complete Uniform Hypergraphs},

 journal = {SIAM Journal on Discrete Mathematics},

 year = {2011},

 volume = {25},

 number = {2},

 pages = {600-610},

 PDF={ftp://ftp-sop.inria.fr/mascotte/Publications/BCCZ11.pdf},

 abstract = {The $\alpha$-arboricity of the complete 3-uniform
 hypergraph is determined completely.$\alpha$-Acyclicity is an important notion in database theory. The $\alpha$-arboricity
 of a hypergraph H is the minimum number of $\alpha$-acyclic hypergraphs that
 partition the edge set of H.},

 x-editorial-board={yes},

 x-international-audience={yes},

 x-proceedings={no},

 x-pays = {SG},

 sorte = "rev-int",

 
}

J-C. Bermond, X. Muñoz, and I. Sau. Traffic Grooming in Bidirectional WDM Ring Networks. Networks, 58(1):20-35, 2011. [WWW ] [PDF ]

Abstract:

We study the minimization of ADMs (Add-Drop Multiplexers) in optical WDM bidirectional rings considering symmetric shortest path routing and all-to-all unitary requests. We precisely formulate the problem in terms of graph decompositions, and state a general lower bound for all the values of the grooming factor $C$ and $N$, the size of the ring. We first study exhaustively the cases $C=1$, $C = 2$, and $C=3$, providing improved lower bounds, optimal constructions for several infinite families, as well as asymptotically optimal constructions and approximations. We then study the case $C>3$, focusing specifically on the case $C = k(k+1)/2$ for some $k \geq 1$. We give optimal decompositions for several congruence classes of $N$ using the existence of some combinatorial designs. We conclude with a comparison of the cost functions in unidirectional and bidirectional WDM rings.

@Article{BMS11,

 author = {J-C. Bermond and X. Mu{\~n}oz and I. Sau},

 title = {{Traffic Grooming in Bidirectional WDM Ring Networks}},

 JOURNAL = {Networks},

 year = {2011},

 volume = {58},

 number = {1},

 pages = {20-35},

 x-pays = {ES},

 sorte = "rev-int",

 url = {http://dx.doi.org/10.1002/net.20410},

 pdf = {http://hal.inria.fr/docs/00/42/91/55/PDF/RR-7080.pdf},

 abstract = {We study the minimization of ADMs (Add-Drop Multiplexers) in optical WDM bidirectional rings considering symmetric shortest path routing and all-to-all unitary requests. We precisely formulate the problem in terms of graph decompositions, and state a general lower bound for all the values of the grooming factor $C$ and $N$, the size of the ring. We first study exhaustively the cases $C=1$, $C = 2$, and $C=3$, providing improved lower bounds, optimal constructions for several infinite families, as well as asymptotically optimal constructions and approximations. We then study the case $C>3$, focusing specifically on the case $C = k(k+1)/2$ for some $k \geq 1$. We give optimal decompositions for several congruence classes of $N$ using the existence of some combinatorial designs. We conclude with a comparison of the cost functions in unidirectional and bidirectional WDM rings.},

 x-editorial-board={yes},

 x-proceedings={yes},

 x-international-audience={yes},

 
}

V. Bilo, M. Flammini, G. Monaco, and L. Moscardelli. On the performances of Nash equilibria in isolation games. Journal of Combinatorial Optimization, 22:378-391, 2011.
Note: Special Issue: Selected Papers from the 15th International Computing and Combinatorics Conference. [WWW ]

Abstract:

We study the performances of Nash equilibria in isolation games, a class of competitive location games recently introduced in Zhao et al. (Proc. of the 19th International Symposium on Algorithms and Computation (ISAAC), pp. 148â159, 2008 ). For all the cases in which the existence of Nash equilibria has been shown, we give tight or asymptotically tight bounds on the prices of anarchy and stability under the two classical social functions mostly investigated in the scientific literature, namely, the minimum utility per player and the sum of the playersâ utilities. Moreover, we prove that the convergence to Nash equilibria is not guaranteed in some of the not yet analyzed cases.

@article{BFM+11,

 author = {Bilo, V. and Flammini, M. and Monaco, G. and Moscardelli, L.},

 title = {On the performances of Nash equilibria in isolation games},

 journal = {Journal of Combinatorial Optimization},

 publisher = {Springer Netherlands},

 issn = {1382-6905},

 pages = {378-391},

 volume = {22},

 issue = {3},

 url = {http://dx.doi.org/10.1007/s10878-010-9300-3},

 note = {Special Issue: Selected Papers from the 15th International Computing and Combinatorics Conference},

 abstract = {We study the performances of Nash equilibria in isolation games, a class of competitive location games recently introduced in Zhao et al. (Proc. of the 19th International Symposium on Algorithms and Computation (ISAAC), pp. 148â159, 2008 ). For all the cases in which the existence of Nash equilibria has been shown, we give tight or asymptotically tight bounds on the prices of anarchy and stability under the two classical social functions mostly investigated in the scientific literature, namely, the minimum utility per player and the sum of the playersâ utilities. Moreover, we prove that the convergence to Nash equilibria is not guaranteed in some of the not yet analyzed cases.},

 year = {2011},

 x-pays = {IT},

 sorte = "rev-int",

 x-editorial-board={yes},

 x-proceedings={no},

 x-international-audience={yes},

 
}

B. Bresar, F. Kardos, J. Katrenic, and G. Semanisin. Minimum $k$-path vertex cover. Discrete Applied Mathematics, 159(12):1189-1195, 2011. [PDF ]

Abstract:

A subset $S$ of vertices of a graph $G$ is called a {\em $k$-path vertex cover} if every path of order $k$ in $G$ contains at least one vertex from $S$. Denote by $\psi_k(G)$ the minimum cardinality of a $k$-path vertex cover in $G$. It is shown that the problem of determining $\psi_k(G)$ is NP-hard for each $k\geq2$, while for trees the problem can be solved in linear time. We investigate upper bounds on the value of $\psi_k(G)$ and provide several estimations and exact values of $\psi_k(G)$. We also prove that $\psi_3(G)\le (2n+m)/6$, for every graph $G$ with $n$ vertices and $m$ edges.

@article{BKK+11,

 author = {Bre{\v{s}}ar, B. and Kardo{\v{s}}, F. and Katreni{\v{c}}, J. and Semani{\v{s}}in, G. },

 title = {Minimum $k$-path vertex cover},

 journal = {Discrete Applied Mathematics},

 year = {2011},

 volume = {159},

 number = {12},

 pages = {1189-1195},

 abstract = {A subset $S$ of vertices of a graph $G$ is called a {\em $k$-path vertex cover} if every path of order $k$ in $G$ contains at least one vertex from $S$. Denote by $\psi_k(G)$ the minimum cardinality of a $k$-path vertex cover in $G$. It is shown that the problem of determining $\psi_k(G)$ is NP-hard for each $k\geq2$, while for trees the problem can be solved in linear time. 
 We investigate upper bounds on the value of $\psi_k(G)$ and provide several estimations and exact values of $\psi_k(G)$. We also prove that $\psi_3(G)\le (2n+m)/6$, for every graph $G$ with $n$ vertices and $m$ edges. },

 pdf = {ftp://ftp-sop.inria.fr/mascotte/Publications/BKK+11.pdf},

 x-editorial-board={yes},

 x-proceedings={no},

 x-international-audience={yes},

 x-pays = {SI, SK},

 sorte = "rev-int",

 
}

C. Caillouet, S. Pérennes, and H. Rivano. Framework for Optimizing the Capacity of Wireless Mesh Networks. Computer Communications, 34(13):1645-1659, 2011. [WWW ]
Keywords: Wireless mesh networks, capacity, routing, scheduling, linear programming, column and cut generation..

Abstract:

In this paper, we address the problem of computing the transport capacity of Wireless Mesh Networks (WMNs) dedicated to Internet access. Routing and transmission scheduling have a major impact on the capacity provided to the clients. A cross-layer optimization of these problems allows the routing to take into account contentions due to radio interference. We present a generic Mixed Integer Linear Programing description of the congurations of a given WMN, addressing gateway placement, routing, and scheduling optimizations. We then develop new optimization models that can take into account a large variety of radio interference models, and QoS requirements on the routing. We also provide efficient resolution methods that deal with realistic size instances. It allows to work around the combinatoric of simultaneously achievable transmissions and point out a critical region in the network bounding the network achievable capacity. Based upon strong duality arguments, it is then possible to restrict the computation to a bounded area. It allows for computing solutions very efficiently on large networks.

@article{CPR11,

 author = {C. Caillouet and S. P\'erennes and H. Rivano},

 title = {{Framework for Optimizing the Capacity of Wireless Mesh Networks}},

 journal = {{Computer Communications}},

 publisher = {Elsevier},

 year = {2011},

 volume = {34},

 number = {13},

 pages = {1645-1659},

 keywords = {Wireless mesh networks, capacity, routing, scheduling, linear programming, column and cut generation.},

 url = {http://dx.doi.org/10.1016/j.comcom.2011.03.002},

 #url = {http://hal.inria.fr/inria-00572967/en},

 abstract = {In this paper, we address the problem of computing the transport capacity of Wireless Mesh Networks (WMNs) dedicated to Internet access. Routing and transmission scheduling have a major impact on the capacity provided to the clients. A cross-layer optimization of these problems allows the routing to take into account contentions due to radio interference. We present a generic Mixed Integer Linear Programing description of the congurations of a given WMN, addressing gateway placement, routing, and scheduling optimizations. We then develop new optimization models that can take into account a large variety of radio interference models, and QoS requirements on the routing. We also provide efficient resolution methods that deal with realistic size instances. It allows to work around the combinatoric of simultaneously achievable transmissions and point out a critical region in the network bounding the network achievable capacity. Based upon strong duality arguments, it is then possible to restrict the 
 computation to a bounded area. It allows for computing solutions very efficiently on large networks.},

 x-editorial-board={yes},

 x-proceedings={no},

 x-international-audience={yes},

 sorte = "rev-int",

 
}

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:

In the classical cop and robber game, two players, the cop C and the robber R, move alternatively along edges of a finite graph G=(V,E). The cop captures the robber if both players are on the same vertex at the same moment of time. A graph G is called cop win if the cop always captures the robber after a finite number of steps. Nowakowski, Winkler (1983) and Quilliot (1983) characterized the cop-win graphs as graphs admitting a dismantling scheme. In this paper, we characterize in a similar way the cop-win graphs in the game in which the cop and the robber move at different speeds s' and s, s'<= s. We also investigate several dismantling schemes necessary or sufficient for the cop-win graphs in the game in which the robber is visible only every k moves for a fixed integer k>1. We characterize the graphs which are cop-win for any value of k.

@article{CCN+11,

 author = {Chalopin, J. and Chepoi, V. and Nisse, N. and Vax\`es, Y.},

 title = {Cop and robber games when the robber can hide and ride},

 journal = {SIAM Journal of Discrete Maths.},

 year = {2011},

 volume = {25},

 number = {1},

 pages = {333-359},

 abstract = {In the classical cop and robber game, two players, the cop
 C and the robber R, move alternatively along edges of a finite graph
 G=(V,E). The cop captures the robber if both players are on the same
 vertex at the same moment of time. A graph G is called cop win if the
 cop always captures the robber after a finite number of
 steps. Nowakowski, Winkler (1983) and Quilliot (1983) characterized
 the cop-win graphs as graphs admitting a dismantling scheme. In this
 paper, we characterize in a similar way the cop-win graphs in the game
 in which the cop and the robber move at different speeds s' and s,
 s'<= s. We also investigate several dismantling schemes necessary or
 sufficient for the cop-win graphs in the game in which the robber is
 visible only every k moves for a fixed integer k>1. We characterize
 the graphs which are cop-win for any value of k.},

 url = {http://hal.archives-ouvertes.fr/inria-00448243/fr/},

 pdf = {http://hal.archives-ouvertes.fr/docs/00/44/82/43/PDF/RR-7178.pdf},

 x-editorial-board={yes},

 x-proceedings={no},

 x-international-audience={yes},

 
}

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:

We consider a variant of the graph searching games that models the routing reconfiguration problem in WDM networks. In the digraph processing game, a team of agents aims at {\it processing}, or clearing, the vertices of a digraph~$D$. We are interested in two different measures: 1) the total number of agents used, and 2) the total number of vertices occupied by an agent during the processing of $D$. These measures respectively correspond to the maximum number of simultaneous connections interrupted and to the total number of interruptions during a routing reconfiguration in a WDM network. Previous works have studied the problem of independently minimizing each of these parameters. In particular, the corresponding minimization problems are APX-hard, and the first one is known not to be in APX. In this paper, we give several complexity results and study tradeoffs between these conflicting objectives. In particular, we show that minimizing one of these parameters while the other is constrained is NP-complete. Then, we prove that there exist some digraphs for which minimizing one of these objectives arbitrarily impairs the quality of the solution for the other one. We show that such bad tradeoffs may happen even for a basic class of digraphs. On the other hand, we exhibit classes of graphs for which good tradeoffs can be achieved. We finally detail the relationship between this game and the routing reconfiguration problem. In particular, we prove that any instance of the processing game, i.e. any digraph, corresponds to an instance of the routing reconfiguration problem.

@Article{CCM+11,

 author = {N. Cohen and D. Coudert and D. Mazauric and N. Nepomuceno and N. Nisse},

 title = {Tradeoffs in process strategy games with application in the {WDM} reconfiguration problem},

 journal = {Theoretical Computer Science (TCS)},

 year = {2011},

 volume = {412},

 number = {35},

 pages = {4675-4687},

 month = aug,

 url = {http://dx.doi.org/10.1016/j.tcs.2011.05.002},

 pdf = {http://hal.inria.fr/docs/00/59/25/07/PDF/paper-noformat.pdf},

 abstract = { We consider a variant of the graph searching games that models the
 routing reconfiguration problem in WDM networks. In the digraph
 processing game, a team of agents aims at {\it processing}, or
 clearing, the vertices of a digraph~$D$. We are interested in two
 different measures: 1) the total number of agents used, and 2) the
 total number of vertices occupied by an agent during the processing
 of $D$. These measures respectively correspond to the maximum number
 of simultaneous connections interrupted and to the total number of
 interruptions during a routing reconfiguration
 in a WDM network.
 
 Previous works have studied the problem of independently minimizing
 each of these parameters. In particular, the
 corresponding minimization problems are APX-hard, and the first one
 is known not to be in APX. In this paper, we give several
 complexity results and study tradeoffs between these conflicting
 objectives. In particular, we show that minimizing one of these
 parameters while the other is constrained is NP-complete. Then, we
 prove that there exist some digraphs for which minimizing one of
 these objectives arbitrarily impairs the quality of the solution for
 the other one. We show that such bad tradeoffs may happen even for a
 basic class of digraphs. On the other hand, we exhibit classes of
 graphs for which good tradeoffs can be achieved. We finally detail
 the relationship between this game and the routing reconfiguration
 problem. In particular, we prove that any instance of the processing
 game, i.e. any digraph, corresponds to an instance of the routing
 reconfiguration problem.},

 x-editorial-board={yes},

 x-proceedings={no},

 x-international-audience={yes},

 x-pays={DK},

 sorte = "rev-int",

 
 
}

N. Cohen and F. Havet. Linear and 2-Frugal Choosability of Graphs of Small Maximum Average Degree. Graphs and Combinatorics, 27(6):831-849, 2011. [WWW ] [PDF ]

Abstract:

A proper vertex colouring of a graph $G$ is {\it 2-frugal} (resp. {\it linear}) if the graph induced by the vertices of any two colour classes is of maximum degree 2 (resp. is a forest of paths). A graph $G$ is {\it 2-frugally} (resp. {\it linearly}) {\it $L$-colourable} if for a given list assignment $L:V(G)\mapsto 2^{\mathbb N}$, there exists a 2-frugal (resp. linear) colouring $c$ of $G$ such that $c(v)\in L(v)$ for all $v\in V(G)$. If $G$ is 2-frugally (resp. linearly) $L$-list colourable for any list assignment such that $|L(v)|\ge k$ for all $v\inV(G)$, then $G$ is {\it 2-frugally} (resp. {\it linearly}) {\it $k$-choosable}. In this paper, we improve some bounds on the 2-frugal choosability and linear choosability of graphs with small maximum average degree.

@article{CoHa11,

 author = {N. Cohen and F. Havet},

 title = {Linear and 2-Frugal Choosability of Graphs of Small Maximum Average Degree},

 journal = {Graphs and Combinatorics},

 volume = {27},

 number = {6},

 year = {2011},

 pages = {831-849},

 abstract = {
 A proper vertex colouring of a graph $G$ is {\it 2-frugal} (resp. {\it linear}) if the graph induced by the vertices of any two colour classes is of maximum degree 2 (resp. is a forest of paths). A graph $G$ is {\it 2-frugally} (resp. {\it linearly}) {\it $L$-colourable} if for a given list assignment $L:V(G)\mapsto 2^{\mathbb N}$, there exists a 2-frugal (resp. linear) colouring $c$ of $G$ such that $c(v)\in L(v)$ for all $v\in V(G)$. If $G$ is 2-frugally (resp. linearly) $L$-list colourable for any list assignment such that $|L(v)|\ge k$ for all $v\inV(G)$, then $G$ is {\it 2-frugally} (resp. {\it linearly}) {\it $k$-choosable}. In this paper, we improve some bounds on the 2-frugal choosability and linear choosability of graphs with small maximum average degree.},

 URL={http://hal.inria.fr/inria-00459692/},

 PDF = {http://hal.inria.fr/docs/00/45/96/92/PDF/RR-7213.pdf},

 sorte = {rev-int},

 x-editorial-board={yes},

 x-proceedings={no},

 x-international-audience={yes},

 
}

D. Coudert, F. Giroire, and I. Sau. Circuits in graphs through a prescribed set of ordered vertices. Journal of Interconnection Networks (JOIN), 11(3-4):121-141, 2011. [WWW ] [PDF ]

Abstract:

A \emph{circuit} in a simple undirected graph $G=(V,E)$ is a sequence of vertices $\{v_1,v_2,\ldots,v_{k+1}\}$ such that $v_1=v_{k+1}$ and $\{v_i,v_{i+1}\} \in E$ for $i=1,\ldots,k$. A circuit $C$ is said to be \emph{edge-simple} if no edge of $G$ is used twice in $C$. In this article we study the following problem: which is the largest integer $k$ such that, given any subset of $k$ ordered vertices of a graph $G$, there exists an edge-simple circuit visiting the $k$ vertices in the prescribed order? We first study the case when $G$ has maximum degree at most 3, establishing the value of $k$ for several subcases, such as when $G$ is planar or 3-vertex-connected. Our main result is that $k=10$ in infinite square grids. To prove this, we introduce a methodology based on the notion of core graph, in order to reduce the number of possible vertex configurations, and then we test each one of the resulting configurations with an Integer Linear Program (ILP) solver.

@article{CGS11,

 author = {D. Coudert and F. Giroire and I. Sau},

 title = {Circuits in graphs through a prescribed set of ordered vertices},

 journal = {Journal of Interconnection Networks (JOIN)},

 year = {2011},

 volume = {11},

 number = {3-4},

 pages = {121-141},

 abstract = {A \emph{circuit} in a simple undirected graph $G=(V,E)$ is a sequence of vertices $\{v_1,v_2,\ldots,v_{k+1}\}$ such that $v_1=v_{k+1}$ and $\{v_i,v_{i+1}\} \in E$ for $i=1,\ldots,k$. A circuit $C$ is said to be \emph{edge-simple} if no edge of $G$ is used twice in $C$. In this article we study the following problem: which is the largest integer $k$ such that, given any subset of $k$ ordered vertices of a graph $G$, there exists an edge-simple circuit visiting the $k$ vertices in the prescribed order? We first study the case when $G$ has maximum degree at most 3, establishing the value of $k$ for several subcases, such as when $G$ is planar or 3-vertex-connected. Our main result is that $k=10$ in infinite square grids. To prove this, we introduce a methodology based on the notion of core graph, in order to reduce the number of possible vertex configurations, and then we test each one of the resulting configurations with an Integer Linear Program (ILP) solver.},

 url = {http://dx.doi.org/10.1142/S0219265910002763},

 pdf = {http://hal.inria.fr/docs/00/58/55/61/PDF/join-final-noformat.pdf},

 x-editorial-board={yes},

 x-proceedings={no},

 x-international-audience={yes},

 
}

D. Coudert and J-S. Sereni. Characterization of graphs and digraphs with small process number. Discrete Applied Mathematics (DAM), 159(11):1094-1109, July 2011. [WWW ] [PDF ]

Abstract:

We introduce the process number of a digraph as a tool to study rerouting issues in \wdm networks. This parameter is closely related to the vertex separation (or pathwidth). We consider the recognition and the characterization of (di)graphs with small process number. In particular, we give a linear time algorithm to recognize (and process) graphs with process number at most $2$, along with a characterization in terms of forbidden minors, and a structural description. As for digraphs with process number $2$, we exhibit a characterization that allows one to recognize (and process) them in polynomial time.

@article{CoSe11,

 author = {D. Coudert and J-S. Sereni},

 title = {Characterization of graphs and digraphs with small process number},

 journal = {Discrete Applied Mathematics (DAM)},

 year = {2011},

 volume = {159},

 number = {11},

 pages = {1094-1109},

 month = {jul},

 abstract = {We introduce the process number of a digraph as a tool to study
 rerouting issues in \wdm networks. This parameter is closely related
 to the vertex separation (or pathwidth). We consider the recognition
 and the characterization of (di)graphs with small process number. In
 particular, we give a linear time algorithm to recognize (and
 process) graphs with process number at most $2$, along with a
 characterization in terms of forbidden minors, and a structural
 description. As for digraphs with process number $2$, we exhibit a
 characterization that allows one to recognize (and process) them in
 polynomial time.},

 url = {http://dx.doi.org/10.1016/j.dam.2011.03.010},

 pdf = {http://hal.inria.fr/docs/00/58/77/17/PDF/dam-noformat.pdf},

 x-editorial-board={yes},

 x-proceedings={no},

 x-international-audience={yes},

 x-pays={},

 sorte = "rev-int",

 
}

J. Czap, S. Jendrol', and F. Kardos. Facial parity edge colouring. Ars Mathematica Contemporanea, 4(2):255-269, 2011. [PDF ]

Abstract:

A \emph{facial parity edge colouring} of a connected bridgeless plane graph is such an edge colouring in which no two face-adjacent edges (consecutive edges of a facial walk of some face) receive the same colour, in addition, for each face $\alpha$ and each colour $c$, either no edge or an odd number of edges incident with $\alpha$ is coloured with $c$. From Vizing's theorem it follows that every $3$-connected plane graph has a such colouring with at most $\Delta^* +1$ colours, where $\Delta^* $ is the size of the largest face. In this paper we prove that any connected bridgeless plane graph has a facial parity edge colouring with at most $92$ colours.

@article{CJK11,

 author = {Czap, J. and S. Jendrol' and Kardo{\v{s}}, F. },

 title = {Facial parity edge colouring},

 journal = {Ars Mathematica Contemporanea},

 year = {2011},

 volume = {4},

 number = {2},

 pages = {255-269},

 abstract = {A \emph{facial parity edge colouring} of a connected bridgeless plane graph is such an edge colouring in which no two face-adjacent edges (consecutive edges of a facial walk of some face) receive the same colour, in addition, for each face $\alpha$ and each colour $c$, either no edge or an odd number of edges incident with $\alpha$ is coloured with $c$. From Vizing's theorem it follows that every $3$-connected plane graph has a such colouring with at most $\Delta^* +1$ colours, where $\Delta^* $ is the size of the largest face. In this paper we prove that any connected bridgeless plane graph has a facial parity edge colouring with at most $92$ colours. },

 pdf = {ftp://ftp-sop.inria.fr/mascotte/Publications/CJK11.pdf},

 x-editorial-board={yes},

 x-proceedings={no},

 x-international-audience={yes},

 x-pays = {SK},

 sorte = "rev-int",

 
}

J. Czap, S. Jendrol', and F. Kardos. On the strong parity chromatic number. Discussiones Mathematicae Graph Theory, 31:587-600, 2011. [PDF ]

Abstract:

A vertex colouring of a 2-connected plane graph $G$ is a strong parity vertex colouring if for every face $f$ and each colour $c$, the number of vertices incident with $f$ coloured by $c$ is either zero or odd. Czap et al. [Discrete Math. 311 (2011) 512Â520] proved that every 2-connected plane graph has a proper strong parity vertex colouring with at most 118 colours. In this paper we improve this upper bound for some classes of plane graphs

@article{CJKa11,

 author = {Czap, J. and S. Jendrol' and Kardo{\v{s}}, F. },

 title = {On the strong parity chromatic number},

 journal = {Discussiones Mathematicae Graph Theory},

 year = {2011},

 volume = {31},

 number = {},

 pages = {587-600},

 abstract = {A vertex colouring of a 2-connected plane graph $G$ is a strong parity vertex colouring if for every face $f$ and each colour $c$, the number of vertices incident with $f$ coloured by $c$ is either zero or odd. Czap et al. [Discrete Math. 311 (2011) 512Â520] proved that every 2-connected plane graph has a proper strong parity vertex colouring with at most 118 colours. In this paper we improve this upper bound for some classes of plane graphs },

 pdf = {ftp://ftp-sop.inria.fr/mascotte/Publications/CJKa11.pdf},

 x-editorial-board={yes},

 x-proceedings={no},

 x-international-audience={yes},

 x-pays = {SK},

 sorte = "rev-int",

 
}

J. Czap, S. Jendrol', F. Kardos, and J. Miskuf. Looseness of Plane Graphs. Graphs and Combinatorics, 27(1):73-85, 2011. [PDF ]

Abstract:

A face of a vertex coloured plane graph is called {\em loose} if the number of colours used on its vertices is at least three. The {\em looseness} of a plane graph $G$ is the minimum $k$ such that any surjective $k$-colouring involves a loose face. In this paper we prove that the looseness of a connected plane graph $G$ equals the maximum number of vertex disjoint cycles in a dual graph $G^*$ increased by 2. We also show upper and lower bounds on the looseness of graphs based on the number of vertices, the edge connectivity, and the girth of the dual graph. These bounds improve the result of Negami for the looseness of plane triangulations. We also present infinite classes of graphs where the equalities are attained.

@article{CJK+11,

 author = {Czap, J. and S. Jendrol' and Kardo{\v{s}}, F. and Mi{\v{s}}kuf, J. },

 title = {Looseness of Plane Graphs},

 journal = {Graphs and Combinatorics},

 year = {2011},

 volume = {27},

 number = {1},

 pages = {73-85},

 abstract = {A face of a vertex coloured plane graph is called {\em loose} if the number of colours used on its vertices is at least three. The {\em looseness} of a plane graph $G$ is the minimum $k$ such that any surjective $k$-colouring involves a loose face.
 In this paper we prove that the looseness of a connected plane graph $G$ equals the maximum number of vertex disjoint cycles in a dual graph $G^*$ increased by 2. We also show upper and lower bounds on the looseness of graphs based on the number of vertices, the edge connectivity, and the girth of the dual graph. These bounds improve the result of Negami for the looseness of plane triangulations.
 We also present infinite classes of graphs where the equalities are attained. },

 pdf = {ftp://ftp-sop.inria.fr/mascotte/Publications/CJK+11.pdf},

 x-editorial-board={yes},

 x-proceedings={no},

 x-international-audience={yes},

 x-pays = {SK},

 sorte = "rev-int",

 
}

G. D'Angelo, Gabriele Di Stefano, Alfredo Navarra, and Cristina Pinotti. Recoverable Robust Timetables: An Algorithmic Approach on Trees. IEEE Transactions on Computers, 60(3):433 - 446, March 2011. [WWW ] [PDF ]

Abstract:

In the context of scheduling and timetabling, we study a challenging combinatorial problem which is very interesting for both practical and theoretical points of view. The motivation behind it is to cope with scheduled activities which might be subject to unavoidable disruptions, such as delays, occurring during the operational phase. The idea is to preventively plan some extra time for the scheduled activities in order to be "prepared" if a delay occurs, and absorb it without the necessity of rescheduling all the activities from scratch. This realizes the concept of designing robust timetables. During the planning phase, one should also consider recovery features that might be applied at runtime if disruptions occur. This leads to the concept of recoverable robust timetables. In this new concept, it is assumed that recovery capabilities are given as input along with the possible disruptions that must be considered. The main objective is the minimization of the overall needed time. The quality of a robust timetable is measured by the price of robustness, i.e., the ratio between the cost of the robust timetable and that of a nonrobust optimal timetable. We show that finding an optimal solution for this problem is NP-hard even though the topology of the network, which models dependencies among activities, is restricted to trees. However, we manage to design a paeudopolynomial time algorithm based on dynamic programming and apply it on both random networks and real case scenarios provided by Italian railways. We evaluate the effect of robustness on the scheduling of the activities and provide the price of robustness with respect to different scenarios. We experimentally show the practical effectiveness and efficiency of the proposed algorithm.

@article{DDN+11,

 hal_id = {hal-00643980},

 url = {http://hal.inria.fr/hal-00643980/en/},

 title = {{Recoverable Robust Timetables: An Algorithmic Approach on Trees}},

 author = {G. D'Angelo and Di Stefano, Gabriele and Navarra, Alfredo and Pinotti, Cristina},

 abstract = {{In the context of scheduling and timetabling, we study a challenging combinatorial problem which is very interesting for both practical and theoretical points of view. The motivation behind it is to cope with scheduled activities which might be subject to unavoidable disruptions, such as delays, occurring during the operational phase. The idea is to preventively plan some extra time for the scheduled activities in order to be "prepared" if a delay occurs, and absorb it without the necessity of rescheduling all the activities from scratch. This realizes the concept of designing robust timetables. During the planning phase, one should also consider recovery features that might be applied at runtime if disruptions occur. This leads to the concept of recoverable robust timetables. In this new concept, it is assumed that recovery capabilities are given as input along with the possible disruptions that must be considered. The main objective is the minimization of the overall needed time. The quality 

of a robust timetable is measured by the price of robustness, i.e., the ratio between the cost of the robust timetable and that of a nonrobust optimal timetable. We show that finding an optimal solution for this problem is NP-hard even though the topology of the network, which models dependencies among activities, is restricted to trees. However, we manage to design a paeudopolynomial time algorithm based on dynamic programming and apply it on both random networks and real case scenarios provided by Italian railways. We evaluate the effect of robustness on the scheduling of the activities and provide the price of robustness with respect to different scenarios. We experimentally show the practical effectiveness and efficiency of the proposed algorithm.}},

 language = {English},

 publisher = {IEEE},

 pages = {433 - 446},

 journal = {IEEE Transactions on Computers},

 volume = {60},

 number = {3 },

 doi = {10.1109/TC.2010.142 },

 year = {2011},

 month = Mar,

 pdf = {http://hal.inria.fr/hal-00643980/PDF/RobustTree.pdf},

 x-pays = {IT},

 x-editorial-board={yes},

 x-proceedings={no},

 x-international-audience={yes},

 sorte = "rev-int",

 
}

O. Dalle. Should Simulation Products Use Software Engineering Techniques or Should They Reuse Products of Software Engineering? -- Part 1. Modeling & Simulation Magazine, 11(3), 07 2011.
Note: Online publication. [WWW ] [PDF ]

Abstract:

This two-part article addresses the issues concerning the building of new simulation software by either reusing existing general purpose software products and frameworks or by writing the simulation software from scratch. As a means of discussing the use of existing software, this first part escribes a selected list of such existing software: the Eclipse IDE as graphical user front-end, Maven for the management and building of projects, Bonita for supporting simulation workflows, Ruby on Rails and its Hobo extension to provide online persistence, and the Fractal Component Model for supporting the popular Component-Based Modeling \& Simulation approach. The second part, to be published in the next issue of the \emph{M\&S Magazine}, will further explore some interesting features found in the selected software solutions, and discuss their benefits when applied to simulation.

@article{Dal11a,

 author = {O. Dalle},

 title = {Should Simulation Products Use Software Engineering Techniques or Should They Reuse Products of Software Engineering? -- Part 1},

 journal = {Modeling \& Simulation Magazine},

 publisher = {Sage Publishers},

 year = {2011},

 volume = {11},

 number = {3},

 month = {07},

 note = {Online publication},

 url = {http://hal.inria.fr/inria-00638553},

 PDF = {ftp://ftp-sop.inria.fr/mascotte/Publications/Dal11.pdf},

 abstract = {This two-part article addresses the issues concerning the building
 of new simulation software by either reusing existing general purpose software
 products and frameworks or by writing the simulation software from scratch.
 As a means of discussing the use of existing software, this first part
 escribes a selected list of such existing software: the Eclipse IDE as
 graphical user front-end, Maven for the management and building of projects,
 Bonita for supporting simulation workflows, Ruby on Rails and its Hobo
 extension to provide online persistence, and the Fractal Component Model for
 supporting the popular Component-Based Modeling \& Simulation approach. The
 second part, to be published in the next issue of the \emph{M\&S Magazine},
 will further explore some interesting features found in the selected software
 solutions, and discuss their benefits when applied to simulation. },

 x-editorial-board={no},

 x-proceedings={no},

 x-international-audience={yes},

 sorte = "conf-int",

 
}

O. Dalle. Should Simulation Products Use Software Engineering Techniques or Should They Reuse Products of Software Engineering? -- Part 2. Modeling & Simulation Magazine, 11(4), 10 2011.
Note: Online publication. [WWW ]

Abstract:

@article{Dal11b,

 author = {O. Dalle},

 title = {Should Simulation Products Use Software Engineering Techniques or Should They Reuse Products of Software Engineering? -- Part 2},

 journal = {Modeling \& Simulation Magazine},

 publisher = {Sage Publishers},

 year = {2011},

 volume = {11},

 number = {4},

 month = {10},

 note = {Online publication},

 url = {http://hal.inria.fr/inria-00638555_v1/},

 abstract = {This two-part article addresses the issues concerning the building
 of new simulation software by either reusing existing general purpose software
 products and frameworks or by writing the simulation software from scratch.
 As a means of discussing the use of existing software, this first part
 escribes a selected list of such existing software: the Eclipse IDE as
 graphical user front-end, Maven for the management and building of projects,
 Bonita for supporting simulation workflows, Ruby on Rails and its Hobo
 extension to provide online persistence, and the Fractal Component Model for
 supporting the popular Component-Based Modeling \& Simulation approach. The
 second part, to be published in the next issue of the \emph{M\&S Magazine},
 will further explore some interesting features found in the selected software
 solutions, and discuss their benefits when applied to simulation. },

 x-editorial-board={no},

 x-proceedings={no},

 x-international-audience={yes},

 sorte = "conf-int",

 
}

R. Erman, F. Havet, B. Lidicky, and O. Pangrác. 5-colouring graphs with 4 crossings. SIAM Journal on Discrete Mathematics, 25(1):401-422, 2011. [PDF ]

Abstract:

We disprove a conjecture of Oporowski and Zhao stating that every graph with crossing number at most 5 and clique number at most 5 is 5-colourable. However, we show that every graph with crossing number at most 4 and clique number at most 5 is 5-colourable. We also show some colourability results on graphs that can be made planar by removing few edges. In particular, we show that if there exists three edges whose removal leaves the graph planar then it is $5$-colourable.

@article{EHL+11,

 author = {R. Erman and F. Havet and B. Lidick{\'{y}} and O. Pangr\'ac},

 title = {5-colouring graphs with 4 crossings},

 year = {2011},

 volume = {25},

 number = {1},

 pages = {401-422},

 journal={SIAM Journal on Discrete Mathematics},

 abstract = {We disprove a conjecture of
 Oporowski and Zhao stating that every graph with crossing number at most 5
 and clique number at most 5 is 5-colourable.
 However, we show that every graph with crossing number at most 4 and
 clique number at most 5 is 5-colourable.
 We also show some colourability results on graphs that can
 be made planar by removing few edges.
 In particular, we show that if there exists three edges whose removal
 leaves the graph planar then it is $5$-colourable.},

 pdf = {ftp://ftp-sop.inria.fr/mascotte/Publications/EHL+11.pdf},

 x-editorial-board={yes},

 x-proceedings={yes},

 x-international-audience={yes},

 x-pays={CZ,SI},

 sorte = "rev-int",

 
}

L. Esperet, F. Kardos, A. D. King, D. Král', and S. Norine. Exponentially many perfect matchings in cubic graphs. Advances in Mathematics, 227(4):1646-1664, 2011. [PDF ]

Abstract:

We show that every cubic bridgeless graph $G$ has at least $2^{|V(G)|/3656}$ perfect matchings. This confirms an old conjecture of Lov{\'{a}}sz and Plummer.

@article{EKK+11,

 author = {Esperet, L. and Kardo{\v{s}}, F. and King, A. D. and Kr{\'{a}}l', D. and Norine, S. },

 title = {Exponentially many perfect matchings in cubic graphs},

 journal = {Advances in Mathematics},

 year = {2011},

 volume = {227},

 number = {4},

 pages = {1646-1664},

 abstract = {We show that every cubic bridgeless graph $G$ has at least $2^{|V(G)|/3656}$ perfect matchings. This confirms an old conjecture of Lov{\'{a}}sz and Plummer. },

 pdf = {ftp://ftp-sop.inria.fr/mascotte/Publications/EKK+11.pdf},

 x-editorial-board={yes},

 x-proceedings={no},

 x-international-audience={yes},

 x-pays = {CZ, SK, US},

 sorte = "rev-int",

 
}

P. Giabbanelli and J. G. Peters. Complex networks and epidemics. Technique et Science Informatiques, 20(2):181-212, 2011.

Abstract:

The study of spreading processes, such as infectious diseases or computer worms, is well-motivated by its financial impact and humanitarian aspects. A vast amount of research has emerged through the theory of complex networks, that sheds light on the properties found in a wide range of "real-world" networks. We review these properties in the context of spreads, with an emphasis on the settings underlying some of the major claims in the literature such as whether or not a scale-free network is particularly prone to spreading phenomena. Stochastic models have been well studied in the literature, and thus we focus on deterministic models, highlighting the connections between the two approaches. Finally, we classify immunization strategies into four categories, which allows comparisons on common features from a computer science perspective. Several topics for future work are suggested. For example, it remains open whether immunization strategies, such as those based on degree, benefit from complex network properties.

@article{GiPe10,

 author="P. Giabbanelli and J. G. Peters",

 title="Complex networks and epidemics",

 journal="Technique et Science Informatiques",

 year={2011},

 volume = {20},

 number = {2},
pages = {181-212},

 month = {},

 abstract={The study of spreading processes, such as infectious diseases or 
 computer worms, is well-motivated by its financial impact and 
 humanitarian aspects. A vast amount of research has emerged through the 
 theory of complex networks, that sheds light on the properties found in a
 wide range of "real-world" networks. We review these properties in the 
 context of spreads, with an emphasis on the settings underlying some of 
 the major claims in the literature such as whether or not a scale-free 
 network is particularly prone to spreading phenomena. Stochastic models 
 have been well studied in the literature, and thus we focus on 
 deterministic models, highlighting the connections between the two 
 approaches. Finally, we classify immunization strategies into four 
 categories, which allows comparisons on common features from a computer 
 science perspective. Several topics for future work are suggested. For 
 example, it remains open whether immunization strategies, such as those 
 based on degree, benefit from complex network properties.},

 doi = {http://dx.doi.org/10.3166/tsi.30.181-212},

 x-editorial-board={yes},

 x-proceedings={no},

 x-international-audience={yes},

 sorte = "rev-nat",

 
}

F. Havet, S. Jendrol', R. Soták, and E. Skrabul'áková. Facial non-repetitive edge-colouring of plane graphs. Journal of Graph Theory, 66(1):38--48, 2011. [WWW ] [PDF ]

Abstract:

A sequence $r_1,r_2,\dots,r_{2n}$ such that $r_i=r_{n+i}$ for all $1\leq i \leq n$, is called a {\em repetition}. A sequence $S$ is called {\em non-repetitive} if no {\it block} (i.e. subsequence of consecutive terms of $S$) is a repetition. Let $G$ be a graph whose edges are coloured. A trail is called {\em non-repetitive} if the sequence of colours of its edges is non-repetitive. If $G$ is a plane graph, a {\em facial non-repetitive edge-colouring} of $G$ is an edge-colouring such that any {\it facial trail} (i.e. trail of consecutive edges on the boundary walk of a face) is non-repetitive. We denote $\pi'_f(G)$ the minimum number of colours of a facial non-repetitive edge-colouring of $G$. In this paper, we show that $\pi'_f(G)\leq 8$ for any plane graph $G$. We also get better upper bounds for $\pi'_f(G)$ in the cases when $G$ is a tree, a plane triangulation, a simple $3$-connected plane graph, a hamiltonian plane graph, an outerplanar graph or a Halin graph. The bound $4$ for trees is tight.

@article{HJS+11,

 author = {F. Havet and S. Jendrol' and R. Sot{\'a}k and E. {\v{S}}krabul'{\'a}kov{\'a}},

 title = {Facial non-repetitive edge-colouring of plane graphs},

 journal = {Journal of Graph Theory},

 volume = {66},

 number = {1},

 year = {2011},

 pages = {38--48},

 abstract = {A sequence $r_1,r_2,\dots,r_{2n}$ such that $r_i=r_{n+i}$ for all $1\leq i \leq n$, is called a {\em repetition}. A sequence $S$ is called {\em non-repetitive} if no {\it block} (i.e. subsequence of consecutive terms of $S$) is a repetition. Let $G$ be a graph whose edges are coloured. A trail is called {\em non-repetitive} if the sequence of colours of its edges is non-repetitive. If $G$ is a plane graph, a {\em facial non-repetitive edge-colouring} of $G$ is an edge-colouring such that any {\it facial trail} (i.e. trail of consecutive edges on the boundary walk of a face) is non-repetitive. We denote $\pi'_f(G)$ the minimum number of colours of a facial non-repetitive edge-colouring of $G$. In this paper, we show that $\pi'_f(G)\leq 8$ for any plane graph $G$. We also get better upper bounds for $\pi'_f(G)$ in the cases when $G$ is a tree, a plane triangulation, a simple $3$-connected plane graph, a hamiltonian plane graph, an outerplanar graph or a Halin graph. The bound $4$ for trees is tight.
 },

 URL={http://hal.inria.fr/inria-00366589/en/},

 PDF = {http://hal.inria.fr/docs/00/36/65/89/PDF/RR-6873.pdf},

 x-editorial-board={yes},

 x-proceedings={no},

 x-international-audience={yes},

 sorte = "rev-int",

 
}

F. Havet, M. Klazar, J. Kratochvìl, D. Kratsch, and M. Liedloff. Exact algorithms for L(2,1)-labelling. Algorithmica, 59(2):169--194, 2011. [PDF ]

Abstract:

The notion of distance constrained graph labelings, motivated by the Frequency Assignment Problem, reads as follows: A mapping from the vertex set of a graph $G=(V,E)$ into an interval of integers $\{0, \dots ,k\}$ is an $L(2,1)$-labeling of $G$ of span $k$ if any two adjacent vertices are mapped onto integers that are at least 2 apart, and every two vertices with a common neighbor are mapped onto distinct integers. It is known that for any fixed $k\ge 4$, deciding the existence of such a labeling is an NP-complete problem. We present exact exponential time algorithms that are faster than the naive $O((k+1)^n)$ algorithm that would try all possible mappings. The improvement is best seen in the first NP-complete case of $k=4$ -- here the running time of our algorithm is $O(1.3006^n)$. % $O(1.3161^n)$. Furthermore we show that dynamic programming can be used to establish 0x1.57ca7bff74698p-895n $O(c^n)$ algorithm to compute an optimal $L(2,1)$-labeling, for a constant $c< 4$. an $O(3.8730^n)$ algorithm to compute an optimal $L(2,1)$-labeling.

@article{HKK+11,

 author = {F. Havet and M. Klazar and J. Kratochv{\'{i}}l and D. Kratsch and M. Liedloff},

 title = {Exact algorithms for L(2,1)-labelling},

 journal = {Algorithmica},

 volume = {59},

 number = {2},

 year = {2011},

 pages = {169--194},

 abstract = {The notion of distance constrained graph labelings, motivated by the
 Frequency Assignment Problem, reads as follows: A mapping from the
 vertex set of a graph $G=(V,E)$ into an interval of integers
 $\{0, \dots ,k\}$ is an $L(2,1)$-labeling of $G$ of span $k$ if any two
 adjacent vertices are mapped onto integers that are at least 2
 apart, and every two vertices with a common neighbor are mapped onto
 distinct integers. It is known that for any fixed $k\ge 4$, deciding
 the existence of such a labeling is an NP-complete problem. We
 present exact exponential time algorithms that are faster than the
 naive $O((k+1)^n)$ algorithm that would try all possible mappings.
 The improvement is best seen in the first NP-complete case of $k=4$
 -- here the running time of our algorithm is $O(1.3006^n)$. % $O(1.3161^n)$.
 Furthermore we show that dynamic programming can be used to establish
 0x1.57ca7bff74698p-895n $O(c^n)$ algorithm to compute an optimal $L(2,1)$-labeling, for a constant $c< 4$.
 an $O(3.8730^n)$ algorithm to compute an optimal $L(2,1)$-labeling.},

 pdf = {http://hal.archives-ouvertes.fr/docs/00/30/33/30/PDF/RR-6587.pdf},

 x-editorial-board={yes},

 x-proceedings={yes},

 x-international-audience={yes},

 x-pays={CZ},

 
}

F. Kardos, J. Katrenic, and I. Schiermeyer. On computing the minimum 3-path vertex cover and dissociation number of graphs. Theoretical Computer Science, 412(50):7009-7017, 2011. [PDF ]

Abstract:

The dissociation number of a graph $G$ is the number of vertices in a maximum size induced subgraph of $G$ with vertex degree at most 1. A $k$-path vertex cover of a graph $G$ is a subset $S$ of vertices of $G$ such that every path of order $k$ in $G$ contains at least one vertex from $S$. The minimum $3$-path vertex cover is a dual problem to the dissociation number. For this problem we present an exact algorithm with a running time of $\mathcal{O}^*(1.5171^n)$ on a graph with $n$ vertices. We also provide a polynomial time randomized approximation algorithm with an expected approximation ratio of $\frac{23}{11}$ for the minimum $3$-path vertex cover.

@article{KKS11,

 author = {Kardo{\v{s}}, F. and Katreni{\v{c}}, J. and Schiermeyer, I. },

 title = {On computing the minimum 3-path vertex cover and dissociation number of graphs},

 journal = {Theoretical Computer Science},

 year = {2011},

 volume = {412},

 number = {50},

 pages = {7009-7017},

 abstract = {The dissociation number of a graph $G$ is the number of vertices in a maximum size induced subgraph of $G$ with vertex degree at most 1. A $k$-path vertex cover of a graph $G$ is a subset $S$ of vertices of $G$ such that every path of order $k$ in $G$ contains at least one vertex from $S$. The minimum $3$-path vertex cover is a dual problem to the dissociation number. For this problem we present an exact algorithm with a running time of $\mathcal{O}^*(1.5171^n)$ on a graph with $n$ vertices.
 We also provide a polynomial time randomized approximation algorithm with an expected approximation ratio of $\frac{23}{11}$ for the minimum $3$-path vertex cover. },

 pdf = {ftp://ftp-sop.inria.fr/mascotte/Publications/KKS11.pdf},

 x-editorial-board={yes},

 x-proceedings={no},

 x-international-audience={yes},

 x-pays = {GE, SK},

 sorte = "rev-int",

 
}

F. Kardos, D. Král', and J. Volec. Fractional colorings of cubic graphs with large girth. SIAM Journal on Discrete Mathematics, 25(3):1454-1476, 2011. [PDF ]

Abstract:

We show that every (sub)cubic $n$-vertex graph with sufficiently large girth has fractional chromatic number at most $2.2978$ which implies that it contains an independent set of size at least $0.4352n$. Our bound on the independence number is valid to random cubic graphs as well as it improves existing lower bounds on the maximum cut in cubic graphs with large girth.

@article{KKV11,

 author = {Kardo{\v{s}}, F. and Kr{\'{a}}l', D. and Volec, J. },

 title = {Fractional colorings of cubic graphs with large girth},

 journal = {SIAM Journal on Discrete Mathematics},

 year = {2011},

 volume = {25},

 number = {3},

 pages = {1454-1476},

 abstract = {We show that every (sub)cubic $n$-vertex graph with sufficiently large girth has fractional chromatic number at most $2.2978$ which implies that it contains an independent set of size at least $0.4352n$. Our bound on the independence number is valid to random cubic graphs as well as it improves existing lower bounds on the maximum cut in cubic graphs with large girth. },

 pdf = {ftp://ftp-sop.inria.fr/mascotte/Publications/KKV11.pdf},

 x-editorial-board={yes},

 x-proceedings={no},

 x-international-audience={yes},

 x-pays = {CZ, SK},

 sorte = "rev-int",

 
}

Conference articles

J. Araujo, J-C. Bermond, F. Giroire, F. Havet, D. Mazauric, and R. Modrzejewski. Weighted Improper Colouring. In C. S. Iliopoulos and W. F. Smyth, editors, Combinatorial Algorithms, volume 7056 of Lecture Notes in Computer Science, Victoria, Canada, pages 1-18, June 2011. Springer Berlin Heidelberg. [WWW ] [PDF ]

Abstract:

In this paper, we study a colouring problem motivated by a practical frequency assignment problem and up to our best knowledge new. In wireless networks, a node interferes with the other nodes the level of interference depending on numerous parameters: distance between the nodes, geographical topography, obstacles, etc. We model this with a weighted graph $G$ where the weights on the edges represent the noise (interference) between the two end-nodes. The total interference in a node is then the sum of all the noises of the nodes emitting on the same frequency. A weighted $t$-improper $k$-colouring of $G$ is a $k$-colouring of the nodes of $G$ (assignment of $k$ frequencies) such that the interference at each node does not exceed some threshold $t$. The Weighted Improper Colouring problem, that we consider here consists in determining the weighted $t$-improper chromatic number defined as the minimum integer $k$ such that $G$ admits a weighted $t$-improper $k$-colouring. We also consider the dual problem, denoted the Threshold Improper Colouring problem, where given a number $k$ of colours (frequencies) we want to determine the minimum real $t$ such that $G$ admits a weighted $t$-improper $k$-colouring. We show that both problems are NP-hard and first present general upper bounds; in particular we show a generalisation of Lov\'asz's Theorem for the weighted $t$-improper chromatic number. We then show how to transform an instance of the Threshold Improper Colouring problem into another equivalent one where the weights are either 1 or $M$, for a sufficient big value $M$. Motivated by the original application, we study a special interference model on various grids (square, triangular, hexagonal) where a node produces a noise of intensity 1 for its neighbours and a noise of intensity 1/2 for the nodes that are at distance 2. Consequently, the problem consists of determining the weighted $t$-improper chromatic number when $G$ is the square of a grid and the weights of the edges are 1, if their end nodes are adjacent in the grid, and 1/2 otherwise. Finally, we model the problem using linear integer programming, propose and test heuristic and exact Branch-and-Bound algorithms on random cell-like graphs, namely the Poisson-Voronoi tessellations.

@InProceedings{ABG+11b,

 author = {Araujo, J. and Bermond, J-C. and Giroire, F. and Havet, F. and Mazauric, D. and Modrzejewski, R.},

 title = {Weighted Improper Colouring},

 booktitle = {Combinatorial Algorithms},

 year = {2011},

 address = {Victoria, Canada},

 publisher= { Springer Berlin Heidelberg },

 series= {Lecture Notes in Computer Science},

 editor={Iliopoulos, C. S. and Smyth, W. F.},

 month = {June},

 volume= {7056},

 pages= {1-18},

 abstract = {In this paper, we study a colouring problem motivated by a
 practical frequency assignment problem and up to our best
 knowledge new. In wireless networks, a node interferes with the
 other nodes the level of interference depending on numerous
 parameters: distance between the nodes, geographical topography,
 obstacles, etc. We model this with a weighted graph $G$ where the
 weights on the edges represent the noise (interference) between the
 two end-nodes. The total interference in a node is then the sum of
 all the noises of the nodes emitting on the same frequency. A
 weighted $t$-improper $k$-colouring of $G$ is a $k$-colouring of the
 nodes of $G$ (assignment of $k$ frequencies) such that the
 interference at each node does not exceed some threshold
 $t$. The Weighted Improper Colouring problem, that we consider here
 consists in determining the weighted $t$-improper chromatic number
 defined as the minimum integer $k$ such that $G$ admits a weighted
 $t$-improper $k$-colouring. We also consider the dual problem, denoted the
 Threshold Improper Colouring problem, where given a number $k$ of
 colours (frequencies) we want to determine the minimum real $t$ such
 that $G$ admits a weighted $t$-improper $k$-colouring. We show that
 both problems are NP-hard and first present general upper bounds; in
 particular we show a generalisation of Lov\'asz's Theorem for the
 weighted $t$-improper chromatic number. We then show how to
 transform an instance of the Threshold Improper Colouring problem
 into another equivalent one where the weights are either 1 or $M$,
 for a sufficient big value $M$. Motivated by the original
 application, we study a special interference model on various grids
 (square, triangular, hexagonal) where a node produces a noise of
 intensity 1 for its neighbours and a noise of intensity 1/2 for the
 nodes that are at distance 2. Consequently, the problem consists of
 determining the weighted $t$-improper chromatic number when $G$ is
 the square of a grid and the weights of the edges are 1, if
 their end nodes are adjacent in the grid, and 1/2 otherwise.
 Finally, we model the problem using linear integer programming,
 propose and test heuristic and exact Branch-and-Bound algorithms on
 random cell-like graphs, namely the Poisson-Voronoi tessellations.},

 doi={10.1007/978-3-642-25011-8_1},

 url={http://dx.doi.org/10.1007/978-3-642-25011-8_1},

 pdf = {ftp://ftp-sop.inria.fr/mascotte/Publications/ABG+11b.pdf},

 x-editorial-board={yes},

 x-proceedings={yes},

 x-international-audience={yes},

 sorte = "conf-int",

 x-pays = {BR},

 
}

J. Araujo, V. Campos, F. Giroire, L. Sampaio, and R. Soares. On the hull number of some graph classes. In Proceedings of European Conference on Combinatorics, Graph Theory and Applications (EuroComb'11), volume 38 of Electronic Notes in Discrete Mathematics, Budapest, Hungary, pages 49-55, September 2011. [WWW ] [PDF ]

Abstract:

Given a graph G = (V, E), the closed interval of a pair of vertices u, v \in V , denoted by I[u, v], is the set of vertices that belongs to some shortest (u, v)-path. For a given S \subseteq V , let I[S] = u,v \in S I[u, v]. We say that S \subseteq V is a convex set if I[S] = S. The convex hull Ih [S] of a subset S \subseteq V is the smallest convex set that contains S. We say that S is a hull set if Ih [S] = V . The cardinality of a minimum hull set of G is the hull number of G, denoted by hn(G). We show that deciding if hn(G) \leq k is an NP-complete problem, even if G is bipartite. We also prove that hn(G) can be computed in polynomial time for cactus and P4 -sparse graphs.

@InProceedings{ACGS+11b,

 author = {J. Araujo and V. Campos and F. Giroire and L. Sampaio and R. Soares },

 title = {On the hull number of some graph classes},

 booktitle = {Proceedings of European Conference on Combinatorics, Graph Theory and Applications (EuroComb'11)},

 series = {Electronic Notes in Discrete Mathematics},

 pages = {49-55},

 volume = {38},

 year = {2011},

 address = {Budapest, Hungary},

 month = {September},

 abstract = {Given a graph G = (V, E), the closed interval of a pair of vertices u, v \in V ,
 denoted by I[u, v], is the set of vertices that belongs to some shortest (u, v)-path.
 For a given S \subseteq V , let I[S] = u,v \in S I[u, v]. We say that S \subseteq V is a convex set if
 I[S] = S.
 The convex hull Ih [S] of a subset S \subseteq V is the smallest convex set that contains
 S. We say that S is a hull set if Ih [S] = V . The cardinality of a minimum hull set
 of G is the hull number of G, denoted by hn(G).
 We show that deciding if hn(G) \leq k is an NP-complete problem, even if G is
 bipartite. We also prove that hn(G) can be computed in polynomial time for cactus
 and P4 -sparse graphs.
 },

 url={http://www.sciencedirect.com/science/article/pii/S1571065311000783},

 pdf={ftp://ftp-sop.inria.fr/mascotte/Publications/ACGS+11b.pdf},

 x-editorial-board={yes},

 x-proceedings={yes},

 x-international-audience={yes},

 x-pays = {BR},

 sorte = "conf-int",

 
}

J. Araujo, F. Giroire, and J. Monteiro. Hybrid Approaches for Distributed Storage Systems. In Proceedings of Fourth International Conference on Data Management in Grid and P2P Systems (Globe'11), Toulouse, France, September 2011. [WWW ] [PDF ]

Abstract:

Distributed or peer-to-peer storage solutions rely on the in- troduction of redundant data to be fault-tolerant and to achieve high reliability. One way to introduce redundancy is by simple replication. This strategy allows an easy and fast access to data, and a good band- width efficiency to repair the missing redundancy when a peer leaves or fails in high churn systems. However, it is known that erasure codes, like Reed-Solomon, are an effi- cient solution in terms of storage space to obtain high durability when compared to replication. Recently, the Regenerating Codes were proposed as an improvement of erasure codes to better use the available bandwidth when reconstructing the missing information. In this work, we compare these codes with two hybrid approaches. The first was already proposed and mixes erasure codes and replication. The second one is a new proposal that we call Double Coding. We compare these approaches with the traditional Reed-Solomon code and also Re- generating Codes from the point of view of availability, durability and storage space. This comparison uses Markov Chain Models that take into account the reconstruction time of the systems.

@InProceedings{AGM11,

 author = {J. Araujo and F. Giroire and J. Monteiro },

 title = {Hybrid Approaches for Distributed Storage Systems},

 booktitle = {Proceedings of Fourth International Conference on Data Management in Grid and P2P Systems (Globe'11)},

 year = {2011},

 address = {Toulouse, France},

 month = {September},

 abstract = {Distributed or peer-to-peer storage solutions rely on the in-
 troduction of redundant data to be fault-tolerant and to achieve high
 reliability. One way to introduce redundancy is by simple replication.
 This strategy allows an easy and fast access to data, and a good band-
 width efficiency to repair the missing redundancy when a peer leaves or
 fails in high churn systems.
 However, it is known that erasure codes, like Reed-Solomon, are an effi-
 cient solution in terms of storage space to obtain high durability when
 compared to replication.
 Recently, the Regenerating Codes were proposed as an improvement of
 erasure codes to better use the available bandwidth when reconstructing
 the missing information.
 In this work, we compare these codes with two hybrid approaches. The
 first was already proposed and mixes erasure codes and replication. The
 second one is a new proposal that we call Double Coding. We compare
 these approaches with the traditional Reed-Solomon code and also Re-
 generating Codes from the point of view of availability, durability and
 storage space. This comparison uses Markov Chain Models that take into
 account the reconstruction time of the systems.
 },

 PDF={ftp://ftp-sop.inria.fr/mascotte/Publications/AGM11.pdf},

 url = {http://hal.inria.fr/inria-00635781/fr/},

 x-editorial-board={yes},

 x-proceedings={yes},

 x-international-audience={yes},

 x-pays = {BR},

 sorte = "conf-int",

 
}

J. Bang-Jensen, F. Havet, and N. Trotignon. Finding an induced subdivision of a digraph. In VI Latin-American Algorithms, Graphs and Optimization Symposium (LAGOS 2011), volume 37, Bariloche, Argentina, pages 09-14, 04 2011.

Abstract:

We consider the following problem for oriented graphs and digraphs: Given an oriented graph (digraph) $G$, does it contain an induced subdivision of a prescribed digraph $D$? The complexity of this problem depends on $D$ and on whether $H$ must be an oriented graph or is allowed to contain 2-cycles. We give a number of examples of polynomial instances as well as several NP-completeness proofs.

@InProceedings{BHT11,

 author = {J. Bang-Jensen and F. Havet and N. Trotignon},

 title = {Finding an induced subdivision of a digraph},

 year = {2011},

 booktitle = {VI Latin-American Algorithms, Graphs and Optimization Symposium (LAGOS 2011)},

 journal = {Electronic Notes on Discrete Mathematics},

 pages = {09-14},

 volume = {37},

 address = {Bariloche, Argentina},

 month = {04},

 abstract = {We consider the following problem for oriented graphs and digraphs:
 Given an oriented graph (digraph) $G$, does it contain an induced
 subdivision of a prescribed digraph $D$? The complexity of
 this problem depends on $D$ and on whether $H$ must be an oriented
 graph or is allowed to contain 2-cycles. We give a number of examples of polynomial instances as well as several NP-completeness proofs.
 },

 sorte = "conf-int",

 x-editorial-board={yes},

 x-proceedings={yes},

 x-international-audience={yes},

 x-pays={DK},

 
}

Sanjoy Baruah, K., Vincenzo Bonifaci, G. D'Angelo, Alberto Marchetti-Spaccamela, Suzanne Ster, Van Der, and Leen Stougie. Mixed-Criticality Scheduling of Sporadic Task Systems. In Camil Demetrescu and Magnús M. Halldórsson, editors, 19th Annual European Symposium on Algorithms (ESA 2011), volume 6942 of Lecture Notes in Computer Science, Saarbruecken, Germany, pages 555-566, August 2011. Springer. [WWW ] [PDF ]

Abstract:

We consider the scheduling of mixed-criticality task systems, that is, systems where each task to be scheduled has multiple levels of worst-case execution time estimates. We design a scheduling algorithm, EDF-VD, whose effectiveness we analyze using the processor speedup metric: we show that any 2-level task system that is schedulable on a unit-speed processor is correctly scheduled by EDF-VD using speed $\phi$; here $\phi$ 2 criticality levels.We finally consider 2-level instances on m identical machines. We prove speedup bounds for scheduling an independent collection of jobs and for the partitioned scheduling of a 2-level task system.

@inproceedings{BBD+11b,

 hal_id = {hal-00643987},

 url = {http://hal.inria.fr/hal-00643987/en/},

 title = {{Mixed-Criticality Scheduling of Sporadic Task Systems}},

 author = {Baruah, K., Sanjoy and Bonifaci, Vincenzo and G. D'Angelo and Marchetti-Spaccamela, Alberto and Ster, Van Der, Suzanne and Stougie, Leen},

 abstract = {{We consider the scheduling of mixed-criticality task systems, that is, systems where each task to be scheduled has multiple levels of worst-case execution time estimates. We design a scheduling algorithm, EDF-VD, whose effectiveness we analyze using the processor speedup metric: we show that any 2-level task system that is schedulable on a unit-speed processor is correctly scheduled by EDF-VD using speed $\phi$; here $\phi$ 2 criticality levels.We finally consider 2-level instances on m identical machines. We prove speedup bounds for scheduling an independent collection of jobs and for the partitioned scheduling of a 2-level task system.}},

 language = {English},

 booktitle = {{19th Annual European Symposium on Algorithms (ESA 2011)}},

 publisher = {Springer},

 pages = {555-566},

 address = {Saarbruecken, Germany},

 volume = {6942},

 editor = {Camil Demetrescu and Magn{\'u}s M. Halld{\'o}rsson },

 series = {Lecture Notes in Computer Science },

 doi = {10.1007/978-3-642-23719-5\_47 },

 year = {2011},

 month = Aug,

 pdf = {http://hal.inria.fr/hal-00643987/PDF/MixedTasks.pdf},

 x-pays = {US,IT,NL,IN},

 x-editorial-board={yes},

 x-proceedings={yes},

 x-international-audience={yes},

 sorte = "conf-int",

 
}

J. Beauquier, P. Blanchard, J. Burman, and S. Delaet. Computing Time Complexity of Population Protocols with Cover Times - the ZebraNet Example. In 13th International Symposium on Stabilization, Safety, and Security of Distributed Systems, SSS 2011, Lecture Notes in Computer Science, pages 47-61, 2011. Springer. [WWW ]

Abstract:

Population protocols are a communication model for large sensor networks with resource-limited mobile agents. The agents move asynchronously and communicate via pair-wise interactions. The original fairness assumption of this model involves a high level of asynchrony and prevents an evaluation of the convergence time of a protocol (via deterministic means). The introduction of some "partial synchrony" in the model, under the form of cover times, is an extension that allows evaluating the time complexities. In this paper, we take advantage of this extension and study a data collection protocol used in the ZebraNet project for the wild-life tracking of zebras in a reserve in central Kenya. In ZebraNet, sensors are attached to zebras and the sensed data is collected regularly by a mobile base station crossing the area. The data collection protocol of ZebraNet has been analyzed through simulations, but to our knowledge, this is the rst time, that a purely analytical study is presented. Our first result is that, in the original protocol, some data may never be delivered to the base station. We then propose two slightly modify ed and correct protocols and we compute their worst case time complexities. Still, in both cases, the result is far from the optimal.

@inproceedings{BBB+11,

 author = {J. Beauquier and P. Blanchard and J. Burman and S. Delaet},

 title = {Computing Time Complexity of Population Protocols with Cover Times - the ZebraNet Example},

 booktitle = {13th International Symposium on Stabilization, Safety, and Security of Distributed Systems, SSS 2011},

 publisher = {Springer},

 year = {2011},

 series = {Lecture Notes in Computer Science},

 abstract = {Population protocols are a communication model for large
 sensor networks with resource-limited mobile agents. The agents move
 asynchronously and communicate via pair-wise interactions. The original
 fairness assumption of this model involves a high level of asynchrony
 and prevents an evaluation of the convergence time of a protocol (via
 deterministic means). The introduction of some "partial synchrony" in
 the model, under the form of cover times, is an extension that allows
 evaluating the time complexities.
 In this paper, we take advantage of this extension and study a data
 collection protocol used in the ZebraNet project for the wild-life tracking
 of zebras in a reserve in central Kenya. In ZebraNet, sensors are attached
 to zebras and the sensed data is collected regularly by a mobile base
 station crossing the area. The data collection protocol of ZebraNet has
 been analyzed through simulations, but to our knowledge, this is the rst
 time, that a purely analytical study is presented. Our first result is that,
 in the original protocol, some data may never be delivered to the base
 station. We then propose two slightly modify ed and correct protocols and
 we compute their worst case time complexities. Still, in both cases, the
 result is far from the optimal.},

 pages = {47-61},

 doi = {http://dx.doi.org/10.1007/978-3-642-24550-3_6},

 url = {http://hal.inria.fr/hal-00639583/en/},

 x-editorial-board={yes},

 x-proceedings={yes},

 x-international-audience={yes},

 sorte = "conf-int",

 
}

J. Beauquier and J. Burman. Self-stabilizing Mutual Exclusion and Group Mutual Exclusion for Population Protocols with Covering. In 15th International Conference On Principles Of Distributed Systems, OPODIS 2011, Lecture Notes in Computer Science, 2011. Springer. [WWW ]

Abstract:

This paper presents and proves correct two self-stabilizing deterministic algorithms solving the mutual exclusion and the group mutual exclusion problems in the model of population protocols with covering. In this variant of the population protocol model, a local fairness is used and bounded state anonymous mobile agents interact in pairs according to constraints expressed in terms of their cover times. The cover time is an indicator of the "time" for an agent to communicate with all the other agents. This indicator is expressed in the number of the pairwise communications (events) and is unknown to agents. In the model, we also assume the existence of a particular agent, the base station. In contrast with the other agents, it has a memory size proportional to the number of the agents. We prove that without this kind of assumption, the mutual exclusion problem has no solution. The algorithms in the paper use a phase clock tool. This is a synchronization tool that was recently proposed in the model we use. For our needs, we extend the functionality of this tool to support also phases with unbounded (but finite) duration. This extension seems to be useful also in the future works.

@inproceedings{BeBu11,

 author = {J. Beauquier and J. Burman},

 title = {Self-stabilizing Mutual Exclusion and Group Mutual Exclusion for Population Protocols with Covering},

 booktitle = {15th International Conference On Principles Of Distributed Systems, OPODIS 2011},

 publisher = {Springer},

 year = {2011},

 series = {Lecture Notes in Computer Science},

 abstract = {This paper presents and proves correct two self-stabilizing deterministic
 algorithms solving the mutual exclusion and the group mutual exclusion problems
 in the model of population protocols with covering. In this variant of the
 population protocol model, a local fairness is used and bounded state anonymous
 mobile agents interact in pairs according to constraints expressed in terms of their
 cover times. The cover time is an indicator of the "time" for an agent to communicate
 with all the other agents. This indicator is expressed in the number of the
 pairwise communications (events) and is unknown to agents. In the model, we
 also assume the existence of a particular agent, the base station. In contrast with
 the other agents, it has a memory size proportional to the number of the agents.
 We prove that without this kind of assumption, the mutual exclusion problem has
 no solution.
 The algorithms in the paper use a phase clock tool. This is a synchronization
 tool that was recently proposed in the model we use. For our needs, we extend
 the functionality of this tool to support also phases with unbounded (but finite)
 duration. This extension seems to be useful also in the future works.},

 url = {http://hal.inria.fr/hal-00639651/en/},

 x-editorial-board={yes},

 x-proceedings={yes},

 x-international-audience={yes},

 sorte = "conf-int",

 
}

J. Beauquier, J. Burman, and V. Malykh. ZebraNet Analysé dans le Modéle des Protocoles de Population. 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 ]

Abstract:

Nous \'etudions le protocole de collecte de donn\'ees du projet ZebraNet, dans le modÄle des protocoles de population. Dans ce projet des capteurs sont attach\'es \'a une population de z\'ebres, en Afrique Centrale, et fournissent des donn\'ees aux biologistes qui \'etudient leurs structures migratoires et comportementales. Nous montrons qu'un protocole voisin de celui utilis\'e dans ce projet ne se termine pas. Cela entra\^ine que le protocole originel ne se termine pas non plus. Aussi proposons nous une modification qui fournit la terminaison. Nous prouvons la correction de ce protocole modifi\'e et nous analysons sa complexit\'e en temps au pire, dans le mod\'ele des protocoles de population avec temps de couverture. La comparaison de cette complexit\'e avec celle du protocole optimal est tr\'es d\'efavorable. Le protocole de collecte de donn\'ees de ZebraNet a fait l'objet de simulations, mais c'est la premi\'ere fois, \'a notre connaissance, qu'est r\'ealis\'ee une \'etude purement analytique.

@inproceedings{BBM11,

 author = {Beauquier, J. and Burman, J. and Malykh, V.},

 title = {ZebraNet Analys\'e dans le Mod\'ele des Protocoles de Population},

 booktitle = {13es Rencontres Francophones sur les Aspects Algorithmiques de T\'el\'ecommunications (AlgoTel)},

 year = {2011},

 editor = {Ducourthial et Bertrand et Felber et Pascal},

 address = {Cap Est\'erel, France},

 abstract = {Nous \'etudions le protocole de collecte de donn\'ees du projet ZebraNet, dans le modÄle des protocoles de population. Dans ce
 projet des capteurs sont attach\'es \'a une population de z\'ebres, en Afrique Centrale, et fournissent des donn\'ees aux biologistes
 qui \'etudient leurs structures migratoires et comportementales. Nous montrons qu'un protocole voisin de celui utilis\'e dans ce
 projet ne se termine pas. Cela entra\^ine que le protocole originel ne se termine pas non plus. Aussi proposons nous une
 modification qui fournit la terminaison. Nous prouvons la correction de ce protocole modifi\'e et nous analysons sa complexit\'e
 en temps au pire, dans le mod\'ele des protocoles de population avec temps de couverture. La comparaison de cette complexit\'e
 avec celle du protocole optimal est tr\'es d\'efavorable.
 Le protocole de collecte de donn\'ees de ZebraNet a fait l'objet de simulations, mais c'est la premi\'ere fois, \'a notre connaissance,
 qu'est r\'ealis\'ee une \'etude purement analytique.},

 url = {http://hal.inria.fr/inria-00586503/fr/},

 x-editorial-board={yes},

 x-proceedings={yes},

 x-international-audience={no},

 x-pays = {RU},

 sorte = "conf-nat"
 
}

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:

{In this paper we ask which properties of a distributed network can be computed from a little amount of local information provided by its nodes. The distributed model we consider is a restriction of the classical CONGEST (distributed) model and it is close to the simultaneous messages (communication complexity) model defined by Babai, Kimmel and Lokam. More precisely, each of these n nodes -which only knows its own ID and the IDs of its neighbors- is allowed to send a message of O(log n) bits to some central entity, called the referee. Is it possible for the referee to decide some basic structural properties of the network topology G? We show that simple questions like, "does G contain a square?", "does G contain a triangle?" or "Is the diameter of G at most 3? cannot be solved in general. On the other hand, the referee can decode the messages in order to have full knowledge of G when G belongs to many graph classes such as planar graphs, bounded treewidth graphs and, more generally, bounded degeneracy graphs. We leave open questions related to the connectivity of arbitrary graphs. }, x-editorial-board={yes}, x-proceedings={yes}, x-international-audience={yes}, x-pays = {CL}, sorte = "conf-int",

@inproceedings{BMN+11,

 author = {Becker, F. and Matamala, M. and Nisse, N. and Rapaport, I. and Suchan, K. and Todinca, I.},

 title = {Adding a referee to an interconnection network: What can(not) be computed in one round},

 booktitle = {25th IEEE International Parallel \& Distributed Processing Symposium (IPDPS)},

 pages = {508-514},

 year = {2011},

 publisher = {IEEE},

 url = {http://arxiv.org/abs/1009.4447},

 pdf = {http://arxiv.org/pdf/1009.4447v2},

 abstract = {In this paper we ask which properties of a distributed network can be computed from a little amount of local information provided by its nodes. The distributed model we consider is a restriction of the classical CONGEST (distributed) model and it is close to the simultaneous messages (communication complexity) model defined by Babai, Kimmel and Lokam. More precisely, each of these n nodes -which only knows its own ID and the IDs of its neighbors- is allowed to send a message of O(log n) bits to some central entity, called the referee. Is it possible for the referee to decide some basic structural properties of the network topology G? We show that simple questions like, "does G contain a square?", "does G contain a triangle?" or "Is the diameter of G at most 3? cannot be solved in general. On the other hand, the referee can decode the messages in order to have full knowledge of G when G belongs to many graph classes such as planar graphs, bounded treewidth graphs and, more generally, bounded 
 degeneracy graphs. We leave open questions related to the connectivity of arbitrary graphs. },
 x-editorial-board={yes},
 x-proceedings={yes},
 x-international-audience={yes},
 x-pays = {CL},
 sorte = "conf-int",
 
}

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:

{Nous Ã©tudions quelles propriÃ©tÃ©s d'un rÃ©seau peuvent Ãªtre calculÃ©es Ã partir d'une petite quantitÃ© d'informations locales fournie par ses noeuds. Notre modÃ¨le est une restriction de CONGEST, un modÃ¨le distribuÃ© classique. Il est proche du modÃ¨le de complexitÃ© de communication avec messages simultanÃ©s de Babai et al. Chacun des n noeuds --qui ne connaissent que leur identifiant, ceux de leurs voisins et la taille du graphe-- envoie un message de taille O(log(n)) bits Ã une entitÃ© centrale, le superviseur. Celui-ci doit alors dÃ©terminer une certaine propriÃ©tÃ© du rÃ©seau. Nous montrons que des questions telles que: ''Est-ce que le graphe contient un triangle? un carrÃ© ? Quel est son diamÃ¨tre?" ne peuvent pas Ãªtre rÃ©solues dans ce modÃ¨le. En revanche, pour de nombreuses classes de graphes : celles de dÃ©gÃ©nÃ©rescence bornÃ©e (incluant les graphes planaires, ceux de largeur arborescente bornÃ©e... ), les sommets peuvent succinctement donner une description complÃ¨te du graphe au superviseur. Nous laissons ouverte la question de dÃ©cider la connexitÃ©.}, x-editorial-board={yes}, x-proceedings={yes}, x-international-audience={no}, x-pays= {CL}, sorte = "conf-nat",

@inproceedings{BMN+11b,

 author = {Becker, F. and Matamala, M. and Nisse, N. and Rapaport, I. and Suchan, K. and Todinca, I.},

 title = {{Reconstruire un graphe en une ronde}},

 booktitle = {13es Rencontres Francophones sur les Aspects Algorithmiques de T\'el\'ecommunications (AlgoTel)},

 year = {2011},

 editor = {Ducourthial and Bertrand et Felber and Pascal},

 address = {Cap Est\'erel, France},

 url = {http://hal.inria.fr/inria-00587250/en},

 abstract = {Nous Ã©tudions quelles propriÃ©tÃ©s d'un rÃ©seau peuvent Ãªtre calculÃ©es Ã partir d'une petite quantitÃ© d'informations locales fournie par ses noeuds. Notre modÃ¨le est une restriction de CONGEST, un modÃ¨le distribuÃ© classique. Il est proche du modÃ¨le de complexitÃ© de communication avec messages simultanÃ©s de Babai et al. Chacun des n noeuds --qui ne connaissent que leur identifiant, ceux de leurs voisins et la taille du graphe-- envoie un message de taille O(log(n)) bits Ã une entitÃ© centrale, le superviseur. Celui-ci doit alors dÃ©terminer une certaine propriÃ©tÃ© du rÃ©seau. Nous montrons que des questions telles que: ''Est-ce que le graphe contient un triangle? un carrÃ© ? Quel est son diamÃ¨tre?" ne peuvent pas Ãªtre rÃ©solues dans ce modÃ¨le. En revanche, pour de nombreuses classes de graphes : celles de dÃ©gÃ©nÃ©rescence bornÃ©e (incluant les graphes planaires, ceux de largeur arborescente bornÃ©e... ), les sommets peuvent succinctement donner une description complÃ¨te du graphe au superviseur. Nous laissons 
 ouverte la question de dÃ©cider la connexitÃ©.},
 x-editorial-board={yes},
 x-proceedings={yes},
 x-international-audience={no},
 x-pays= {CL},
 sorte = "conf-nat",
 
}

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:

Dans un rÃ©seau WDM, utiliser une nouvelle longueur d'onde dans une ï¬bre demande Ã recalibrer les autres longueurs d'ondes. Cela gÃ©nÃ¨re un coÃ»t (e.g., Ã©nergÃ©tique) qui dÃ©pend non linÃ©airement du nombre de longueurs d'ondes utilisant la ï¬bre. Lorsqu'un ensemble de requÃªtes doivent changer de chemins optiques dans le rÃ©seau (lors d'une opÃ©ration de maintenance sur un lien du rÃ©seau), l'ordre dans lequel les requÃªtes sont dÃ©placÃ©es inï¬ue sur le coÃ»t total de l'opÃ©ration. Nous initions l'Ã©tude du problÃ¨me d'optimisation correspondant. Nous prouvons que dÃ©terminer l'ordre de dÃ©placements optimal est NP-complet pour un rÃ©seau de 2 nÅuds. Nous donnons des bornes gÃ©nÃ©rales et identiï¬ons des classes d'instances faciles. Enï¬n, nous proposons et Ã©valuons par simulations des heuristiques pour ce problÃ¨me.

@inproceedings{BCM+11,

 author = {Belhareth, S. and Coudert, D. and Mazauric, D. and Nisse, N. and Tahiri, I.},

 title = {{Reconfiguration avec contraintes physiques dans les r\'eseaux WDM}},

 booktitle = {13es Rencontres Francophones sur les Aspects Algorithmiques de T\'el\'ecommunications (AlgoTel)},

 year = {2011},

 editor = {Ducourthial et Bertrand et Felber et Pascal},

 address = {Cap Est\'erel, France},

 pdf = {http://hal.inria.fr/docs/00/58/77/09/PDF/reconf-20110406.pdf},

 url = {http://hal.inria.fr/inria-00583829/en},

 abstract = {Dans un rÃ©seau WDM, utiliser une nouvelle longueur d'onde dans une ï¬bre demande Ã recalibrer les autres longueurs d'ondes. Cela gÃ©nÃ¨re un coÃ»t (e.g., Ã©nergÃ©tique) qui dÃ©pend non linÃ©airement du nombre de longueurs d'ondes utilisant la ï¬bre. Lorsqu'un ensemble de requÃªtes doivent changer de chemins optiques dans le rÃ©seau (lors d'une opÃ©ration de maintenance sur un lien du rÃ©seau), l'ordre dans lequel les requÃªtes sont dÃ©placÃ©es inï¬ue sur le coÃ»t total de l'opÃ©ration. Nous initions l'Ã©tude du problÃ¨me d'optimisation correspondant. Nous prouvons que dÃ©terminer l'ordre de dÃ©placements optimal est NP-complet pour un rÃ©seau de 2 nÅuds. Nous donnons des bornes gÃ©nÃ©rales et identiï¬ons des classes d'instances faciles. Enï¬n, nous proposons et Ã©valuons par simulations des heuristiques pour ce problÃ¨me.},

 x-editorial-board={yes},

 x-proceedings={yes},

 x-international-audience={no},

 x-pays = {TN},

 sorte = "conf-nat",

 
}

J-C. Bermond, L. Gargano, S. Pérennes and A.A. Rescigno, and U. Vaccaro. Optimal Time Data Gathering in Wireless Networks with Omni-Directional Antennas. In SIROCCO 2011, volume 6796 of Lecture Notes in Computer Science, Gdansk, Poland, pages 306-317, June 2011. Springer-Verlag. [PDF ]

Abstract:

We study algorithmic and complexity issues originating from the problem of data gathering in wireless networks. We give an algorithm to construct minimum makespan transmission schedules for data gathering when the communication graph $G$ is a tree network, the interference range is \emph{any} integer $m\geq 2$, and no buffering is allowed at intermediate nodes. In the interesting case in which all nodes in the network have to deliver an arbitrary non-zero number of packets, we provide a closed formula for the makespan of the optimal gathering schedule. Additionally, we consider the problem of determining the computational complexity of data gathering in general graphs and show that the problem is weakly NP-complete. On the positive side, we design a simple $(1+2/m)$ factor approximation algorithm for general networks.

@inproceedings{BGP+11,

 author= {J-C. Bermond and L. Gargano and S. P\'erennes and
 A.A. Rescigno and U. Vaccaro},

 title= {Optimal Time Data Gathering in Wireless Networks
 with Omni-Directional Antennas },

 booktitle= { SIROCCO 2011 },

 publisher= { Springer-Verlag },

 series= {Lecture Notes in Computer Science},

 address= {Gdansk, Poland },

 month=jun,

 volume = {6796},

 pages = {306-317},

 year= {2011},

 PDF={ftp://ftp-sop.inria.fr/mascotte/personnel/Jean-Claude.Bermond/PUBLIS/BGPRV11.pdf},

 abstract={We study algorithmic and complexity issues originating from
 the problem of data gathering 
 in wireless networks.
 We give an algorithm to construct 
 minimum makespan transmission schedules
 for data gathering
 when the communication graph
 $G$ is a tree network, the interference range is \emph{any}
 integer $m\geq 2$, and no buffering is allowed at intermediate nodes.
 In the interesting case in which all nodes in the network have to deliver
 an arbitrary non-zero number of packets,
 we provide a closed formula for the
 makespan of the optimal gathering schedule.
 Additionally, we consider the problem of determining the
 computational complexity of data gathering in general graphs
 and show that the problem is weakly NP-complete. On the positive side,
 we design
 a simple $(1+2/m)$ factor approximation algorithm for general networks.},

 x-editorial-board={yes},

 x-proceedings={yes},

 x-international-audience={yes},

 sorte = "conf-int",

 x-pays = {IT},

 
}

C. Caillouet and A. Koster. Routage et Ordonnancement Robustes dans les Réseaux Radio Maillés. 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 ]

@inproceedings{CaKo11,

 author = {C. Caillouet and A. Koster},

 title = {{Routage et Ordonnancement Robustes dans les R{\'e}seaux Radio Maill{\'e}s}},

 booktitle = {{13es Rencontres Francophones sur les Aspects Algorithmiques de T{\'e}l{\'e}communications (AlgoTel)}},

 year = {2011},

 editor = {Ducourthial and Bertrand et Felber and Pascal},

 address = {Cap Est{\'e}rel, France},

 url = {http://hal.inria.fr/inria-00586698/en},

 x-editorial-board={yes},

 x-proceedings={yes},

 x-international-audience={no},

 sorte = "conf-nat",

 
}

C. Caillouet, X. Li, and T. Razafindralambo. A Multi-objective Approach for Data Collection in Wireless Sensor Networks. In 10th International Conference on Ad Hoc Networks and Wireless (AdHocNow), Padderborn, Germany, July 2011. [WWW ]

@inproceedings{CLR11,

 author = {C. Caillouet and X. Li and T. Razafindralambo},

 title = {{A Multi-objective Approach for Data Collection in Wireless Sensor Networks}},

 booktitle = {{10th International Conference on Ad Hoc Networks and Wireless (AdHocNow)}},

 year = {2011},

 month = Jul,

 address = {Padderborn, Germany},

 url = {http://hal.inria.fr/inria-00601679/en},

 x-editorial-board={yes},

 x-proceedings={yes},

 x-international-audience={yes},

 sorte = "conf-int",

 
}

C. Caillouet and T. Razafindralambo. Compromis énergie-délai pour la collecte de données dans les réseaux de capteurs. 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 ]

@inproceedings{CaRa11,

 author = {C. Caillouet and T. Razafindralambo},

 title = {{Compromis {\'e}nergie-d{\'e}lai pour la collecte de donn{\'e}es dans les r{\'e}seaux de capteurs}},

 booktitle = {{13es Rencontres Francophones sur les Aspects Algorithmiques de T{\'e}l{\'e}communications (AlgoTel)}},

 year = {2011},

 editor = {Ducourthial and Bertrand et Felber and Pascal},

 address = {Cap Est{\'e}rel, France},

 url = {http://hal.inria.fr/inria-00586681/en},

 x-editorial-board={yes},

 x-proceedings={yes},

 x-international-audience={no},

 sorte = "conf-nat",

 
}

V. Campos, C. Linhares Sales, A. K. Maia, N. Martins, and R. Sampaio. Restricted coloring problems on graphs with few $P_4$'s. In VI Latin-American Algorithms, Graphs and Optimization Symposium (LAGOS'11), volume 37 of Electronic Notes in Discrete Mathematics, pages 57-62, 2011. [WWW ] [PDF ]

Abstract:

In this paper, we obtain polynomial time algorithms to determine the acyclic chromatic number, the star chromatic number and the harmonious chromatic number of $P_4$ -tidy graphs and $(q , q â 4)$-graphs, for every fixed q. These classes include cographs, $P_4$ -sparse and $P_4$ -lite graphs. We also obtain a polynomial time algorithm to determine the Grundy number of $(q , q â 4)$-graphs. All these coloring problems are known to be NP-hard for general graphs.

@InProceedings{CLM+11,

 author = {Campos, V. and Linhares Sales, C. and Maia, A. K. and Martins, N. and Sampaio, R.},

 title = {Restricted coloring problems on graphs with few $P_4$'s},

 OPTcrossref = {},

 OPTkey = {},

 booktitle = {VI Latin-American Algorithms, Graphs and Optimization Symposium (LAGOS'11)},

 pages = {57-62},

 year = {2011},

 OPTeditor = {},

 volume = {37},

 OPTnumber = {},

 series = {Electronic Notes in Discrete Mathematics},

 OPTaddress = {},

 OPTmonth = {},

 OPTorganization = {},

 OPTpublisher = {},

 abstract = {In this paper, we obtain polynomial time algorithms to determine the acyclic chromatic number, the star chromatic number and the harmonious 
 chromatic number of $P_4$ -tidy graphs and $(q , q â 4)$-graphs, for every fixed q. These classes include cographs, $P_4$ -sparse and $P_4$ -lite graphs. We also 
 obtain a polynomial time algorithm to determine the Grundy number of $(q , q â 4)$-graphs. All these coloring problems are known to be NP-hard for general 
 graphs.},

 pdf = {http://hal.inria.fr/docs/00/64/31/80/PDF/col-fewP4.pdf},

 doi = "10.1016/j.endm.2011.05.011",

 url = "http://www.sciencedirect.com/science/article/pii/S1571065311000126",

 x-editorial-board = {yes},

 x-proceedings = {yes},

 x-international-audience = {yes},

 x-pays = {BR},

 sorte = "conf-int",

 
}

G. Classen, D. Coudert, A. Koster, and N. Nepomuceno. A Chance-Constrained Model & Cutting Planes for Fixed Broadband Wireless Networks. In International Network Optimization Conference (INOC), volume 6701 of Lecture Notes in Computer Science, Hamburg, Germany, pages 37-42, June 2011. [PDF ]

Abstract:

In this paper, we propose a chance-constrained mathematical program for fixed broadband wireless networks under unreliable channel conditions. The model is reformulated as integer linear program and valid inequalities are derived for the corresponding polytope. Computational results show that by an exact separation approach the optimality gap is closed by~$42$\,\27775643230n average.

@InProceedings{CCKN11b,

 author = {G. Cla{\ss}en and D. Coudert and A. Koster and N. Nepomuceno},

 title = {A Chance-Constrained Model \& Cutting Planes for Fixed Broadband Wireless Networks},

 booktitle = {International Network Optimization Conference (INOC)},

 pages = {37-42},

 year = {2011},

 volume = {6701},

 series = {Lecture Notes in Computer Science},

 address = {Hamburg, Germany},

 month = jun,

 abstract = {In this paper, we propose a chance-constrained mathematical program for fixed broadband wireless networks under unreliable channel conditions. The model is reformulated as integer linear program and valid inequalities are derived for the corresponding polytope. Computational results show that by an exact separation approach the optimality gap is closed by~$42$\,\27775643230n average.},

 pdf = {http://hal.inria.fr/docs/00/58/76/69/PDF/ClCoKoNe-noformat.pdf},

 DOI = {10.1007/978-3-642-21527-8\_5},

 x-editorial-board={yes},

 x-proceedings={yes},

 x-international-audience={yes},

 x-pays={DE,DK},

 sorte = "conf-int",

 
}

G. Classen, D. Coudert, A. Koster, and N. Nepomuceno. Bandwidth assignment for reliable fixed broadband wireless networks. In 12th IEEE International Symposium on a World of Wireless Mobile and Multimedia Networks (WoWMoM), Lucca, Italy, pages 1-6, June 2011. IEEE. [PDF ]

Abstract:

In this paper, we investigate on conceiving reliable fixed broadband wireless networks under outage probability constraints. We introduce a joint optimization of data routing and bandwidth assignment that minimizes the total renewal fees of licenses, while handling all the traffic requirements simultaneously. This problem differs from classical capacity planning in the sense that the capacity of microwave radio links are prone to variations due to external factors (e.g., weather). Therefore, we must consider probabilistic constraints to deal with random parameters (viz., modulation schemes) and guarantee a desirable reliability level of the solution. We propose a (joint) chance-constrained programming approach to tackle this problem. This approach remains one of the main challenges of modern stochastic programming and it is still considered as very difficult and widely intractable. We then derive integer linear programming (ILP) counterparts for these chance-constrained programs and propose cutset-based valid inequalities to enhance the performance of ILP solvers. Preliminary computational results illustrate the price of reliability and present a comparative study on the performance of the different formulations.

@InProceedings{CCKN11,

 author = {G. Cla{\ss}en and D. Coudert and A. Koster and N. Nepomuceno},

 title = {Bandwidth assignment for reliable fixed broadband wireless networks},

 booktitle = {12th {IEEE} International Symposium on a World of Wireless Mobile and Multimedia Networks ({WoWMoM})},

 pages = {1-6},

 year = {2011},

 address = {Lucca, Italy},

 month = jun,

 publisher = {IEEE},

 abstract = {In this paper, we investigate on conceiving reliable fixed broadband wireless networks under outage probability constraints. We introduce a joint optimization of data routing and bandwidth assignment that minimizes the total renewal fees of licenses, while handling all the traffic requirements simultaneously. This problem differs from classical capacity planning in the sense that the capacity of microwave radio links are prone to variations due to external factors (e.g., weather). Therefore, we must consider probabilistic constraints to deal with random parameters (viz., modulation schemes) and guarantee a desirable reliability level of the solution. We propose a (joint) chance-constrained programming approach to tackle this problem. This approach remains one of the main challenges of modern stochastic programming and it is still considered as very difficult and widely intractable. We then derive integer linear programming (ILP) counterparts for these chance-constrained programs and propose 
 cutset-based valid inequalities to enhance the performance of ILP solvers. Preliminary computational results illustrate the price of reliability and present a comparative study on the performance of the different formulations.},

 pdf = {http://hal.inria.fr/docs/00/58/76/98/PDF/bare_conf-noformat.pdf},

 DOI = {10.1109/WoWMoM.2011.5986471},

 x-editorial-board={yes},

 x-proceedings={yes},

 x-international-audience={yes},

 x-pays={DE,DK},

 sorte = "conf-int",

 
}

D. Coudert, N. Nepomuceno, and I. Tahiri. Energy saving in fixed wireless broadband networks. In International Network Optimization Conference (INOC), volume 6701 of Lecture Notes in Computer Science, Hamburg, Germany, pages 484-489, June 2011. [PDF ]

Abstract:

In this paper, we present a mathematical formulation for saving energy in fixed broadband wireless networks by selectively turning off idle communication devices in low-demand scenarios. This problem relies on a fixed-charge capacitated network design (FCCND), which is very hard to optimize. We then propose heuristic algorithms to produce feasible solutions in a short time.

@InProceedings{CNT11b,

 author = {Coudert, D. and Nepomuceno, N. and Tahiri, I.},

 title = {Energy saving in fixed wireless broadband networks},

 booktitle = {International Network Optimization Conference (INOC)},

 pages = {484-489},

 year = {2011},

 volume = {6701},

 series = {Lecture Notes in Computer Science},

 address = {Hamburg, Germany},

 month = jun,

 abstract = {In this paper, we present a mathematical formulation for saving energy in fixed broadband wireless networks by selectively turning off idle communication devices in low-demand scenarios. This problem relies on a fixed-charge capacitated network design (FCCND), which is very hard to optimize. We then propose heuristic algorithms to produce feasible solutions in a short time.},

 pdf = {http://hal.inria.fr/docs/00/58/76/85/PDF/CNT11-noformat.pdf},

 DOI = {10.1007/978-3-642-21527-8\_53},

 x-editorial-board={yes},

 x-proceedings={yes},

 x-international-audience={yes},

 x-pays={DK},

 sorte = "conf-int",

 
 
}

D. Coudert, N. Nepomuceno, and I. Tahiri. Optimisation de la consommation énergétique dans les réseaux sans fil fixes. In Pascal Ducourthial, Bertrand et Felber, editor, 13es Rencontres Francophones sur les Aspects Algorithmiques de Télécommunications (AlgoTel), Cap Estérel France, 2011. [WWW ] [PDF ]

Abstract:

{N}ous {\'e}tudions le probl{\`e}me d'optimisation {\'e}nerg{\'e}tique dans les r{\'e}seaux sans fil fixes dans le cas d'une faible demande de trafic par rapport {\`a} la capacit{\'e} du r{\'e}seau. {N}ous proposons un programme lin{\'e}aire pour r{\'e}soudre le probl{\`e}me, puis nous pr{\'e}sentons une heuristique permettant de trouver rapidement une bonne solution.

@inproceedings{CNT11,

 HAL_ID = {inria-00588129},

 url = {http://hal.inria.fr/inria-00588129/en/},

 title = { {O}ptimisation de la consommation {\'e}nerg{\'e}tique dans les r{\'e}seaux sans fil fixes},

 author = {Coudert, D. and Nepomuceno, N. and Tahiri, I.},

 abstract = {{N}ous {\'e}tudions le probl{\`e}me d'optimisation {\'e}nerg{\'e}tique dans les r{\'e}seaux sans fil fixes dans le cas d'une faible demande de trafic par rapport {\`a} la capacit{\'e} du r{\'e}seau. {N}ous proposons un programme lin{\'e}aire pour r{\'e}soudre le probl{\`e}me, puis nous pr{\'e}sentons une heuristique permettant de trouver rapidement une bonne solution.},

 language = {{F}ran{\c{c}}ais},

 affiliation = {{MASCOTTE} - {INRIA} {S}ophia {A}ntipolis / {L}aboratoire {I}3{S} - {INRIA} - {U}niversit{\'e} de {N}ice {S}ophia-{A}ntipolis - {CNRS} : {UMR}6070 },

 booktitle = {13es {R}encontres {F}rancophones sur les {A}spects {A}lgorithmiques de {T}{\'e}l{\'e}communications ({A}lgo{T}el) },

 address = {{C}ap {E}st{\'e}rel {F}rance },

 editor = {{D}ucourthial, {B}ertrand et {F}elber, {P}ascal },

 audience = {internationale },

 year = {2011},

 pdf = {http://hal.inria.fr/inria-00588129/PDF/document.pdf},

 x-editorial-board={yes},

 x-proceedings={yes},

 x-international-audience={no},

 sorte = "conf-nat",

 
 
}

G. D'Angelo, Mattia D'Emidio, Daniele Frigioni, and Vinicio Maurizio. A Speed-Up Technique for Distributed Shortest Paths Computation. In Beniamino Murgante, Osvaldo Gervasi, Andrés Iglesias, David Taniar, and Bernady O. Apduhan, editors, 11th International Conference on Computational Science and Its Applications (ICCSA 2011), volume 6783 of Lecture Notes in Computer Science, Santander, Spain, pages 578-593, June 2011. Springer. [WWW ] [PDF ]

Abstract:

We propose a simple and practical speed-up technique, which can be combined with every distance vector routing algorithm based on shortest paths, allowing to reduce the total number of messages sent by that algorithm. We combine the new technique with two algorithms known in the literature: DUAL, which is part of CISCO's widely used EIGRP protocol, and the recent DUST, which has been shown to be very effective on networks with power law node degree distribution. We give experimental evidence that these combinations lead to an important gain in terms of the number of messages sent by DUAL and DUST at the price of a little increase in terms of space occupancy per node.

@inproceedings{DDF+11,

 hal_id = {hal-00644049},

 url = {http://hal.inria.fr/hal-00644049/en/},

 title = {{A Speed-Up Technique for Distributed Shortest Paths Computation}},

 author = {G. D'Angelo and D'Emidio, Mattia and Frigioni, Daniele and Maurizio, Vinicio},

 abstract = {{We propose a simple and practical speed-up technique, which can be combined with every distance vector routing algorithm based on shortest paths, allowing to reduce the total number of messages sent by that algorithm. We combine the new technique with two algorithms known in the literature: DUAL, which is part of CISCO's widely used EIGRP protocol, and the recent DUST, which has been shown to be very effective on networks with power law node degree distribution. We give experimental evidence that these combinations lead to an important gain in terms of the number of messages sent by DUAL and DUST at the price of a little increase in terms of space occupancy per node.}},

 language = {English},

 booktitle = {{11th International Conference on Computational Science and Its Applications (ICCSA 2011)}},

 publisher = {Springer},

 pages = {578-593},

 address = {Santander, Spain},

 volume = {6783},

 editor = {Beniamino Murgante and Osvaldo Gervasi and Andr{\'e}s Iglesias and David Taniar and Bernady O. Apduhan },

 series = {Lecture Notes in Computer Science },

 audience = {international },

 doi = {10.1007/978-3-642-21887-3\_44 },

 year = {2011},

 month = Jun,

 pdf = {http://hal.inria.fr/hal-00644049/PDF/dlp.pdf},

 x-pays = {IT},

 x-editorial-board={yes},

 x-proceedings={yes},

 x-international-audience={yes},

 sorte = "conf-int",

 
}

G. D'Angelo, Gabriele Di Stefano, and Alfredo Navarra. Bandwidth Constrained Multi-interface Networks. In Ivana Cerná, Tibor Gyimóthy, Juraj Hromkovic, Keith Jefferey, Rastislav Královic, Marko Vukolic, and Stefan Wolf, editors, 37th Conference on Current Trends in Theory and Practice of Computer Science, volume 6543 of Lecture Notes in Computer Science, Novy Smokovec, Slovakia, pages 202-213, January 2011. Springer. [WWW ] [PDF ]

Abstract:

In heterogeneous networks, devices can communicate by means of multiple wired or wireless interfaces. By switching among interfaces or by combining the available interfaces, each device might establish several connections. A connection is established when the devices at its endpoints share at least one active interface. Each interface is assumed to require an activation cost, and provides a communication bandwidth. In this paper, we consider the problem of activating the cheapest set of interfaces among a network Gâ=â(V,E) in order to guarantee a minimum bandwidth B of communication between two specified nodes. Nodes V represent the devices, edges E represent the connections that can be established. In practical cases, a bounded number k of different interfaces among all the devices can be considered. Despite this assumption, the problem turns out to be NP-hard even for small values of k and $\Delta$, where $\Delta$ is the maximum degree of the network. In particular, the problem is NP-hard for any fixed kâ$\ge$â2 and $\Delta$â$\ge$â3, while it is polynomially solvable when kâ=â1, or $\Delta$â$\le$â2 and kâ=âO(1). Moreover, we show that the problem is not approximable within $\eta$logB or $\Omega$(loglog|V|) for any fixed kâ$\ge$â3, $\Delta$â$\ge$â3, and for a certain constant $\eta$, unless P=NP. We then provide an approximation algorithm with ratio guarantee of b max , where b max is the maximum communication bandwidth allowed among all the available interfaces. Finally, we focus on particular cases by providing complexity results and polynomial algorithms for $\Delta$â$\le$â2.

@inproceedings{DDN11e,

 hal_id = {hal-00644104},

 url = {http://hal.inria.fr/hal-00644104/en/},

 title = {{Bandwidth Constrained Multi-interface Networks}},

 author = {G. D'Angelo and Di Stefano, Gabriele and Navarra, Alfredo},

 abstract = {{In heterogeneous networks, devices can communicate by means of multiple wired or wireless interfaces. By switching among interfaces or by combining the available interfaces, each device might establish several connections. A connection is established when the devices at its endpoints share at least one active interface. Each interface is assumed to require an activation cost, and provides a communication bandwidth. In this paper, we consider the problem of activating the cheapest set of interfaces among a network Gâ=â(V,E) in order to guarantee a minimum bandwidth B of communication between two specified nodes. Nodes V represent the devices, edges E represent the connections that can be established. In practical cases, a bounded number k of different interfaces among all the devices can be considered. Despite this assumption, the problem turns out to be NP-hard even for small values of k and $\Delta$, where $\Delta$ is the maximum degree of the network. In particular, the problem is NP-hard for 
 any fixed kâ$\ge$â2 and $\Delta$â$\ge$â3, while it is polynomially solvable when kâ=â1, or $\Delta$â$\le$â2 and kâ=âO(1). Moreover, we show that the problem is not approximable within $\eta$logB or $\Omega$(loglog|V|) for any fixed kâ$\ge$â3, $\Delta$â$\ge$â3, and for a certain constant $\eta$, unless P=NP. We then provide an approximation algorithm with ratio guarantee of b max , where b max is the maximum communication bandwidth allowed among all the available interfaces. Finally, we focus on particular cases by providing complexity results and polynomial algorithms for $\Delta$â$\le$â2.}},

 language = {English},

 booktitle = {{37th Conference on Current Trends in Theory and Practice of Computer Science}},

 publisher = {Springer},

 pages = {202-213},

 address = {Nov{\'y} Smokovec, Slovakia},

 volume = {6543},

 editor = {Ivana Cern{\'a} and Tibor Gyim{\'o}thy and Juraj Hromkovic and Keith Jefferey and Rastislav Kr{\'a}lovic and Marko Vukolic and Stefan Wolf },

 series = {Lecture Notes in Computer Science },

 doi = {10.1007/978-3-642-18381-2\_17 },

 year = {2011},

 month = Jan,

 pdf = {http://hal.inria.fr/hal-00644104/PDF/MultiInterfacesFlowTheor.pdf},

 x-pays = {IT},

 x-editorial-board={yes},

 x-proceedings={yes},

 x-international-audience={yes},

 sorte = "conf-int",

 
}

G. D'Angelo, Gabriele Di Stefano, and Alfredo Navarra. Gathering of Six Robots on Anonymous Symmetric Rings. In Adrian Kosowski and Masafumi Yamashita, editors, Structural Information and Communication Complexity, volume 6796 of Lecture Notes in Computer Science, Gdansk, Poland, pages 174-185, July 2011. Springer. [WWW ] [PDF ]

Abstract:

The paper deals with a recent model of robot-based computing which makes use of identical, memoryless mobile robots placed on nodes of anonymous graphs. The robots operate in Look-Compute-Move cycles; in one cycle, a robot takes a snapshot of the current configuration (Look), takes a decision whether to stay idle or to move to one of its adjacent nodes (Compute), and in the latter case makes an instantaneous move to this neighbor (Move). Cycles are performed asynchronously for each robot. In particular, we consider the case of only six robots placed on the nodes of an anonymous ring in such a way they constitute a symmetric placement with respect to one single axis of symmetry, and we ask whether there exists a strategy that allows the robots to gather at one single node. This is in fact the first case left open after a series of papers [1,2,3,4] dealing with the gathering of oblivious robots on anonymous rings. As long as the gathering is feasible, we provide a new distributed approach that guarantees a positive answer to the posed question. Despite the very special case considered, the provided strategy turns out to be very interesting as it neither completely falls into symmetry-breaking nor into symmetry-preserving techniques.

@inproceedings{DDN11b,

 hal_id = {hal-00644039},

 url = {http://hal.inria.fr/hal-00644039/en/},

 title = {{Gathering of Six Robots on Anonymous Symmetric Rings}},

 author = {G. D'Angelo and Di Stefano, Gabriele and Navarra, Alfredo},

 abstract = {{The paper deals with a recent model of robot-based computing which makes use of identical, memoryless mobile robots placed on nodes of anonymous graphs. The robots operate in Look-Compute-Move cycles; in one cycle, a robot takes a snapshot of the current configuration (Look), takes a decision whether to stay idle or to move to one of its adjacent nodes (Compute), and in the latter case makes an instantaneous move to this neighbor (Move). Cycles are performed asynchronously for each robot. In particular, we consider the case of only six robots placed on the nodes of an anonymous ring in such a way they constitute a symmetric placement with respect to one single axis of symmetry, and we ask whether there exists a strategy that allows the robots to gather at one single node. This is in fact the first case left open after a series of papers [1,2,3,4] dealing with the gathering of oblivious robots on anonymous rings. As long as the gathering is feasible, we provide a new distributed approach that 
 guarantees a positive answer to the posed question. Despite the very special case considered, the provided strategy turns out to be very interesting as it neither completely falls into symmetry-breaking nor into symmetry-preserving techniques.}},

 language = {English},

 booktitle = {{Structural Information and Communication Complexity}},

 publisher = {Springer},

 pages = {174-185},

 address = {Gdansk, Poland},

 volume = {6796},

 editor = {Adrian Kosowski and Masafumi Yamashita },

 series = {Lecture Notes in Computer Science },

 doi = {10.1007/978-3-642-22212-2\_16 },

 year = {2011},

 month = Jul,

 pdf = {http://hal.inria.fr/hal-00644039/PDF/GatheringSixRobots.pdf},

 x-pays = {IT},

 x-editorial-board={yes},

 x-proceedings={yes},

 x-international-audience={yes},

 sorte = "conf-int",

 
}

G. D'Angelo, Gabriele Di Stefano, and Alfredo Navarra. Maximum Flow and Minimum-Cost Flow in Multi-Interface Networks. In 5th International Conference on Ubiquitous Information Management and Communication, Seoul, Korea, Republic Of, pages 19, February 2011. ACM. [WWW ] [PDF ]

Abstract:

In heterogeneous networks, devices can communicate by means of multiple wired or wireless interfaces. By switching among interfaces or by combining the available interfaces, each device might establish several connections. A connection is established when the devices at its endpoints share at least one active interface. Each interface is assumed to require an activation cost, and provides a communication bandwidth. In this paper, we consider two fundamental optimization problems. In the first one, we aim to activate a set of interfaces in the network G = (V, E) in order to guarantee the maximal bandwidth between two given nodes. Nodes V represent the devices, edges E represent the connections that can be established according to the availability of the interfaces in the devices. In the second problem, we look for activating the cheapest set of interfaces among a network in order to guarantee a minimum bandwidth B of communication between two specified nodes. We show that the first problem is polynomially solvable while the second one is NP-Hard. However, we experimentally analyzed an algorithm for the second problem, showing that in practical cases it guarantees a low approximation ratio which allows us to use it in real-world networks.

@inproceedings{DDN11d,

 hal_id = {hal-00644073},

 url = {http://hal.inria.fr/hal-00644073/en/},

 title = {{Maximum Flow and Minimum-Cost Flow in Multi-Interface Networks}},

 author = {G. D'Angelo and Di Stefano, Gabriele and Navarra, Alfredo},

 abstract = {{In heterogeneous networks, devices can communicate by means of multiple wired or wireless interfaces. By switching among interfaces or by combining the available interfaces, each device might establish several connections. A connection is established when the devices at its endpoints share at least one active interface. Each interface is assumed to require an activation cost, and provides a communication bandwidth. In this paper, we consider two fundamental optimization problems. In the first one, we aim to activate a set of interfaces in the network G = (V, E) in order to guarantee the maximal bandwidth between two given nodes. Nodes V represent the devices, edges E represent the connections that can be established according to the availability of the interfaces in the devices. In the second problem, we look for activating the cheapest set of interfaces among a network in order to guarantee a minimum bandwidth B of communication between two specified nodes. We show that the first problem is 
 polynomially solvable while the second one is NP-Hard. However, we experimentally analyzed an algorithm for the second problem, showing that in practical cases it guarantees a low approximation ratio which allows us to use it in real-world networks.}},

 language = {English},

 booktitle = {{5th International Conference on Ubiquitous Information Management and Communication}},

 publisher = {ACM},

 pages = {19},

 address = {Seoul, Korea, Republic Of},

 doi = {10.1145/1968613.1968637 },

 year = {2011},

 month = Feb,

 pdf = {http://hal.inria.fr/hal-00644073/PDF/MultiInterfacesFlowExp.pdf},

 x-pays = {IT},

 x-editorial-board={yes},

 x-proceedings={yes},

 x-international-audience={yes},

 sorte = "conf-int",

 
}

G. D'Angelo, Gabriele Di Stefano, and Alfredo Navarra. Min-Max Coverage in Multi-interface Networks. In Ivana Cerná, Tibor Gyimóthy, Juraj Hromkovic, Keith Jefferey, Rastislav Královic, Marko Vukolic, and Stefan Wolf, editors, 37th Conference on Current Trends in Theory and Practice of Computer Science, volume 6543 of Lecture Notes in Computer Science, Novy Smokovec, Slovakia, pages 190-201, January 2011. Springer. [WWW ] [PDF ]

Abstract:

We consider devices equipped with multiple wired or wireless interfaces. By switching among interfaces or by combining the available interfaces, each device might establish several connections. A connection is established when the devices at its endpoints share at least one active interface. Each interface is assumed to require an activation cost. In this paper, we consider the problem of establishing the connections defined by a network Gâ=â(V,E) while keeping as low as possible the maximum cost set of active interfaces at the single nodes. Nodes V represent the devices, edges E represent the connections that must be established. We study the problem of minimizing the maximum cost set of active interfaces among the nodes of the network in order to cover all the edges. We prove that the problem is NP-hard for any fixed $\Delta$â$\ge$â5 and kâ$\ge$â16, with $\Delta$ being the maximum degree, and k being the number of different interfaces among the network. We also show that the problem cannot be approximated within $\Omega$(ln $\Delta$). We then provide a general approximation algorithm which guarantees a factor of O((1â+âb)ln ($\Delta$)), with b being a parameter depending on the topology of the input graph. Interestingly, b can be bounded by a constant for many graph classes. Other approximation and exact algorithms for special cases are presented.

@inproceedings{DDN11f,

 hal_id = {hal-00644084},

 url = {http://hal.inria.fr/hal-00644084/en/},

 title = {{Min-Max Coverage in Multi-interface Networks}},

 author = {G. D'Angelo and Di Stefano, Gabriele and Navarra, Alfredo},

 abstract = {{We consider devices equipped with multiple wired or wireless interfaces. By switching among interfaces or by combining the available interfaces, each device might establish several connections. A connection is established when the devices at its endpoints share at least one active interface. Each interface is assumed to require an activation cost. In this paper, we consider the problem of establishing the connections defined by a network Gâ=â(V,E) while keeping as low as possible the maximum cost set of active interfaces at the single nodes. Nodes V represent the devices, edges E represent the connections that must be established. We study the problem of minimizing the maximum cost set of active interfaces among the nodes of the network in order to cover all the edges. We prove that the problem is NP-hard for any fixed $\Delta$â$\ge$â5 and kâ$\ge$â16, with $\Delta$ being the maximum degree, and k being the number of different interfaces among the network. We also show that the problem cannot be 
 approximated within $\Omega$(ln $\Delta$). We then provide a general approximation algorithm which guarantees a factor of O((1â+âb)ln ($\Delta$)), with b being a parameter depending on the topology of the input graph. Interestingly, b can be bounded by a constant for many graph classes. Other approximation and exact algorithms for special cases are presented.}},

 language = {English},

 booktitle = {{37th Conference on Current Trends in Theory and Practice of Computer Science}},

 publisher = {Springer},

 pages = {190-201},

 address = {Nov{\'y} Smokovec, Slovakia},

 volume = {6543},

 editor = {Ivana Cern{\'a} and Tibor Gyim{\'o}thy and Juraj Hromkovic and Keith Jefferey and Rastislav Kr{\'a}lovic and Marko Vukolic and Stefan Wolf },

 series = {Lecture Notes in Computer Science },

 audience = {international },

 doi = {10.1007/978-3-642-18381-2\_16 },

 year = {2011},

 month = Jan,

 pdf = {http://hal.inria.fr/hal-00644084/PDF/MultiInterfacesCoverage.pdf},

 x-pays = {IT},

 x-editorial-board={yes},

 x-proceedings={yes},

 x-international-audience={yes},

 sorte = "conf-int",

 
}

G. D'Angelo, Daniele Frigioni, and Camillo Vitale. Dynamic Arc-Flags in Road Networks. In Panos M. Pardalos and Steffen Rebennack, editors, 10th International Symposium, SEA 2011, volume 6630 of Lecture Notes in Computer Science, Kolimpari, Chania, Crete, Greece, pages 88-99, April 2011. Springer. [WWW ] [PDF ]

Abstract:

In this work we introduce a new data structure, named Road-Signs, which allows us to efficiently update the Arc-Flags of a graph in a dynamic scenario. Road-Signs can be used to compute Arc-Flags, can be efficiently updated and do not require large space consumption for many real-world graphs like, e.g., graphs arising from road networks. In detail, we define an algorithm to preprocess Road-Signs and an algorithm to update them each time that a weight increase operation occurs on an edge of the network. We also experimentally analyze the proposed algorithms in real-world road networks showing that they yields a significant speed-up in the updating phase of Arc-Flags, at the cost of a very small space and time overhead in the preprocessing phase.

@inproceedings{DDV11c,

 hal_id = {hal-00644054},

 url = {http://hal.inria.fr/hal-00644054/en/},

 title = {{Dynamic Arc-Flags in Road Networks}},

 author = {G. D'Angelo and Frigioni, Daniele and Vitale, Camillo},

 abstract = {{In this work we introduce a new data structure, named Road-Signs, which allows us to efficiently update the Arc-Flags of a graph in a dynamic scenario. Road-Signs can be used to compute Arc-Flags, can be efficiently updated and do not require large space consumption for many real-world graphs like, e.g., graphs arising from road networks. In detail, we define an algorithm to preprocess Road-Signs and an algorithm to update them each time that a weight increase operation occurs on an edge of the network. We also experimentally analyze the proposed algorithms in real-world road networks showing that they yields a significant speed-up in the updating phase of Arc-Flags, at the cost of a very small space and time overhead in the preprocessing phase.}},

 language = {English},

 booktitle = {{10th International Symposium, SEA 2011}},

 publisher = {Springer},

 pages = {88-99},

 address = {Kolimpari, Chania, Crete, Greece},

 volume = {6630},

 editor = {Panos M. Pardalos and Steffen Rebennack },

 series = {Lecture Notes in Computer Science },

 doi = {10.1007/978-3-642-20662-7\_8 },

 year = {2011},

 month = Apr,

 pdf = {http://hal.inria.fr/hal-00644054/PDF/RoadSigns.pdf},

 x-pays = {IT},

 x-editorial-board={yes},

 x-proceedings={yes},

 x-international-audience={yes},

 sorte = "conf-int",

 
}

O. Dalle and E. Mancini. Traces Generation To Simulate Large-Scale Distributed Applications. In S. Jain, R. R. Creasey, J. Himmelspach, K. P. White, and M. Fu, editors, Winter Simulation Conference, Phoenix, AZ, États-Unis, pages 10p., December 2011. [WWW ] [PDF ]

Abstract:

In order to study the performance of scheduling algorithms, simulators of parallel and distributed applications need accurate models of the application's behavior during execution. For this purpose, traces of low-level events collected during the actual execution of real applications are needed. Collecting such traces is a difficult task due to the timing, to the interference of instrumentation code, and to the storage and transfer of the collected data. To address this problem we propose a comprehensive software architecture, which instruments the application's executables, gather hierarchically the traces, and post-process them in order to feed simulation models. We designed it to be scalable, modular and extensible.

@inproceedings{DaMa11,

 hal_id = {inria-00638561},

 url = {http://hal.inria.fr/inria-00638561},

 title = {{Traces Generation To Simulate Large-Scale Distributed Applications}},

 author = {Dalle, O. and Mancini, E.},

 abstract = {{In order to study the performance of scheduling algorithms, simulators of parallel and distributed applications need accurate models of the application's behavior during execution. 
 For this purpose, traces of low-level events collected during the actual execution of real applications are needed. 
 Collecting such traces is a difficult task due to the timing, to the interference of instrumentation code, and to the storage and transfer of the collected data. 
 To address this problem we propose a comprehensive software architecture, which instruments the application's executables, gather hierarchically the traces, and post-process them in order to feed simulation models. 
 We designed it to be scalable, modular and extensible.}},

 booktitle = {{Winter Simulation Conference}},

 pages = {10p.},

 address = {Phoenix, AZ, {\'E}tats-Unis},

 editor = {Jain, S. and Creasey, R. R. and Himmelspach, J. and White, K. P. and Fu, M. },

 year = {2011},

 month = Dec,

 pdf = {http://hal.inria.fr/inria-00638561/PDF/MaDa11.pdf},

 x-editorial-board={yes},

 x-proceedings={yes},

 x-international-audience={yes},

 sorte = "conf-int",

 
}

O. Dalle and J. Ribault. Some Desired Features for the DEVS Architecture Description Language. In Proceedings of the Symposium On Theory of Modeling and Simulation -- DEVS Integrative M&S Symposium (TMS/DEVS 2011), volume Book 4 -- Symposium on Theory of Modeling & Simulation - DEVS Integrative M&S Symposium (TMS/DEVS), Boston, MA, États-Unis, pages 258-263, 04 2011. [WWW ] [PDF ]

Abstract:

ADL are particularly well suited for component-based model frameworks that support hierarchical composition, such as DEVS with coupled models. In this paper we present some features found in the ADL of another hierarchical component model, namely the Fractal Component Model (FCM). To our best knowledge, these features are not yet available in most of the current DEVS implementations. Using a few examples coming from our experience, we demonstrate the usefulness of these features for Modeling & Simulation and their potential relevance for inclusion in a future DEVS implementation standard.

@InProceedings{DaRi11,

 author = {O. Dalle and J. Ribault},

 title = {Some Desired Features for the DEVS Architecture Description Language},

 booktitle = {Proceedings of the Symposium On Theory of Modeling and Simulation -- DEVS Integrative M\&S Symposium (TMS/DEVS 2011)},

 year = {2011},

 pages = {258-263},

 address = {Boston, MA, {\'E}tats-Unis},

 volume = {Book 4 -- Symposium on Theory of Modeling \& Simulation - DEVS Integrative M\&S Symposium (TMS/DEVS)},

 month = {04},

 url = {http://hal.inria.fr/inria-00638565/en/},

 pdf = {http://hal.inria.fr/inria-00638565/PDF/document.pdf},

 abstract = {ADL are particularly well suited for component-based model
 frameworks that support hierarchical composition, such as DEVS with coupled
 models. In this paper we present some features found in the ADL of another
 hierarchical component model, namely the Fractal Component Model (FCM).
 To our best knowledge, these features are not yet available in most of the
 current DEVS implementations. Using a few examples coming from our experience,
 we demonstrate the usefulness of these features for Modeling & Simulation and
 their potential relevance for inclusion in a future DEVS implementation
 standard.},

 x-editorial-board={yes},

 x-proceedings={no},

 x-international-audience={yes},

 sorte = "conf-int",

 
}

S. Felix and J. Galtier. Shortest Paths and Probabilities on Time-Dependent Graphs - Applications to Transport Networks. In Proceedings of the 11th International Conference on ITS Telecommunications, Saint Petersburg, Russia, pages 56--62, August 2011. [WWW ]

Abstract:

In this paper, we focus on time-dependent graphs which seem to be a good way to model transport networks. In the first part, we remind some notations and techniques related to time-dependent graphs. In the second one, we introduce new algorithms to take into account the notion of probability related to paths in order to guarantee travelling times with a certain accuracy. We also discuss different probabilistic models and show the links between them.

@inproceedings{Fe11,

 address = {Saint Petersburg, Russia},

 author = {S. Felix and J. Galtier},

 booktitle = {Proceedings of the 11th International Conference on ITS Telecommunications},

 pages = {56--62},

 month = {August},

 title = {Shortest Paths and Probabilities on Time-Dependent Graphs - Applications to Transport Networks},

 year = 2011,

 isbn = {978-1-60558-945-9},

 url={http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=06060121},

 abstract = {In this paper, we focus on time-dependent graphs
 which seem to be a good way to model transport networks. In
 the first part, we remind some notations and techniques related
 to time-dependent graphs. In the second one, we introduce new
 algorithms to take into account the notion of probability related
 to paths in order to guarantee travelling times with a certain
 accuracy. We also discuss different probabilistic models and show
 the links between them.},

 x-editorial-board={yes},

 x-proceedings={yes},

 x-international-audience={yes},

 sorte = "conf-int",

 
}

F. Giroire, D. Mazauric, and J. Moulierac. Routage efficace en énergie. 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 ]

Abstract:

De rÃ©centes Ã©tudes montrent que la charge de trafic des routeurs n'a qu'une faible influence sur leur consommation Ã©nergÃ©tique. Par consÃ©quent, la consommation dans les rÃ©seaux est fortement liÃ©e au nombre d'Ã©quipements du rÃ©seau activÃ©s (interfaces, chassis, etc). Dans un objectif de minimisation de l'Ã©nergie dans les rÃ©seaux, il est intÃ©ressant de minimiser le nombre (pondÃ©rÃ©) d'Ã©quipements utilisÃ©s lors du routage. Dans cet article, nous considÃ©rons une architecture simplifiÃ©e oÃ¹ un lien entre deux routeurs relie deux interfaces. Quand un lien n'est pas activÃ©, les deux interfaces correspondantes peuvent Ãªtre Ã©teintes. Par consÃ©quent, afin de rÃ©duire la consommation d'Ã©nergie, l'objectif est de trouver un routage qui minimise le nombre de liens utilisÃ©s et satisfait toutes les demandes. Nous montrons des rÃ©sultats d'inapproximabilitÃ© de ce problÃ¨me, mÃªme si l'on considÃ¨re des instances particuliÃ¨res. Nous prouvons des bornes en gÃ©nÃ©ral et pour des topologies particuliÃ¨res telles que la grille, l'arbre ou le graphe complet. Nous proposons ensuite une heuristique dont nous Ã©valuons les performances Ã l'aide de simulations sur des topologies rÃ©elles. Nous Ã©tudions ensuite l'impact de ces solutions efficaces en Ã©nergie sur la tolÃ©rance aux pannes et sur la longueur moyenne des routes.

@inproceedings{GMM11,

 author = {Giroire, F. and Mazauric, D. and Moulierac, J.},

 title = {{Routage efficace en \'energie}},

 booktitle = {13es Rencontres Francophones sur les Aspects
 Algorithmiques de T\'el\'ecommunications (AlgoTel)},

 year = {2011},

 editor = {Ducourthial et Bertrand et Felber et Pascal},

 address = {Cap Est\'erel, France},

 url = {http://hal.inria.fr/inria-00587944/fr},

 abstract = {De rÃ©centes Ã©tudes montrent que la charge de trafic des
 routeurs n'a qu'une faible influence sur leur consommation
 Ã©nergÃ©tique. Par consÃ©quent, la consommation dans les rÃ©seaux est
 fortement liÃ©e au nombre d'Ã©quipements du rÃ©seau activÃ©s (interfaces,
 chassis, etc). Dans un objectif de minimisation de l'Ã©nergie dans les
 rÃ©seaux, il est intÃ©ressant de minimiser le nombre (pondÃ©rÃ©)
 d'Ã©quipements utilisÃ©s lors du routage. Dans cet article, nous
 considÃ©rons une architecture simplifiÃ©e oÃ¹ un lien entre deux routeurs
 relie deux interfaces. Quand un lien n'est pas activÃ©, les deux
 interfaces correspondantes peuvent Ãªtre Ã©teintes. Par consÃ©quent, afin
 de rÃ©duire la consommation d'Ã©nergie, l'objectif est de trouver un
 routage qui minimise le nombre de liens utilisÃ©s et satisfait toutes
 les demandes. Nous montrons des rÃ©sultats d'inapproximabilitÃ© de ce
 problÃ¨me, mÃªme si l'on considÃ¨re des instances particuliÃ¨res. Nous
 prouvons des bornes en gÃ©nÃ©ral et pour des topologies particuliÃ¨res
 telles que la grille, l'arbre ou le graphe complet. Nous proposons
 ensuite une heuristique dont nous Ã©valuons les performances Ã l'aide
 de simulations sur des topologies rÃ©elles. Nous Ã©tudions ensuite
 l'impact de ces solutions efficaces en Ã©nergie sur la tolÃ©rance aux
 pannes et sur la longueur moyenne des routes.},

 x-editorial-board={yes},

 x-proceedings={yes},

 x-international-audience={no},

 x-pays = {MA},

 sorte = "conf-nat",

 
 
}

Y. Liu and G. Simon. Peer-Assisted Time-shifted Streaming Systems: Design and Promises. In IEEE International Conference on Communications (ICC'2011), Kyoto, Japan, 06 2011. IEEE. [PDF ]

Abstract:

Time-shifted streaming (or catch-up TV) allows viewers to watch their TV programs within an expanded time window. In this paper, we emphasize the challenging characteristics of time-shifted TV systems that prevent known delivery systems to be used. We model time-shifted TV as multiple-interval graph, then we present a Peer-Assisted Catch-Up Streaming system, namely PACUS, where a set of end users' computers assists the server for the content delivery. We show in particular how the PACUS tracker server can be efficiently implemented for catch-up TV. We demonstrate the benefits of PACUS by simulations. We especially highlight that PACUS reduces the traffic at the server side with the advantages of lightweight and self-adaptive unstructured peer-to-peer systems.

@InProceedings{LiSi+11,

 author = {Y. Liu and G. Simon},

 title = {Peer-Assisted Time-shifted Streaming Systems: Design and Promises},

 booktitle = {IEEE International Conference on Communications (ICC'2011)},

 year = {2011},

 address = {Kyoto, Japan},

 month = {06},

 publisher = {IEEE},

 abstract = { Time-shifted streaming (or catch-up TV) allows viewers to watch their TV programs within an expanded time window. In this paper, we emphasize the challenging characteristics of time-shifted TV systems that prevent known delivery systems to be used. We model time-shifted TV as multiple-interval graph, then we present a Peer-Assisted Catch-Up Streaming system, namely PACUS, where a set of end users' computers assists the server for the content delivery. We show in particular how the PACUS tracker server can be efficiently implemented for catch-up TV. We demonstrate the benefits of PACUS by simulations. We especially highlight that PACUS reduces the traffic at the server side with the advantages of lightweight and self-adaptive unstructured peer-to-peer systems.},

 pdf = {ftp://ftp-sop.inria.fr/mascotte/Publications/LS+11.pdf},

 x-editorial-board={yes},

 x-proceedings={yes},

 x-international-audience={yes},

 x-pays={},

 sorte = "conf-int",

 
}

F. Maffray and G. Morel. Algorithmes linÃ©aires pour les graphes sans $P_5$ 3-colorables. In 12e congrès annuel de la ROADEF, 2011.

@inproceedings{MaMo11b,

 title = {{ Algorithmes linÃ©aires pour les graphes sans $P_5$ 3-colorables}},

 author={Maffray, F. and Morel, G.},

 booktitle={12e congr\`es annuel de la ROADEF},

 year={2011},

 x-editorial-board = {no},

 x-proceedings = {yes},

 x-international-audience = {no},

 sorte = "conf-nat",

 
}

Internal reports

P. Aboulker, F. Havet, and N. Trotignon. On wheel-free graphs. Research Report RR-7651, INRIA, June 2011. [WWW ] [PDF ]

Abstract:

A wheel is a graph formed by a chordless cycle and a vertex that has at least three neighbors in the cycle. We prove that every 3-connected graph that does not contain a wheel as a subgraph is in fact minimally 3-connected. We prove that every graph that does not contain a wheel as a subgraph is 3-colorable.

@techreport{AHT11,

 hal_id= {inria-00602079},

 url = {http://hal.inria.fr/inria-00602079/en/},

 title = {{On wheel-free graphs}},

 author = {P. Aboulker and F. Havet and N. Trotignon},

 abstract = {{A wheel is a graph formed by a chordless cycle and a vertex that has at least three neighbors in the cycle. We prove that every 3-connected graph that does not contain a wheel as a subgraph is in fact minimally 3-connected. We prove that every graph that does not contain a wheel as a subgraph is 3-colorable.}},

 language = {Anglais},

 affiliation = {Laboratoire d'informatique Algorithmique : Fondements et Applications - LIAFA - CNRS : UMR7089 - Universit\'e Paris Diderot - Paris 7 - MASCOTTE - INRIA Sophia Antipolis / Laboratoire I3S - INRIA - Universit\'e de Nice Sophia-Antipolis - CNRS : UMR6070},

 type = {Research Report},

 institution = {INRIA},

 number = {RR-7651},

 year = {2011},

 month = Jun,

 pdf = {http://hal.inria.fr/inria-00602079/PDF/RR-7651.pdf},

 x-editorial-board={no},

 x-proceedings={yes},

 x-international-audience={yes},

 
}

L. Addario-Berry, F. Havet, C. Linhares Sales, B. Reed, and S. Thomassé. Oriented trees in digraphs. Research Report 7502, INRIA, 01 2011. [WWW ] [PDF ]

Abstract:

Let $f(k)$ be the smallest integer such that every $f(k)$-chromatic digraph contains every oriented tree of order $k$. Burr proved that $f(k)\leq (k-1)^2$ and conjectured $f(k)=2n-2$. In this paper, we give some sufficient conditions for an $n$-chromatic digraphs to contains some oriented tree. In particular, we show that every acyclic $n$-chromatic digraph contains every oriented tree of order $n$. We also show that $f(k)\leq k^2/2-k/2+1$. Finally, we consider the existence of antidirected trees in digraphs. We prove that every antidirected tree of order $k$ is contained in every $(5k-9)$-chromatic digraph. We conjecture that if $|E(D)| > (k-2) |V(D)|$, then the digraph $D$ contains every antidirected tree of order $k$. This generalizes Burr's conjecture for antidirected trees and the celebrated Erd\H{o}s-S\'os Conjecture. We give some evidences for our conjecture to be true.

@TechReport{AHL+11,

 author = {Addario-Berry, L. and Havet, F. and Linhares Sales, C. and Reed, B. and Thomass\'e, S.},

 title = {Oriented trees in digraphs},

 year = {2011},

 month = {01},

 institution = {INRIA},

 number = {7502},

 type = {Research Report},

 URL = {http://hal.inria.fr/inria-00551133/fr/},

 PDF = {http://hal.inria.fr/docs/00/55/11/33/PDF/RR-7502.pdf},

 abstract = {Let $f(k)$ be the smallest integer such that every $f(k)$-chromatic digraph contains every oriented tree of order $k$.
 Burr proved that $f(k)\leq (k-1)^2$ and conjectured $f(k)=2n-2$.
 In this paper, we give some sufficient conditions for an $n$-chromatic digraphs to contains some oriented tree.
 In particular, we show that every acyclic $n$-chromatic digraph contains every oriented tree of order $n$.
 We also show that $f(k)\leq k^2/2-k/2+1$.
 Finally, we consider the existence of antidirected trees in digraphs.
 We prove that every antidirected tree of order $k$ is contained in every $(5k-9)$-chromatic digraph.
 We conjecture that if $|E(D)| > (k-2) |V(D)|$,
 then the digraph $D$ contains every antidirected tree of order $k$.
 This generalizes Burr's conjecture for antidirected trees and the celebrated Erd\H{o}s-S\'os Conjecture.
 We give some evidences for our conjecture to be true.},

 sorte = {Rapports},

 x-editorial-board={yes},

 x-proceedings={yes},

 x-international-audience={yes},

 x-pays={BR,CA},

 
}

J. Araujo, J-C. Bermond, F. Giroire, F. Havet, D. Mazauric, and R. Modrzejewski. Weighted Improper Colouring. Research Report RR-7590, INRIA, 04 2011. [WWW ] [PDF ]
Keywords: graph colouring, improper colouring, grids, integer programming, algorithms.

Abstract:

{I}n this paper, we study a new colouring problem up to our best knowledge inspired by the imperative of practical networks. {I}n real-life wireless networks, nodes interfere with one another with various intensities depending on numerous parameters: distance between them, the geographical topography, obstacles, etc. {W}e model this with a noise matrix. {T}he interference perceived by a node then is the sum of all the noise of the nodes emitting on the same frequency. {T}he problem is then to determine the minimum number of colours (or frequencies) needed to colour the whole graph so that the interference does not exceed a given threshold. {W}e provide several general results, such as bounds on this number of colours (e.g. a {B}rook's like theorem). {W}e then study the practical case of square of infinite grids which corresponds to operators' network and a noise decreasing with the distance. {W}e provide the chromatic number of the square, triangular and hexagonal grids for all possible admissible interference levels. {F}inally, we model the problem using linear programming, propose and test a heuristic and an exact branch\&bound algorithms on random cell-like graphs, namely the {P}oisson {V}oronoi tessellations.

@techreport{ABGH+11a,

 url = {http://hal.inria.fr/inria-00583036/en/},

 title = { {W}eighted {I}mproper {C}olouring},

 author = {J. Araujo and J-C. Bermond and F. Giroire and F. Havet and D. Mazauric and R. Modrzejewski},

 abstract = {{I}n this paper, we study a new colouring problem up to our best knowledge inspired by the imperative of practical networks. {I}n real-life wireless networks, nodes interfere with one another with various intensities depending on numerous parameters: distance between them, the geographical topography, obstacles, etc. {W}e model this with a noise matrix. {T}he interference perceived by a node then is the sum of all the noise of the nodes emitting on the same frequency. {T}he problem is then to determine the minimum number of colours (or frequencies) needed to colour the whole graph so that the interference does not exceed a given threshold. {W}e provide several general results, such as bounds on this number of colours (e.g. a {B}rook's like theorem). {W}e then study the practical case of square of infinite grids which corresponds to operators' network and a noise decreasing with the distance. {W}e provide the chromatic number of the square, triangular and hexagonal grids for all possible 
 admissible interference levels. {F}inally, we model the problem using linear programming, propose and test a heuristic and an exact branch\&bound algorithms on random cell-like graphs, namely the {P}oisson {V}oronoi tessellations.},

 keywords = {graph colouring, improper colouring, grids, integer programming, algorithms},

 language = {{A}nglais},

 affiliation = {{MASCOTTE} - {INRIA} {S}ophia {A}ntipolis / {L}aboratoire {I}3{S} - {INRIA} - {U}niversit{\'e} de {N}ice {S}ophia-{A}ntipolis - {CNRS} : {UMR}6070 - {P}arallelism, {G}raphs and {O}ptimization {R}esearch {G}roup - {P}ar{GO} - {U}niversidade {F}ederal do {C}eara - {MAESTRO} - {INRIA} {S}ophia {A}ntipolis - {INRIA} - {U}niversit{\'e} {M}ontpellier {II} - {S}ciences et {T}echniques du {L}anguedoc },

 pages = {16 },

 type = {Research Report},

 institution = {INRIA},

 number = {{RR}-7590},

 month = {04},

 year = {2011},

 pdf = {http://hal.inria.fr/inria-00583036/PDF/RR-7590.pdf},

 sorte = {Rapports},

 x-editorial-board={no},

 x-proceedings={no},

 x-international-audience={yes},

 
}

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:

In this paper, we study the geodetic convexity of graphs focusing on the problem of the complexity to compute inclusion-minimum hull set of a graph in several graph classes. For any two vertices $u,v\in V$ of a connected graph $G=(V,E)$, the {\em closed interval} $I[u,v]$ of $u$ and $v$ is the the set of vertices that belong to some shortest $(u,v)$-path. For any $S \subseteq V$, let $I[S]= \bigcup\_{u,v\in S} I[u,v]$. A subset $S\subseteq V$ is {\em geodesically convex} if $I[S] = S$. In other words, a subset $S$ is convex if, for any $u,v \in S$ and for any shortest $(u,v)$-path $P$, $V(P) \subseteq S$. Given a subset $S\subseteq V$, the {\em convex hull} $I\_h[S]$ of $S$ is the smallest convex set that contains $S$. We say that $S$ is a {\em hull set} of $G$ if $I\_h[S] = V$. The size of a minimum hull set of $G$ is the {\em hull number} of $G$, denoted by $hn(G)$. The {\sc Hull Number} problem is to decide whether $hn(G)\leq k$, for a given graph $G$ and an integer $k$. Dourado {\it et al.} showed that this problem is NP-complete in general graphs. In this paper, we answer an open question of Dourado et al.\~\cite{Douradoetal09} by showing that the {\sc Hull Number} problem is NP-hard even when restricted to the class of bipartite graphs. Then, we design polynomial time algorithms to solve the {\sc Hull Number} problem in several graph classes. First, we deal with the class of complements of bipartite graphs. Then, we generalize some results in\~\cite{ACGSS11} to the class of $(q,q-4)$-graphs and to the class of cacti. Finally, we prove tight upper bounds on the hull numbers. In particular, we show that the hull number of an $n$-node graph $G$ without simplicial vertices is at most $1+\lceil \frac{3(n-1)}{5}\rceil$ in general, at most $1+\lceil \frac{n-1}{2}\rceil$ if $G$ is regular or has no triangle, and at most $1+\lceil \frac{n-1}{3}\rceil$ if $G$ has girth at least $6$.

@techreport{ACG+11,

 url = {http://hal.inria.fr/inria-00576581/en/},

 title = {{On the hull number of some graph classes}},

 author = {J. Araujo and V. Campos and F. Giroire and N. Nisse and L. Sampaio and R. Soares},

 abstract = {{In this paper, we study the geodetic convexity of graphs focusing on the problem of the complexity to compute inclusion-minimum hull set of a graph in several graph classes. For any two vertices $u,v\in V$ of a connected graph $G=(V,E)$, the {\em closed interval} $I[u,v]$ of $u$ and $v$ is the the set of vertices that belong to some shortest $(u,v)$-path. For any $S \subseteq V$, let $I[S]= \bigcup\_{u,v\in S} I[u,v]$. A subset $S\subseteq V$ is {\em geodesically convex} if $I[S] = S$. In other words, a subset $S$ is convex if, for any $u,v \in S$ and for any shortest $(u,v)$-path $P$, $V(P) \subseteq S$. Given a subset $S\subseteq V$, the {\em convex hull} $I\_h[S]$ of $S$ is the smallest convex set that contains $S$. We say that $S$ is a {\em hull set} of $G$ if $I\_h[S] = V$. The size of a minimum hull set of $G$ is the {\em hull number} of $G$, denoted by $hn(G)$. The {\sc Hull Number} problem is to decide whether $hn(G)\leq k$, for a given graph $G$ and an integer $k$. Dourado {\it et al.} 
 showed that this problem is NP-complete in general graphs. In this paper, we answer an open question of Dourado et al.\~\cite{Douradoetal09} by showing that the {\sc Hull Number} problem is NP-hard even when restricted to the class of bipartite graphs. Then, we design polynomial time algorithms to solve the {\sc Hull Number} problem in several graph classes. First, we deal with the class of complements of bipartite graphs. Then, we generalize some results in\~\cite{ACGSS11} to the class of $(q,q-4)$-graphs and to the class of cacti. Finally, we prove tight upper bounds on the hull numbers. In particular, we show that the hull number of an $n$-node graph $G$ without simplicial vertices is at most $1+\lceil \frac{3(n-1)}{5}\rceil$ in general, at most $1+\lceil \frac{n-1}{2}\rceil$ if $G$ is regular or has no triangle, and at most $1+\lceil \frac{n-1}{3}\rceil$ if $G$ has girth at least $6$.}},

 pages = {19},

 sorte = {Rapports},

 institution = {INRIA},

 number = {RR-7567},

 year = {2011},

 month = Sep,

 pdf = {http://hal.inria.fr/inria-00576581/PDF/hn-RR\_v2.pdf},

 x-editorial-board={no},

 x-proceedings={no},

 x-international-audience={no},

 x-pays = {BR},

 
}

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:

In this work we study the computational power of graph-based models of distributed computing in which each node additionally has access to a global whiteboard. A node can read the contents of the whiteboard and, when activated, can write one message of $O(\log n)$ bits on it. A message is only based on the local knowledge of the node and the current content of the whiteboard. When the protocol terminates, each node computes the output based on the final contents of the whiteboard in order to answer some question on the network's topology. We propose a framework to formally define several scenarios modelling how nodes access the whiteboard, in a synchronous way or not. This extends the work of Becker {\it et al.} [IPDPS 2011] where nodes were imposed to create their messages only based on their local knowledge (i.e., with the whiteboard empty). We prove that the four models studied have increasing power of computation: any problem that can be solved in the weakest one can be solved in the the second, and so on. Moreover, we exhibit problems that {\it separate} models, i.e., that can be solved in one model but not in a weaker one. These problems are related to Maximal Independent Set and detection of cycles. Finally we investigate problems related to connectivity as the construction of spanning- or BFS-tree in our different models.

@techreport{BKN+11,

 url = {http://hal.inria.fr/inria-00627910/en/},

 title = {{Interconnection network with a shared whiteboard: Impact of (a)synchronicity on computing power}},

 author = {Becker, F. and Kosowski, A. and Nisse, N. and Rapaport, I. and Suchan, K.},

 abstract = {{In this work we study the computational power of graph-based models of distributed computing in which each node additionally has access to a global whiteboard. A node can read the contents of the whiteboard and, when activated, can write one message of $O(\log n)$ bits on it. A message is only based on the local knowledge of the node and the current content of the whiteboard. When the protocol terminates, each node computes the output based on the final contents of the whiteboard in order to answer some question on the network's topology. We propose a framework to formally define several scenarios modelling how nodes access the whiteboard, in a synchronous way or not. This extends the work of Becker {\it et al.} [IPDPS 2011] where nodes were imposed to create their messages only based on their local knowledge (i.e., with the whiteboard empty). We prove that the four models studied have increasing power of computation: any problem that can be solved in the weakest one can be solved in the the 
 second, and so on. Moreover, we exhibit problems that {\it separate} models, i.e., that can be solved in one model but not in a weaker one. These problems are related to Maximal Independent Set and detection of cycles. Finally we investigate problems related to connectivity as the construction of spanning- or BFS-tree in our different models.}},

 sorte = {Rapports},

 institution = {INRIA},

 number = {RR-7746},

 year = {2011},

 pdf = {http://hal.inria.fr/inria-00627910/PDF/RR-7746.pdf},

 x-editorial-board={no},

 x-proceedings={no},

 x-international-audience={no},

 x-pays = {CL,PL},

 
}

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:

In a WDM network, setting up a new wavelength in a fiber requires recalibrating the other wavelengths passing through this fiber. This induces a cost (e.g., time, energy, degradation of QoS) that depends nonlinearly on the number of wavelengths using the fiber. When a set of connection requests must change their optical paths in the network (e.g., during a maintenance operation on a link in the network), the order in which requests are switched affects the total cost of the operation. That is, the reconfiguration of the routing in a WDM network has some cost due to physical layer impairments. We initiate the study of the corresponding optimization problem by modeling the cost of switching a request as a non-linear function depending on the load of the links used by the new lightpath. We prove that determining the optimal rerouting order is NP-complete for a $2$-nodes network. We then give general lower and upper bounds on the minimum cost and we identify classes of instances where the problem can be solved in polynomial time. Finally, we design heuristics for this problem and we analyze and compare them by simulations.

@techreport{BCM+11c,

 AUTHOR = {Belhareth, S. and Coudert, D. and Mazauric, D. and Nisse, N. and Tahiri, I.},

 TITLE = {{Reconfiguration with physical constraints in WDM networks}},

 TYPE = {Research Report},

 YEAR = {2011},

 KEYWORDS = {Reconfiguration, WDM, NP-complete, Physical Layer Impaiments.},

 INSTITUTION = {INRIA},

 NUMBER = {RR-7850},

 URL = {http://hal.inria.fr/hal-00654111/en},

 PDF = {http://hal.inria.fr/docs/00/65/41/11/PDF/RR-7850.pdf},

 abstract = {In a WDM network, setting up a new wavelength in a fiber requires recalibrating the other wavelengths passing through this fiber. This induces a cost (e.g., time, energy, degradation of QoS) that depends nonlinearly on the number of wavelengths using the fiber. When a set of connection requests must change their optical paths in the network (e.g., during a maintenance operation on a link in the network), the order in which requests are switched affects the total cost of the operation. That is, the reconfiguration of the routing in a WDM network has some cost due to physical layer impairments. We initiate the study of the corresponding optimization problem by modeling the cost of switching a request as a non-linear function depending on the load of the links used by the new lightpath. We prove that determining the optimal rerouting order is NP-complete for a $2$-nodes network. We then give general lower and upper bounds on the minimum cost and we identify classes of instances where the problem 

can be solved in polynomial time. Finally, we design heuristics for this problem and we analyze and compare them by simulations.},

 
}

J-C. Bermond, A. Jean-Marie, D. Mazauric, and J. Yu. Well Balanced Designs for Data Placement. Research Report 7725, INRIA, 09 2011. [WWW ]

Abstract:

The problem we consider in this article is motivated by data placement in particular data replication in video on demand systems. We are given a set $V$ of $n$ servers and $b$ files (data, documents). Each file is replicated on exactly $k$ servers. A placement consists in finding a family of $b$ subsets of $V$ (representing the files) called blocks each of size $k$. Each server has some probability to fail and we want to find a placement which minimizes the variance of the number of available files. It was conjectured that there always exists an optimal placement (with variance better than that of any other placement for any value of the probability of failure). We show that the conjecture is true, if there exists a well balanced design, that is a family of blocks, such that each j-element subset of $V$ , $1 \leq j \leq k$, belongs to the same or almost the same number of blocks (difference at most one). The existence of well balanced designs is a difficult problem as it contains as subproblem the existence of Steiner systems. We completely solve the case $k=2$ and give bounds and constructions for $k = 3$ and some values of $n$ and $b$.

@techreport{BJMY11,

 author = {Bermond, J-C. and Jean-Marie, A. and Mazauric, D. and Yu, J.},

 title = {Well Balanced Designs for Data Placement},

 year = {2011},

 month = {09},

 institution = {INRIA},

 number = {7725},

 type = {Research Report},

 url= {http://hal.inria.fr/inria-00618656},

 abstract = {The problem we consider in this article is motivated by
 data placement in particular data replication in video on demand
 systems. We are given a set $V$ of $n$ servers and $b$ files (data,
 documents). Each file is replicated on exactly $k$ servers. A
 placement consists in finding a family of $b$ subsets of $V$
 (representing the files) called blocks each of size $k$. Each server
 has some probability to fail and we want to find a placement which
 minimizes the variance of the number of available files. It was
 conjectured that there always exists an optimal placement (with
 variance better than that of any other placement for any value of the
 probability of failure). We show that the conjecture is true, if there
 exists a well balanced design, that is a family of blocks, such that
 each j-element subset of $V$ , $1 \leq j \leq k$, belongs to the same
 or almost the same number of blocks (difference at most one). The
 existence of well balanced designs is a difficult problem as it
 contains as subproblem the existence of Steiner systems. We completely
 solve the case $k=2$ and give bounds and constructions for $k = 3$ and
 some values of $n$ and $b$.},

 x-editorial-board={no},

 x-proceedings={no},

 x-international-audience={yes},

 x-pays = {MA},

 sorte = "Rapports",

 
}

S. Bessy and F. Havet. Enumerating the edge-colourings and total colourings of a regular graph. Research Report RR-7652, INRIA, June 2011. [WWW ] [PDF ]

Abstract:

In this paper, we are interested in computing the number of edge colourings and total colourings of a graph. We prove that the maximum number of $k$-edge-colourings of a $k$-regular graph on $n$ vertices is $k\cdot(k-1!)^{n/2}$. Our proof is constructible and leads to a branching algorithm enumerating all the $k$-edge-colourings of a $k$-regular graph using a time $O^*((k-1!)^{n/2})$ and polynomial space. In particular, we obtain a algorithm on time $O^*(2^{n/2})=O^*(1.4143^n)$ and polynomial space to enumerate all the $3$-edge colourings of a cubic graph, improving the running time of $O^*(1.5423^n)$ of the algorithm due to Golovach et al.\~\cite{GKC10}. We also show that the number of $4$-total-colourings of a connected cubic graph is at most $3.2^{3n/2}$. Again, our proof yields a branching algorithm to enumerate all the $4$-total-colourings of a connected cubic graph.

@techreport{BeHa11,

 hal_id = {inria-00602188},

 url = {http://hal.inria.fr/inria-00602188/en/},

 title = {{Enumerating the edge-colourings and total colourings of a regular graph}},

 author = {S. Bessy and F. Havet},

 abstract = {{In this paper, we are interested in computing the number of edge colourings and total colourings of a graph. We prove that the maximum number of $k$-edge-colourings of a $k$-regular graph on $n$ vertices is $k\cdot(k-1!)^{n/2}$. Our proof is constructible and leads to a branching algorithm enumerating all the $k$-edge-colourings of a $k$-regular graph using a time $O^*((k-1!)^{n/2})$ and polynomial space. In particular, we obtain a algorithm on time $O^*(2^{n/2})=O^*(1.4143^n)$ and polynomial space to enumerate all the $3$-edge colourings of a cubic graph, improving the running time of $O^*(1.5423^n)$ of the algorithm due to Golovach et al.\~\cite{GKC10}. We also show that the number of $4$-total-colourings of a connected cubic graph is at most $3.2^{3n/2}$. Again, our proof yields a branching algorithm to enumerate all the $4$-total-colourings of a connected cubic graph.}},

 language = {Anglais},

 type = {Research Report},

 affiliation = {Laboratoire d'Informatique de Robotique et de Micro\'electronique de Montpellier - LIRMM - CNRS : UMR5506 - Universit\'e Montpellier II - Sciences et Techniques du Languedoc - MASCOTTE - INRIA Sophia Antipolis / Laboratoire I3S - INRIA - Universit\'e de Nice Sophia-Antipolis - CNRS : UMR6070},

 institution = {INRIA},

 number = {RR-7652},

 year = {2011},

 month = Jun,

 pdf = {http://hal.inria.fr/inria-00602188/PDF/RR-7652.pdf},

 x-editorial-board={no},

 x-proceedings={yes},

 x-international-audience={yes},

 
}

V. Campos and F. Havet. 5-choosability of graphs with 2 crossings. Research Report RR-7618, INRIA, 05 2011. [WWW ] [PDF ]

Abstract:

{W}e show that every graph with two crossings is 5-choosable. {W}e also prove that every graph which can be made planar by removing one edge is 5-choosable.

@techreport{CaHa11,

 URL = {http://hal.inria.fr/inria-00593426/en/},

 title = { 5-choosability of graphs with 2 crossings},

 author = {V. Campos and F. Havet},

 abstract = {{W}e show that every graph with two crossings is 5-choosable. {W}e also prove that every graph which can be made planar by removing one edge is 5-choosable.},

 language = {{A}nglais},

 affiliation = {{L}aborat{\'o}rios de {P}esqu{I}sa em {C}omput{A}{\c{c}}{\~a}o - {LIA} - {U}niversite {F}ederale du {C}eara - {MASCOTTE} - {INRIA} {S}ophia {A}ntipolis / {L}aboratoire {I}3{S} - {INRIA} - {U}niversit{\'e} de {N}ice {S}ophia-{A}ntipolis - {CNRS} : {UMR}6070},

 pages = {22},

 type = {Research Report},

 institution = {INRIA},

 number = {{RR}-7618},

 month = {05},

 year = {2011},

 PDF = {http://hal.inria.fr/inria-00593426/PDF/RR-7618.pdf},

 x-pays={BR},

 
}

J. G. Chang, F. Havet, M. Montassier, and A. Raspaud. Steinberg's Conjecture and near-colorings. Rapport de recherche RR-7669, INRIA, 7 2011. [WWW ] [PDF ]

Abstract:

Let ${\cal F}$ be the family of planar graphs without cycles of length 4 and 5. Steinberg's Conjecture (1976) that says every graph of ${\cal F}$ is 3-colorable remains widely open. Motiv\'ees par une relaxation propos\'ee par Erd\H{o}s (1991), plusieurs \'etudes ont montr\'e la conjecture pour des sous-classes de ${\cal F}$. Par exemple, Borodin {\it et al.}~ont prouv\'e que tout graphe planaire sans cycles de longueur 4 \`a 7 est 3-colorable. Dans ce rapport, nous relaxons le probl\`eme non pas sur la classe de graphes mais sur le type de coloration en consid\'erant des {\em quasi-colorations}. Un graphe $G=(V,E)$ est dit $(i,j,k)$-colorable si son ensemble de sommet peut \^etre partitionner en trois ensembles $V_1,V_2,V_3$ tels que les graphes $G[V_1],G[V_2],G[V_3]$ induits par ces ensembles soit de degr\'e maximum au plus $i,j,k$ respectivement. Avec cette terminologie, la Conjecture de Steinberg dit que tout graphe de ${\cal F}$ est $(0,0,0)$-colorable. Un r\'esultat de Xu (2008) implique que tout graphe de ${\cal F}$ est $(1,1,1)$-colorable. Nous montrons ici que tout graphe de ${\cal F}$ est $(2,1,0)$-colorable et $(4,0,0)$-colorable.

@techreport{CHM+11,

 url = {http://hal.inria.fr/inria-00605810/en/},

 title = {{Steinberg's Conjecture and near-colorings}},

 author = {J. G. Chang and F. Havet and M. Montassier and A. Raspaud},

 abstract = {Let ${\cal F}$ be the family of planar graphs without cycles of length
 4 and 5. Steinberg's Conjecture (1976) that says every graph of ${\cal
 F}$ is 3-colorable remains widely open. Motiv\'ees par une relaxation propos\'ee par Erd\H{o}s (1991), plusieurs
 \'etudes ont montr\'e la conjecture pour des sous-classes de ${\cal F}$. Par exemple, Borodin {\it et al.}~ont prouv\'e
 que tout graphe planaire sans cycles de longueur 4 \`a 7 est
 3-colorable. Dans ce rapport, nous relaxons le probl\`eme non pas sur la classe de graphes mais
 sur le type de coloration en consid\'erant des {\em quasi-colorations}.
 Un graphe $G=(V,E)$ est dit $(i,j,k)$-colorable
 si son ensemble de sommet peut \^etre partitionner en trois ensembles $V_1,V_2,V_3$
 tels que les graphes $G[V_1],G[V_2],G[V_3]$ induits par ces ensembles soit de degr\'e maximum au plus $i,j,k$
 respectivement. Avec cette terminologie, la Conjecture de Steinberg dit que
 tout graphe de ${\cal F}$ est $(0,0,0)$-colorable. Un r\'esultat de Xu (2008)
 implique que tout graphe de ${\cal F}$ est $(1,1,1)$-colorable. Nous montrons ici que tout graphe de ${\cal F}$ est $(2,1,0)$-colorable et
 $(4,0,0)$-colorable.},

 language = {Anglais},

 affiliation = {Department of Mathematics - National Taiwan University - Taida Insitute for Mathematical Science - National Taiwan University - National Taiwan University - National Center for Theoretical Science - National Center for Theoretical Science - MASCOTTE - INRIA Sophia Antipolis / Laboratoire I3S - INRIA - Universit{\'e} de Nice Sophia-Antipolis - CNRS : UMR6070 - Laboratoire Bordelais de Recherche en Informatique - LaBRI - CNRS : UMR5800 - Universit{\'e} Sciences et Technologies - Bordeaux I - Ecole Nationale Sup{\'e}rieure d'Electronique, Informatique et Radiocommunications de Bordeaux - Universit{\'e} Victor Segalen - Bordeaux II},

 type = {Rapport de recherche},

 institution = {INRIA},

 number = {RR-7669},

 collaboration = {NSC Taiwan, NSC99-2923-M-002-007-MY3 },

 year = {2011},

 month = {7},

 pdf = {http://hal.inria.fr/inria-00605810/PDF/RR-7669.pdf},

 x-pays={CN},

 x-editorial-board={yes},

 x-proceedings={yes},

 x-international-audience={yes},

 
}

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:

Prefetching is a basic mechanism to avoid to waste time when accessing data. However, a tradeoff must be established between the amount of network's resources wasted by the prefetching and the gain of time. For instance, in the Web, browsers may download documents in advance while an Internaut is surfing on the Web. Since the web surfer follows the hyperlinks in an unpredictable way, the choice of the web pages to be prefetched must be computed online. The question is then to determine the minimum amount of resources used by prefetching and that ensures that all documents accessed by the web surfer have previously been loaded in the cache. We model this problem as a game similar to Cops and Robber Games in graphs. A fugitive starts on a marked vertex of a (di)graph G. Turn by turn, an observer marks at most k >= 1 vertices and then the fugitive can move along one edge/arcs of G. The observer wins if he prevents the fugitive to reach an unmarked vertex. The fugitive wins otherwise, i.e., if she enters an unmarked vertex. The surveillance number of a graph is the least k >=1 allowing the observer to win whatever the fugitive does. We also consider the connected variant of this game, i.e., when a vertex can be marked only if it is adjacent to an already marked vertex. All our results hold for both variants, connected or not. We show that deciding whether the surveillance number of a chordal graph equals 2 is NP-hard. Deciding if the surveillance number of a DAG equals 4 is PSPACE-complete. Moreover, computing the surveillance number is NP-hard in split graphs. On the other hand, we provide polynomial time algorithms to compute surveillance number of trees and interval graphs. Moreover, in the case of trees, we establish a combinatorial characterization, related to isoperimetry, of the surveillance number.

@techreport{FGJ+11,

 url = {http://hal.inria.fr/inria-00625703/en/},

 title = {{To Satisfy Impatient Web surfers is Hard}},

 author = {Fomin, F. and Giroire, F. and Jean-Marie, A. and Mazauric, D. and Nisse, N.},

 abstract = {{Prefetching is a basic mechanism to avoid to waste time when accessing data. However, a tradeoff must be established between the amount of network's resources wasted by the prefetching and the gain of time. For instance, in the Web, browsers may download documents in advance while an Internaut is surfing on the Web. Since the web surfer follows the hyperlinks in an unpredictable way, the choice of the web pages to be prefetched must be computed online. The question is then to determine the minimum amount of resources used by prefetching and that ensures that all documents accessed by the web surfer have previously been loaded in the cache. We model this problem as a game similar to Cops and Robber Games in graphs. A fugitive starts on a marked vertex of a (di)graph G. Turn by turn, an observer marks at most k >= 1 vertices and then the fugitive can move along one edge/arcs of G. The observer wins if he prevents the fugitive to reach an unmarked vertex. The fugitive wins otherwise, i.e., if she 

enters an unmarked vertex. The surveillance number of a graph is the least k >=1 allowing the observer to win whatever the fugitive does. We also consider the connected variant of this game, i.e., when a vertex can be marked only if it is adjacent to an already marked vertex. All our results hold for both variants, connected or not. We show that deciding whether the surveillance number of a chordal graph equals 2 is NP-hard. Deciding if the surveillance number of a DAG equals 4 is PSPACE-complete. Moreover, computing the surveillance number is NP-hard in split graphs. On the other hand, we provide polynomial time algorithms to compute surveillance number of trees and interval graphs. Moreover, in the case of trees, we establish a combinatorial characterization, related to isoperimetry, of the surveillance number.}},

 pages = {20},

 sorte = {Rapports},

 institution = {INRIA},

 number = {RR-7740},

 year = {2011},

 month = Sep,

 pdf = {http://hal.inria.fr/inria-00625703/PDF/RR-7740.pdf},

 x-editorial-board={no},

 x-proceedings={no},

 x-international-audience={no},

 x-pays = {NO},

 
}

F. Giroire, S. K. Gupta, R. Modrzejewski, J. Monteiro, and S. Pérennes. Analysis of the Repair Time in Distributed Storage Systems. Research Report RR-7538, INRIA, 02 2011. [WWW ] [PDF ]
Keywords: P2P storage systems, data lifetime, queuing model, regenerating codes per- formance evaluation.

Abstract:

{D}istributed or peer-to-peer storage systems introduce redundancy to preserve the data in case of peer failures or departures. {T}o ensure long-term fault tolerance, the storage system must have a self-repair service that continuously reconstructs lost fragments of redundancy. {T}he speed of this reconstruction process is crucial for the data survival. {T}his speed is mainly determined by available bandwidth, a critical resource of such systems. {W}e propose a new analytical framework that takes into account the correlation of concurrent repairs when estimating the repair time and the probability of data loss. {M}ainly, we intro- duce queuing models in which reconstructions are served by peers at a rate that depends on the available bandwidth. {T}he models and schemes proposed are validated by mathematical analysis, extensive set of simulations, and experimentation using the {G}rid'5000 test-bed platform.

@techreport{GGM+11,

 url = {http://hal.inria.fr/inria-00565359/en/},

 title = { {A}nalysis of the {R}epair {T}ime in {D}istributed {S}torage {S}ystems},

 author = {Giroire, F. and Gupta, S. K. and Modrzejewski, R. and Monteiro, J. and P{\'e}rennes, S.},

 abstract = {{D}istributed or peer-to-peer storage systems introduce redundancy to preserve the data in case of peer failures or departures. {T}o ensure long-term fault tolerance, the storage system must have a self-repair service that continuously reconstructs lost fragments of redundancy. {T}he speed of this reconstruction process is crucial for the data survival. {T}his speed is mainly determined by available bandwidth, a critical resource of such systems. {W}e propose a new analytical framework that takes into account the correlation of concurrent repairs when estimating the repair time and the probability of data loss. {M}ainly, we intro- duce queuing models in which reconstructions are served by peers at a rate that depends on the available bandwidth. {T}he models and schemes proposed are validated by mathematical analysis, extensive set of simulations, and experimentation using the {G}rid'5000 test-bed platform.},

 keywords = {{P}2{P} storage systems, data lifetime, queuing model, regenerating codes per- formance evaluation},

 language = {{A}nglais},

 affiliation = {{MASCOTTE} - {INRIA} {S}ophia {A}ntipolis / {L}aboratoire {I}3{S} - {INRIA} - {U}niversit{\'e} de {N}ice {S}ophia-{A}ntipolis - {CNRS} : {UMR}6070 - {I}ndian {I}nstitute of {T}echnology [{D}elhi] - {IIT} {D}elhi - {I}ndian {I}nstitute of {T}echnology {D}elhi },

 pages = {28},

 type = {Research Report},

 institution = {INRIA},

 number = {{RR}-7538},

 month = {02},

 year = {2011},

 pdf = {http://hal.inria.fr/inria-00565359/PDF/RR-7538.pdf},

 x-editorial-board={no},

 x-proceedings={no},

 x-international-audience={yes},

 x-pays = {BR},

 
}

F. Havet and X. Zhu. The game Grundy number of graphs. Rapport de recherche RR-7646, INRIA, June 2011. [WWW ] [PDF ]
Keywords: colouring game, game Grundy number, trees, partial 2-trees.

Abstract:

Given a graph G = (V;E), two players, Alice and Bob, alternate their turns in choosing uncoloured vertices to be coloured. Whenever an uncoloured vertex is chosen, it is coloured by the least positive integer not used by any of its coloured neighbours. Alice's goal is to minimize the total number of colours used in the game, and Bob's goal is to maximize it. The game Grundy number of G is the number of colours used in the game when both players use optimal strategies. It is proved in this paper that the maximum game Grundy number of forests is 3, and the game Grundy number of any partial 2-tree is at most 7.

@techreport{HaZh11,

 url = {http://hal.inria.fr/inria-00600738/en/},

 title = {{The game Grundy number of graphs}},

 author = {F. Havet and X. Zhu},

 abstract = {{Given a graph G = (V;E), two players, Alice and Bob, alternate their turns in choosing uncoloured vertices to be coloured. Whenever an uncoloured vertex is chosen, it is coloured by the least positive integer not used by any of its coloured neighbours. Alice's goal is to minimize the total number of colours used in the game, and Bob's goal is to maximize it. The game Grundy number of G is the number of colours used in the game when both players use optimal strategies. It is proved in this paper that the maximum game Grundy number of forests is 3, and the game Grundy number of any partial 2-tree is at most 7.}},

 keywords = {colouring game, game Grundy number, trees, partial 2-trees},

 language = {Anglais},

 affiliation = {MASCOTTE - INRIA Sophia Antipolis / Laboratoire I3S - INRIA - Universit\'e de Nice Sophia-Antipolis - CNRS : UMR6070 - Department of Mathematics - Zhejiang Normal University},

 type = {Rapport de recherche},

 institution = {INRIA},

 number = {RR-7646},

 year = {2011},

 month = Jun,

 pdf = {http://hal.inria.fr/inria-00600738/PDF/RR-7646.pdf},

 x-editorial-board={no},

 x-proceedings={no},

 x-international-audience={yes},

 x-pays={CN},

 
}

F. Maffray and G. Morel. On 3-colorable $P_5$-free graphs. Technical report 191, Les Cahiers Leibniz, Laboratoire G-SCOP, 2011. [PDF ]

@techreport{MaMo11a,

 title = {{On 3-colorable $P_5$-free graphs}},

 author={Maffray, F. and Morel, G.},

 number = {191},

 institution={Les Cahiers Leibniz, Laboratoire G-SCOP},

 year={2011},

 pdf={https://consult-cahiersleibniz.g-scop.grenoble-inp.fr/WebObjects/ProjetCahiersLeibniz.woa/Contents/WebServerResources/CahiersLeibniz/cahiers/Cahier191.pdf},

 x-editorial-board = {no},

 x-proceedings = {no},

 x-international-audience = {yes},

 sorte = "Rapports"
 
}

J. Moulierac, T. K. Phan, N. Thoai, and C. Tran. Xcast6 Treemap Islands - A Mixed Model of Application and Network Layer Multicast. Rapport de recherche RR-7784, INRIA, December 2011. [WWW ] [PDF ]
Keywords: IP multicast, Application Layer Multicast, Xcast, media streaming, linear program, algorithms.

Abstract:

IP multicast is a protocol that deals with group communications with the aim of reducing traffic redundancy in the network. However, due to difficulty in deployment and poor scalability with a large number of multicast groups, IP multicast is still not widely deployed and used on the Internet. Recently, Xcast6 and Xcast6 Treemap, the two network layer multicast protocols, have been proposed with complementary scaling properties to IP multicast: they support a very large number of active multicast sessions. However, the key limitation of these protocols is that they only support small multicast group. In this paper, we propose Xcast6 Treemap island - a hybrid model of Application Layer Multicast (ALM) and Xcast6 that can work for large multicast group. Our model has several key advantages: ease of deployment, efficiency in bandwidth savings, no control message between end-host and router, zero multicast forwarding state at router and no need for a multicast address allocation protocol. In addition, this model is a potential service from which an ISP can get new revenue. Finally, in simulation section, we have made a comparison with IP multicast and NICE protocol to show the feasibility of our new model.

@techreport{Mou11,

 hal_id = {inria-00637656},

 url = {http://hal.inria.fr/inria-00637656/en/},

 title = {{Xcast6 Treemap Islands - A Mixed Model of Application and Network Layer Multicast}},

 author = {J. Moulierac and T. K. Phan and N. Thoai and C. Tran},

 abstract = {{IP multicast is a protocol that deals with group communications with the aim of reducing traffic redundancy in the network. However, due to difficulty in deployment and poor scalability with a large number of multicast groups, IP multicast is still not widely deployed and used on the Internet. Recently, Xcast6 and Xcast6 Treemap, the two network layer multicast protocols, have been proposed with complementary scaling properties to IP multicast: they support a very large number of active multicast sessions. However, the key limitation of these protocols is that they only support small multicast group. In this paper, we propose Xcast6 Treemap island - a hybrid model of Application Layer Multicast (ALM) and Xcast6 that can work for large multicast group. Our model has several key advantages: ease of deployment, efficiency in bandwidth savings, no control message between end-host and router, zero multicast forwarding state at router and no need for a multicast address allocation protocol. In 
 addition, this model is a potential service from which an ISP can get new revenue. Finally, in simulation section, we have made a comparison with IP multicast and NICE protocol to show the feasibility of our new model.}},

 keywords = {IP multicast, Application Layer Multicast, Xcast, media streaming, linear program, algorithms},

 language = {Anglais},

 affiliation = {MASCOTTE - INRIA Sophia Antipolis / Laboratoire I3S - INRIA - Universit{\'e} de Nice Sophia-Antipolis - CNRS : UMR6070 - Faculty of Mechanical Engineering [HCM University] - FME - Ho CHi Minh City University of Technology},

 pages = {27},

 type = {Rapport de recherche},

 institution = {INRIA},

 number = {RR-7784},

 year = {2011},

 month = Dec,

 x-pays = {VN},

 x-editorial-board={no},

 x-proceedings={no},

 x-international-audience={yes},

 sorte = "Rapports",

 pdf = {http://hal.inria.fr/inria-00637656/PDF/RR-7784.pdf},

 
}

BACK TO MASCOTTE PUBLICATION INDEX

Last modified: Thu Oct 10 14:10:00 2013

This document was translated from BibT_EX by bibtex2html