|
MASCOTTE no longer exists => visit the new project-team
Publications of year 2010
BACK TO MASCOTTE PUBLICATION INDEX
Publications of year 2010
-
D. Coudert and D. Simplot-Ryl, editors.
Ad Hoc & Sensor Wireless Networks, an International Journal -- Special issue on Ad hoc, Mobile and Wireless Networks,
volume 9.
Old City Publishing,
2010.
[WWW
]
@book{CoSi10,
editor = {Coudert, D. and Simplot-Ryl, D.},
title = {Ad Hoc \& Sensor Wireless Networks, an International Journal -- Special issue on Ad hoc, Mobile and Wireless Networks},
publisher = {Old City Publishing},
year = {2010},
volume = {9},
number = {1-2},
issn = {1551-9899},
url = {http://www.oldcitypublishing.com/AHSWN/AHSWN.php},
OPTx-editorial-board={yes},
OPTx-proceedings={no},
OPTx-international-audience={yes},
sorte = "livres-edit",
}
-
O. Dalle and G. Wainer, editors.
SIMULATION: Transactions of the Society of Modeling and Simulation International. Special Issue on Software Tools, Techniques and Architectures for Computer Simulation,
volume 86.
Sage,
2010.
@book{DaWa10,
title = {SIMULATION: Transactions of the Society of Modeling and Simulation International. Special Issue on Software Tools, Techniques and Architectures for Computer Simulation},
publisher = {Sage},
year = {2010},
editor = {Dalle, O. and Wainer, G.},
doi = {10.1177/0037549710369877},
volume = {86},
OPTx-editorial-board={yes},
OPTx-proceedings={no},
OPTx-international-audience={yes},
sorte = "livres-edit",
}
-
F. Giroire and D. Mazauric, editors.
11es Journées Doctorales en Informatique et Réseaux (JDIR 2010),
number 11,
Sophia Antipolis, France,
March 2010.
Mascotte, INRIA, I3S(CNRS / Univ. of Nice-Sophia).
[WWW
]
@proceedings{jdir10,
title = {11es Journ\'ees Doctorales en Informatique et R\'eseaux (JDIR 2010)},
year = {2010},
editor = {F. Giroire and D. Mazauric},
number = {11},
sorte = "livres-edit",
address = {Sophia Antipolis, France},
month = mar,
organization = {Mascotte, INRIA, I3S(CNRS / Univ. of Nice-Sophia)},
opturl = {http://www-sop.inria.fr/teams/mascotte/jdir2010/},
url = {http://hal.inria.fr/JDIR2010/},
}
-
D. Coudert.
Algorithmique et optimisation dans les réseaux de télécommunications.
Habilitation à Diriger des Recherches,
Université de Nice Sophia-Antipolis (UNS),
March 2010.
[WWW
] [PDF
]
@phdthesis{Cou10,
author = {D. Coudert},
title = {Algorithmique et optimisation dans les r\'eseaux de t\'el\'ecommunications},
type = {Habilitation \`a Diriger des Recherches},
school = {{Universit\'e de Nice Sophia-Antipolis (UNS)}},
year = {2010},
month = mar,
pdf = {http://www-sop.inria.fr/members/David.Coudert/hdr/HDR-Coudert.pdf},
url = {http://www-sop.inria.fr/members/David.Coudert/hdr/},
OPTx-editorial-board={yes},
OPTx-proceedings={no},
OPTx-international-audience={yes},
sorte = "HDR",
}
-
Julian Monteiro.
Modeling and Analysis of Reliable Peer-to-Peer Storage Systems.
PhD thesis,
Ecole doctorale STIC, Université de Nice-Sophia Antipolis,
November 2010.
[WWW
]
| Abstract: |
Large scale peer-to-peer systems are foreseen as a way to provide highly reliable data storage at low cost. To ensure high durability and high resilience over a long period of time the system must add redundancy to the original data. It is well-known that erasure coding is a space efficient solution to obtain a high degree of fault-tolerance by distributing encoded fragments into different peers of the network. Therefore, a repair mechanism needs to cope with the dynamic and unreliable behavior of peers by continuously reconstructing the missing redundancy. Consequently, the system depends on many parameters that need to be well tuned, such as the redundancy factor, the placement policies, and the frequency of data repair. These parameters impact the amount of resources, such as the bandwidth usage and the storage space overhead that are required to achieve a desired level of reliability, i.e., probability of losing data. This thesis aims at providing tools to analyze and predict the performance
of general large scale data storage systems. We use these tools to analyze the impact of different choices of system design on different performance metrics. For instance, the bandwidth consumption, the storage space overhead, and the probability of data loss should be as small as possible. Different techniques are studied and applied. First, we describe a simple Markov chain model that harnesses the dynamics of a storage system under the effects of peer failures and of data repair. Then we provide closed-form formulas that give good approximations of the model. These formulas allow us to understand the interactions between the system parameters. Indeed, a lazy repair mechanism is studied and we describe how to tune the system parameters to obtain an efficient utilization of bandwidth. We confirm by comparing to simulations that this model gives correct approximations of the system average behavior, but does not capture its variations over time. We then propose a new stochastic model based on a fluid approximation that indeed captures the deviations around the mean behavior. These variations are most of the time neglected by previous works, despite being very important to correctly allocate the system resources. We additionally study several other aspects of a distributed storage system: we propose queuing models to calculate the repair time distribution under limited bandwidth scenarios; we discuss the trade-offs of a Hybrid coding (mixing erasure codes and replication); and finally we study the impact of different ways to distribute data fragments among peers, i.e., placement strategies. |
@phdthesis{Mon10,
author = {Monteiro, Julian},
title = {Modeling and Analysis of Reliable Peer-to-Peer Storage Systems},
school = {Ecole doctorale {STIC}, Universit\'e de Nice-Sophia Antipolis},
day = {16},
month = nov,
year = {2010},
url = {http://tel.archives-ouvertes.fr/tel-00545724/},
ftp = {http://tel.archives-ouvertes.fr/docs/00/54/57/24/PDF/these-jmonteiro.pdf},
abstract = {Large scale peer-to-peer systems are foreseen as a way to provide highly reliable data storage at low cost. To ensure high durability and high resilience over a long period of time the system must add redundancy to the original data. It is well-known that erasure coding is a space efficient solution to obtain a high degree of fault-tolerance by distributing encoded fragments into different peers of the network. Therefore, a repair mechanism needs to cope with the dynamic and unreliable behavior of peers by continuously reconstructing the missing redundancy. Consequently, the system depends on many parameters that need to be well tuned, such as the redundancy factor, the placement policies, and the frequency of data repair. These parameters impact the amount of resources, such as the bandwidth usage and the storage space overhead that are required to achieve a desired level of reliability, i.e., probability of losing data. This thesis aims at providing tools to analyze and predict the performance
of general large scale data storage systems. We use these tools to analyze the impact of different choices of system design on different performance metrics. For instance, the bandwidth consumption, the storage space overhead, and the probability of data loss should be as small as possible. Different techniques are studied and applied. First, we describe a simple Markov chain model that harnesses the dynamics of a storage system under the effects of peer failures and of data repair. Then we provide closed-form formulas that give good approximations of the model. These formulas allow us to understand the interactions between the system parameters. Indeed, a lazy repair mechanism is studied and we describe how to tune the system parameters to obtain an efficient utilization of bandwidth. We confirm by comparing to simulations that this model gives correct approximations of the system average behavior, but does not capture its variations over time. We then propose a new stochastic model based on a fluid approximation that indeed captures the deviations around the mean behavior. These variations are most of the time neglected by previous works, despite being very important to correctly allocate the system resources. We additionally study several other aspects of a distributed storage system: we propose queuing models to calculate the repair time distribution under limited bandwidth scenarios; we discuss the trade-offs of a Hybrid coding (mixing erasure codes and replication); and finally we study the impact of different ways to distribute data fragments among peers, i.e., placement strategies.},
x-pays = {FR},
OPTx-editorial-board={no},
OPTx-proceedings={no},
OPTx-international-audience={yes},
sorte = "these"
}
-
N. Nepomuceno.
Network optimization for wireless microwave backhaul.
PhD thesis,
Ecole doctorale STIC, Université de Nice-Sophia Antipolis,
December 2010.
[WWW
] [PDF
]
Keywords:
Wireless communications,
Mathematical programming,
Network optimization,
Multicommodity flows,
Microwave backhaul networks.
| Abstract: |
Technological breakthroughs have transformed the telecommunications industry aiming at providing capacity and efficiency to support the increasing demand for wireless broadband services. With the advances in access technologies, the capacity bottleneck of cellular networks is gradually moving from the radio interface towards the backhaul -- the portion of the network infrastructure that provides interconnectivity between the access and core networks. The ability for microwave to be rapidly and cost-effectively deployed is being a crucial point for successfully tackling the backhaul bottleneck problem. However, backhaul solutions available with this technology have received little attention from the scientific community. Nevertheless, the growth of microwave backhaul networks and their increasing complexity give rise to many interesting optimization problems. In fact, unlike wired networks, the capacity of a microwave radio link is prone to variations, either due to external factors (e.g., weather) or by the action of the network operator. This fundamental difference raises a variety of new issues to be addressed appropriately. Therefore, more refined approaches for dealing with network optimization in wireless microwave backhaul need to be conceived. In this thesis, we investigate network optimization problems related to the design and configuration of wireless microwave backhaul. We are concerned with a general class of problems expressed in terms of minimum cost multicommodity flows with discontinuous step increasing cost functions on the links of the network. These problems are among the most important and challenging problems in network optimization. Generally, they are computationally very difficult and, in practice, can only be solved approximately. We introduce mathematical models for some of these problems and present solution approaches essentially based on general mixed integer programming, chance-constrained programming, relaxation techniques, cutting plane methods, as well as hybrid metaheuristics. This work was done in collaboration with the SME~3Roam, and partially developed within the scope of the joint project RAISOM (R\'eseaux de collecte IP sans fil optimis\'es), among INRIA Sophia |
@phdthesis{Nepo10,
author = {N. Nepomuceno},
title = {Network optimization for wireless microwave backhaul},
school = {Ecole doctorale {STIC}, Universit\'e de Nice-Sophia Antipolis},
year = {2010},
month = {dec},
url = {http://tel.archives-ouvertes.fr/tel-00593412/fr/},
pdf = {http://tel.archives-ouvertes.fr/docs/00/59/34/12/PDF/thesis.pdf},
keywords = {Wireless communications, Mathematical programming, Network optimization, Multicommodity flows, Microwave backhaul networks},
abstract = {Technological breakthroughs have transformed the telecommunications industry aiming at providing capacity and efficiency to support the increasing demand for wireless broadband services. With the advances in access technologies, the capacity bottleneck of cellular networks is gradually moving from the radio interface towards the backhaul -- the portion of the network infrastructure that provides interconnectivity between the access and core networks. The ability for microwave to be rapidly and cost-effectively deployed is being a crucial point for successfully tackling the backhaul bottleneck problem. However, backhaul solutions available with this technology have received little attention from the scientific community. Nevertheless, the growth of microwave backhaul networks and their increasing complexity give rise to many interesting optimization problems. In fact, unlike wired networks, the capacity of a microwave radio link is prone to variations, either due to external factors (e.g., weather) or by the action of the network operator. This fundamental difference raises a variety of new issues to be addressed appropriately. Therefore, more refined approaches for dealing with network optimization in wireless microwave backhaul need to be conceived. In this thesis, we investigate network optimization problems related to the design and configuration of wireless microwave backhaul. We are concerned with a general class of problems expressed in terms of minimum cost multicommodity flows with discontinuous step increasing cost functions on the links of the network. These problems are among the most important and challenging problems in network optimization. Generally, they are computationally very difficult and, in practice, can only be solved approximately. We introduce mathematical models for some of these problems and present solution approaches essentially based on general mixed integer programming, chance-constrained programming, relaxation techniques, cutting plane methods, as well as hybrid metaheuristics. This work was done in collaboration with the SME~3Roam, and partially developed within the scope of the joint project RAISOM (R\'eseaux de collecte IP sans fil optimis\'es), among INRIA Sophia},
sorte = {thesis},
OPTx-pays = {FR, BR},
OPTx-editorial-board={no},
OPTx-proceedings={no},
OPTx-international-audience={yes}
}
-
S. Pérennes.
Contribution à l'algorithmique des réseaux de télécommunications.
Habilitation à Diriger des Recherches,
Université de Nice Sophia-Antipolis (UNS),
March 2010.
[WWW
]
@phdthesis{Per10,
author = {S. P\'erennes},
title = {Contribution \`a l'algorithmique des r\'eseaux de t\'el\'ecommunications },
type = {Habilitation \`a Diriger des Recherches},
school = {{Universit\'e de Nice Sophia-Antipolis (UNS)}},
year = {2010},
month = mar,
url = {http://www-sop.inria.fr/members/Stephane.Perennes/ },
sorte = "HDR",
}
-
A. Casamayou,
N. Cohen,
G. Connan,
T. Dumont,
L. Fousse,
F. Maltey,
M. Meulien,
M. Mezzarobba,
C. Pernet,
N.M. Thiéry,
and P. Zimmermann.
Calcul mathématique avec Sage,
chapter Théorie des graphes.
2010.
[WWW
]
@inbook{CCC+10a,
author = {A. Casamayou and N. Cohen and G. Connan and T. Dumont and L. Fousse and F. Maltey and M. Meulien and M. Mezzarobba and C. Pernet and N.M. Thi\'ery and P. Zimmermann},
title = {Calcul math\'ematique avec Sage},
chapter = {Th\'eorie des graphes},
year = {2010},
sorte = "livres-chap",
url = {http://sagebook.gforge.inria.fr/},
OPTx-editorial-board={no},
OPTx-proceedings={no},
OPTx-international-audience={yes},
sorte = "livres-chap",
}
-
A. Casamayou,
N. Cohen,
G. Connan,
T. Dumont,
L. Fousse,
F. Maltey,
M. Meulien,
M. Mezzarobba,
C. Pernet,
N. M. Thiéry,
and P. Zimmermann.
Calcul mathématique avec Sage,
chapter Programmation Linéaire.
2010.
[WWW
]
@inbook{CCC+10b,
author = {A. Casamayou and N. Cohen and G. Connan and T. Dumont and L. Fousse and F. Maltey and M. Meulien and M. Mezzarobba and C. Pernet and N. M. Thi\'ery and P. Zimmermann},
title = {Calcul math\'ematique avec Sage},
chapter = {Programmation Lin\'eaire},
year = {2010},
sorte = "livres-chap",
url = {http://sagebook.gforge.inria.fr/},
OPTx-editorial-board={no},
OPTx-proceedings={no},
OPTx-international-audience={yes},
sorte = "Rapports",
}
-
T. Cinkler,
D. Coudert,
M. Flammini,
G. Monaco,
L. Moscardelli,
X. Muñoz,
I. Sau,
M. Shalom,
and S. Zaks.
Graphs and Algorithms in Communication Networks: Studies in Broadband, Optical, Wireless, and Ad Hoc Networks,
volume XXVII of EATCS Texts in Theoretical Computer Science,
chapter Traffic Grooming: Combinatorial Results and Practical Resolutions,
pages 63-94.
Springer,
A. Koster and X. Muñoz edition,
2010.
[WWW
] [PDF
]
| Abstract: |
In an optical network using the wavelength division multiplexing (WDM) technology, routing a request consists in assigning it a route in the physical network and a wavelength. If each request uses $1/g$ of the bandwidth of the wavelength, we will say that the grooming factor is $g$. That means that on a given edge of the network we can groom (group) at most $g$ requests on the same wavelength. With this constraint the objective can be either to minimize the number of wavelengths (related to the transmission cost) or minimize the number of Add Drop Multiplexers\index{add drop multiplexer} (shortly ADM) used in the network (related to the cost of the nodes).
Here, we first survey the main theoretical results obtained for different grooming factors on various topologies: complexity, (in)approximability, optimal constructions, approximation algorithms, heuristics, etc. Then, we give an ILP formulation for multilayer traffic grooming and present some experimental results. |
@InBook{CCF+09,
AUTHOR = {Cinkler, T. and Coudert, D. and Flammini, M. and Monaco, G. and Moscardelli, L. and Mu{\~n}oz, X. and Sau, I. and Shalom, M. and Zaks, S.},
ALTeditor = {},
title = {Graphs and Algorithms in Communication Networks: Studies in Broadband, Optical, Wireless, and Ad Hoc Networks},
chapter = {Traffic Grooming: Combinatorial Results and Practical Resolutions},
publisher = {Springer},
year = {2010},
x-pays = {HU,IL,ES,IS},
OPTkey = {},
volume = {XXVII},
OPTnumber = {},
edition = {{A. Koster and X. Mu{\~n}oz}},
X-INTERNATIONAL-AUDIENCE = {yes},
URL-HAL = {http://hal.inria.fr/inria-00530964},
X-ID-HAL = {inria-00530964},
pages = {63-94},
series = {EATCS Texts in Theoretical Computer Science},
ISBN = {978-3-642-02249-4},
url = {http://www.springer.com/computer/foundations/book/978-3-642-02249-4},
abstract = {In an optical network using the wavelength division multiplexing (WDM) technology, routing a request consists in assigning it a route in the physical network and a wavelength. If each request uses $1/g$ of the bandwidth of the wavelength, we will say that the grooming factor is $g$. That means that on a given edge of the network we can groom (group) at most $g$ requests on the same wavelength. With this constraint the objective can be either to minimize the number of wavelengths (related to the transmission cost) or minimize the number of Add Drop Multiplexers\index{add drop multiplexer} (shortly ADM) used in the network (related to the cost of the nodes).
Here, we first survey the main theoretical results obtained for different grooming factors on various topologies: complexity, (in)approximability, optimal constructions, approximation algorithms, heuristics, etc. Then, we give an ILP formulation for multilayer traffic grooming and present some experimental results.},
pdf = {ftp://ftp-sop.inria.fr/mascotte/personnel/David.Coudert/Publication/CCF+09.pdf},
sorte = "livres-chap",
}
-
L. Addario-Berry,
W.S. Kennedy,
A.D. King,
Z. Li,
and B. Reed.
Finding the maximum-weight induced $k$-partite subgraph of an $i$-triangulated graph.
Discrete Applied Mathematics,
158(7):765-770,
April 2010.
[WWW
]
| Abstract: |
An i-triangulated graph is a graph in which every odd cycle has two non-crossing chords; i-triangulated graphs form a subfamily of perfect graphs. A slightly more general family of perfect graphs are clique-separable graphs. A graph is clique-separable precisely if every induced subgraph either has a clique cutset, or is a complete multipartite graph or a clique joined to an arbitrary bipartite graph. We exhibit a polynomial time algorithm for finding a maximum-weight induced k-partite subgraph of an i-triangulated graph, and show that the problem of finding a maximum-size bipartite induced subgraph in a clique-separable graph is View the MathML source-complete. |
@article{AK+09,
author = {L. {Addario-Berry} and W.S. Kennedy and A.D. King and Z. Li and B. Reed},
title = {Finding the maximum-weight induced $k$-partite subgraph of an $i$-triangulated graph},
journal = {Discrete Applied Mathematics},
volume = {158},
number = {7},
pages = {765-770},
year = {2010},
month = apr,
url = {http://dx.doi.org/10.1016/j.dam.2008.08.020},
abstract = {An i-triangulated graph is a graph in which every odd cycle has two non-crossing chords; i-triangulated graphs form a subfamily of perfect graphs. A slightly more general family of perfect graphs are clique-separable graphs. A graph is clique-separable precisely if every induced subgraph either has a clique cutset, or is a complete multipartite graph or a clique joined to an arbitrary bipartite graph. We exhibit a polynomial time algorithm for finding a maximum-weight induced k-partite subgraph of an i-triangulated graph, and show that the problem of finding a maximum-size bipartite induced subgraph in a clique-separable graph is View the MathML source-complete.},
sorte = "rev-int",
}
-
O. Amini,
F. Giroire,
F. Huc,
and S. Pérennes.
Minimal selectors and fault tolerant networks.
Networks,
55(4):326-340,
July 2010.
[WWW
] [PDF
]
| Abstract: |
In this paper we study a combinatorial optimization problem issued from on-board networks in satellites. In this kind of networks the entering signals (inputs) should be routed to amplifiers (outputs). The connections are made via expensive switches with four links available. The paths connecting inputs to outputs should be link-disjoint. More formally, we call {it $\plk-$network } an undirected graph with $p+\lambda$ inputs, $p+k$ outputs and internal vertices of degree four. A $\plk-$network is \emph{valid} if it is tolerant to a restricted number of faults in the network, i.e. if for any choice of at most $k$ faulty inputs and $\lambda$ faulty outputs, there exist $p$ edge-disjoint paths from the remaining inputs to the remaining outputs. In the special case $\lambda=0$, a $\plk-$network is already known as a \emph{selector}. Our optimization problem consists of determining $N\plk$, the minimum number of nodes in a valid $\plk-$network. For this, we present validity certificates and a gluing
lemma from which derive lower bounds for $N\plk$. We also provide constructions, and hence upper bounds, based on expanders. The problem is very sensitive to the order of $\lambda$ and $k$. For instance, when $\lambda$ and $k$ are small compared to $p$, the question reduces to avoid certain forbidden local configurations. For larger values of $\lambda$ and $k$, the problem is to find graphs with a good expansion property for small sets. This leads us to introduce a new parameter called \emph{$\alpha$-robustness}. We use $\alpha$-robustness to generalize our constructions to higher order values of $k$ and $\lambda$. In many cases, we provide asymptotically tight bounds for $N\plk$. |
@article{AGHP10,
author = {O. Amini and F. Giroire and F. Huc and S. P\'erennes },
title = { Minimal selectors and fault tolerant networks },
journal = { Networks },
year = {2010},
volume = {55},
number = {4},
pages = {326-340},
month = jul,
OPTnote = {To appear. Published online 31 July 2009, DOI 10.1002/net.20326},
url = {http://doi.wiley.com/10.1002/net.20326},
pdf = { ftp://ftp-sop.inria.fr/mascotte/Publications/AG+07.pdf },
abstract = { In this paper we study a combinatorial optimization problem issued from on-board networks in satellites. In this kind of networks the entering signals (inputs) should be routed to amplifiers (outputs). The connections are made via expensive switches with four links available. The paths connecting inputs to outputs should be link-disjoint. More formally, we call {it $\plk-$network } an undirected graph with $p+\lambda$ inputs, $p+k$ outputs and internal vertices of degree four. A $\plk-$network is \emph{valid} if it is tolerant to a restricted number of faults in the network, i.e. if for any choice of at most $k$ faulty inputs and $\lambda$ faulty outputs, there exist $p$ edge-disjoint paths from the remaining inputs to the remaining outputs. In the special case $\lambda=0$, a $\plk-$network is already known as a \emph{selector}. Our optimization problem consists of determining $N\plk$, the minimum number of nodes in a valid $\plk-$network. For this, we present validity certificates and a gluing
lemma from which derive lower bounds for $N\plk$. We also provide constructions, and hence upper bounds, based on expanders. The problem is very sensitive to the order of $\lambda$ and $k$. For instance, when $\lambda$ and $k$ are small compared to $p$, the question reduces to avoid certain forbidden local configurations. For larger values of $\lambda$ and $k$, the problem is to find graphs with a good expansion property for small sets. This leads us to introduce a new parameter called \emph{$\alpha$-robustness}. We use $\alpha$-robustness to generalize our constructions to higher order values of $k$ and $\lambda$. In many cases, we provide asymptotically tight bounds for $N\plk$. },
OPTx-editorial-board={yes},
OPTx-proceedings={no},
OPTx-international-audience={yes},
sorte = "rev-int",
}
-
O. Amini,
F. Havet,
F. Huc,
and S. Thomassé.
WDM and directed star arboricity.
Combinatorics, Probability and Computing,
19:161--182,
2010.
[PDF
]
| Abstract: |
A digraph is $m$-labelled if every arc is labelled by an integer in $\{1, \dots ,m\}$. Motivated by wavelength assignment for multicasts in optical networks, we introduce and study $n$-fibre colourings of labelled digraphs. These are colourings of the arcs of $D$ such that at each vertex $v$, and for each colour $\alpha$, $in(v,\alpha)+out(v,\alpha)\leq n$ with $in(v,\alpha)$ the number of arcs coloured $\alpha$ entering $v$ and $out(v,\alpha)$ the number of labels $l$ such that there is at least one arc of label $l$ leaving $v$ and coloured with $\alpha$. The problem is to find the minimum number of colours $\lambda_n(D)$ such that the $m$-labelled digraph $D$ has an $n$-fibre colouring. In the particular case when $D$ is $1$-labelled, $\lambda_1(D)$ is called the directed star arboricity of $D$, and is denoted by $dst(D)$. We first show that $dst(D)\leq 2\Delta^-(D)+1$, and conjecture that if $\Delta^-(D)\geq 2$, then $dst(D)\leq 2\Delta^-(D)$. We also prove that for a subcubic digraph $D$, then $dst(D)\leq 3$, and that if $\Delta^+(D), \Delta^-(D)\leq 2$, then $dst(D)\leq 4$. Finally, we study $\lambda_n(m,k)=\max\{\lambda_n(D) \tq D \mbox{ is $m$-labelled} \et \Delta^-(D)\leq k\}$. We show that if $m\geq n$, then $\ds \left\lceil\frac{m}{n}\left\lceil \frac{k}{n}\right\rceil + \frac{k}{n} \right\rceil\leq \lambda_n(m,k) \leq\left\lceil\frac{m}{n}\left\lceil \frac{k}{n}\right\rceil + \frac{k}{n} \right\rceil + C \frac{m2\log k}{n}$ for some constant $C$. We conjecture that the lower bound should be the right value of $\lambda_n(m,k)$. |
@article{AHH+10,
author={O. Amini and F. Havet and F. Huc and S. Thomass\'e},
title={WDM and directed star arboricity},
journal = {Combinatorics, Probability and Computing},
volume = {19},
year = {2010},
pages = {161--182},
abstract = { A digraph is $m$-labelled if every arc is labelled by an integer in $\{1, \dots ,m\}$. Motivated by wavelength assignment for multicasts in optical networks, we introduce and study $n$-fibre colourings of labelled digraphs. These are colourings of the arcs of $D$ such that at each vertex $v$, and for each colour $\alpha$, $in(v,\alpha)+out(v,\alpha)\leq n$ with $in(v,\alpha)$ the number of arcs coloured $\alpha$ entering $v$ and $out(v,\alpha)$ the number of labels $l$ such that there is at least one arc of label $l$ leaving $v$ and coloured with $\alpha$. The problem is to find the minimum number of colours $\lambda_n(D)$ such that the $m$-labelled digraph $D$ has an $n$-fibre colouring. In the particular case when $D$ is $1$-labelled, $\lambda_1(D)$ is called the directed star arboricity of $D$, and is denoted by $dst(D)$. We first show that $dst(D)\leq 2\Delta^-(D)+1$, and conjecture that if $\Delta^-(D)\geq 2$, then $dst(D)\leq 2\Delta^-(D)$. We also prove that for a subcubic digraph $D$, then $dst(D)\leq 3$, and that if $\Delta^+(D), \Delta^-(D)\leq 2$, then $dst(D)\leq 4$. Finally, we study $\lambda_n(m,k)=\max\{\lambda_n(D) \tq D \mbox{ is $m$-labelled} \et \Delta^-(D)\leq k\}$. We show that if $m\geq n$, then $\ds \left\lceil\frac{m}{n}\left\lceil \frac{k}{n}\right\rceil + \frac{k}{n} \right\rceil\leq \lambda_n(m,k) \leq\left\lceil\frac{m}{n}\left\lceil \frac{k}{n}\right\rceil + \frac{k}{n} \right\rceil + C \frac{m2\log k}{n}$ for some constant $C$. We conjecture that the lower bound should be the right value of $\lambda_n(m,k)$.},
pdf= { ftp://ftp-sop.inria.fr/mascotte/Publications/AHH+10.pdf},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
sorte = "rev-int",
}
-
M. Asté,
F. Havet,
and C. Linhares Sales.
Grundy number and products of graphs.
Discrete Mathematics,
310(9):1482--1490,
2010.
[PDF
]
| Abstract: |
The {\em Grundy number} of a graph $G$, denoted by $\Gamma (G)$, is the largest $k$ such that $G$ has a {\em greedy} $k$-colouring, that is a colouring with $k$ colours obtained by applying the greedy algorithm according to some ordering of the vertices of $G$. In this paper, we study the Grundy number of the lexicographic and the cartesian products of two graphs in terms of the Grundy numbers of these graphs.
Regarding the lexicographic product, we show that $\Gamma(G)\times \Gamma(H)\leq \Gamma(G[H])\leq 2^{\Gamma(G)-1}(\Gamma(H)-1)+\Gamma(G)$. In addition, we show that if $G$ is a tree or $\Gamma(G)=\Delta(G)+1$, then $\Gamma(G[H])=\Gamma(G)\times\Gamma(H)$. We then deduce that for every fixed $c\geq 1$, given a graph $G$, it is CoNP-Complete to decide if $\Gamma(G)\leq c\times \chi(G)$ and it is CoNP-Complete to decide if $\Gamma(G)\leq c\times \omega(G)$.
Regarding the cartesian product, we show that there is no upper bound of $\Gamma(G\square H)$ as a function of $\Gamma(G)$ and $\Gamma(H)$. Nevertheless, we prove that $\Gamma(G\square H) \leq \Delta(G)\cdot 2^{\Gamma(H)-1} + \Gamma(H)$. |
@article{AHL10,
author = {Ast\'e, M. and Havet, F. and Linhares Sales, C.},
title = {Grundy number and products of graphs},
journal = {Discrete Mathematics},
year = {2010},
volume = {310},
number = {9},
pages = {1482--1490},
abstract = {The {\em Grundy number} of a graph $G$, denoted by $\Gamma (G)$, is the largest $k$ such that $G$ has a {\em greedy} $k$-colouring, that is a colouring with $k$ colours obtained by applying the greedy algorithm according to some ordering of the vertices of $G$. In this paper, we study the Grundy number of the lexicographic and the cartesian products of two graphs in terms of the Grundy numbers of these graphs.
Regarding the lexicographic product, we show that $\Gamma(G)\times \Gamma(H)\leq \Gamma(G[H])\leq 2^{\Gamma(G)-1}(\Gamma(H)-1)+\Gamma(G)$. In addition, we show that if $G$ is a tree or $\Gamma(G)=\Delta(G)+1$, then $\Gamma(G[H])=\Gamma(G)\times\Gamma(H)$. We then deduce that for every fixed $c\geq 1$, given a graph $G$, it is CoNP-Complete to decide if $\Gamma(G)\leq c\times \chi(G)$ and it is CoNP-Complete to decide if $\Gamma(G)\leq c\times \omega(G)$.
Regarding the cartesian product, we show that there is no upper bound of $\Gamma(G\square H)$ as a function of $\Gamma(G)$ and $\Gamma(H)$. Nevertheless, we prove that $\Gamma(G\square H) \leq \Delta(G)\cdot 2^{\Gamma(H)-1} + \Gamma(H)$.},
pdf = {ftp://ftp-sop.inria.fr/mascotte/Publications/AHL10.pdf},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
x-pays = {BR},
sorte = "rev-int",
}
-
J-C. Bermond,
C. J. Colbourn,
L. Gionfriddo,
G. Quattrocchi,
and I. Sau.
Drop Cost and Wavelength Optimal Two-Period Grooming with Ratio 4.
SIAM Journal on Discrete Mathematics,
24(2):400-419,
2010.
[PDF
]
| Abstract: |
We study grooming for two-period optical networks, a variation of the traffic grooming problem for WDM ring networks introduced by Colbourn, Quattrocchi, and Syrotiuk. In the two-period grooming problem, during the first period of time there is all-to-all uniform traffic among $n$ nodes, each request using $1/C$ of the bandwidth; and during the second period, there is all-to-all uniform traffic only among a subset $V$ of $v$ nodes, each request now being allowed to use $1/C'$ of the bandwidth, where $C' < C$. We determine the minimum drop cost (minimum number of ADMs) for any $n,v$ and $C=4$ and $C' \in \{1,2,3\}$. To do this, we use tools of graph decompositions. Indeed the two-period grooming problem corresponds to minimizing the total number of vertices in a partition of the edges of the complete graph $K_n$ into subgraphs, where each subgraph has at most $C$ edges and where furthermore it contains at most $C'$ edges of the complete graph on $v$ specified vertices. Subject to the condition that the two-period grooming has the least drop cost, the minimum number of wavelengths required is also determined in each case. |
@article{BCG+10,
author = {J-C. Bermond and C. J. Colbourn and L. Gionfriddo and G. Quattrocchi and I. Sau},
title = {{Drop Cost and Wavelength Optimal Two-Period Grooming with Ratio 4}},
journal = {SIAM Journal on Discrete Mathematics},
year = {2010},
volume = {24},
number = {2},
pages = {400-419},
abstract = { We study grooming for two-period optical networks, a variation of the traffic grooming problem for WDM ring networks introduced by Colbourn, Quattrocchi, and Syrotiuk. In the two-period grooming problem, during the first period of time there is all-to-all uniform traffic among $n$ nodes, each request using $1/C$ of the bandwidth; and during the second period, there is all-to-all uniform traffic only among a subset $V$ of $v$ nodes, each request now being allowed to use $1/C'$ of the bandwidth, where $C' < C$. We determine the minimum drop cost (minimum number of ADMs) for any $n,v$ and $C=4$ and $C' \in \{1,2,3\}$. To do this, we use tools of graph decompositions. Indeed the two-period grooming problem corresponds to minimizing the total number of vertices in a partition of the edges of the complete graph $K_n$ into subgraphs, where each subgraph has at most $C$ edges and where furthermore it contains at most $C'$ edges of the complete graph on $v$ specified vertices. Subject to the condition that the two-period grooming has the least drop cost, the minimum number of wavelengths required is also determined in each case.},
pdf = {ftp://ftp-sop.inria.fr/mascotte/Publications/BCG+10.pdf},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
x-pays = {ES, IT, US},
sorte = "rev-int",
}
-
J-C. Bermond,
L. Gargano,
and A. A. Rescigno.
Gathering with minimum completion time in sensor tree networks.
JOIN,
11(1-2):1-33,
2010.
Note: A preliminary version has been presented at Sirocco08.
[PDF
]
| Abstract: |
Data gathering is a fundamental operation in wireless sensor networks in which data packets generated at sensor nodes are to be collected at a base station. In this paper we suppose that each sensor is equipped with an halfâduplex interface; hence, a node cannot receive and transmit at the same time. Moreover, each node is equipped with omnidirectional antennas allowing the transmission over distance R. The network is a multi-hop wireless network and the time is slotted so that oneâhop transmission of one data item consumes one time slot. We model the network with a graph where the vertices represent the nodes and two nodes are connected if they are in the transmission range of each other. We suppose that the interference range is the same as the transmission range; therefore due to interferences a collision happens at a node if two or more of its neighbors try to transmit at the same time. Furthermore we suppose that an intermediate node should forward a message as soon as it receives it. We give an optimal collision free gathering schedule for tree networks whenever each node has exactly one data packet to send. |
@article{BGR10,
citekey= {BGR10},
author = {Bermond, J-C. and Gargano, L. and Rescigno, A. A.},
title= {Gathering with minimum completion time in sensor tree networks },
journal = {JOIN},
volume= {11},
number= {1-2},
year= {2010},
pages={1-33},
pdf={ftp://ftp-sop.inria.fr/mascotte/personnel/Jean-Claude.Bermond//PUBLIS/BGR10.pdf},
note = {A preliminary version has been presented at Sirocco08},
abstract ={ Data gathering is a fundamental operation in wireless sensor networks in which data packets generated at sensor nodes are to be collected at a base station. In this paper we suppose that each sensor is equipped with an halfâduplex interface; hence, a node cannot receive and transmit at the same time. Moreover, each node is equipped with omnidirectional antennas allowing the transmission over distance R. The network is a multi-hop wireless network and the time is slotted so that oneâhop transmission of one data item consumes one time slot. We model the network with a graph where the vertices represent the nodes and two nodes are connected if they are in the transmission range of each other. We suppose that the interference range is the same as the transmission range; therefore due to interferences a collision happens at a node if two or more of its neighbors try to transmit at the same time. Furthermore we suppose that an intermediate node should forward a message as soon as it receives it. We give an optimal collision free gathering schedule for tree networks whenever each node has exactly one data packet to send. },
OPTx-editorial-board={yes},
OPTx-international-audience={yes},
x-pays = {IT},
sorte = "rev-int",
}
-
J-C. Bermond,
F. Havet,
F. Huc,
and C. Linhares Sales.
Improper colouring of weighted grid and hexagonal graphs.
Discrete Mathematics, Algorithms and Applications,
2(3):395-411,
2010.
[PDF
]
| Abstract: |
{W}e study a weighted improper colouring problem motivated by a frequency allocation problem. {I}t consists of associating to each vertex a set of $p(v)$ (weight) distinct colours (frequencies), such that the set of vertices having a given colour induces a graph of degree at most $k$ (the case $k=0$ corresponds to proper colouring). {T}he objective is to minimize the number of colours. We propose approximation algorithms to compute such a colouring for general graphs. {W}e apply these to obtain good approximation ratio for grid and hexagonal graphs. {F}urthermore we give exact results for the 2-dimensional grid and the triangular lattice when the weights are all the same. |
@article{BHHL10,
title = {{I}mproper colouring of weighted grid and hexagonal graphs},
author = {Bermond, J-C. and Havet, F. and Huc, F. and Linhares Sales, C.},
journal = {Discrete Mathematics, Algorithms and Applications},
year = {2010},
volume = {2},
number = {3},
pages = {395-411},
abstract = {{W}e study a weighted improper colouring problem motivated by a frequency allocation problem. {I}t consists of associating to each vertex a set of $p(v)$ (weight) distinct colours (frequencies), such that the set of vertices having a given colour induces a graph of degree at most $k$ (the case $k=0$ corresponds to proper colouring). {T}he objective is to minimize the number of colours. We propose approximation algorithms to compute such a colouring for general graphs. {W}e apply these to obtain good approximation ratio for grid and hexagonal graphs. {F}urthermore we give exact results for the 2-dimensional grid and the triangular lattice when the weights are all the same.},
pdf = {ftp://ftp-sop.inria.fr/mascotte/Publications/BHHL10.pdf},
x-editorial-board={yes},
x-proceedings={yes},
x-international-audience={yes},
x-pays={BR},
sorte = "rev-int",
}
-
J-C. Bermond and M-L. Yu.
Optimal gathering algorithms in multi-hop radio tree networks with interferences.
Ad Hoc and Sensor Wireless Networks,
9(1-2):109-128,
2010.
[PDF
]
| Abstract: |
We study the problem of gathering information from the nodes of a multi-hop radio network into a pre-defined destination node under the interference constraints. In such a network, a message can only be properly received if there is no interference from another message being simultaneously transmitted. The network is modeled as a graph, where the vertices represent the nodes and the edges, the possible com- munications. The interference constraint is modeled by a fixed integer dI ? 1, which implies that nodes within distance d I in the graph from one sender cannot receive messages from another node. In this paper, we suppose that it takes one unit of time (slot) to transmit a unit-length message. A step (or round) consists of a set of non interfering (compat- ible) calls and uses one slot. We present optimal algorithms that give minimum number of steps (delay) for the gathering problem with buffer- ing possibility, when the network is a tree, the root is the destination and dI = 1. In fact we study the equivalent personalized broadcasting problem instead. |
@article{BeYu10,
citekey= {BeYu10},
author= {J-C. Bermond and M-L. Yu},
title= {Optimal gathering algorithms in multi-hop radio tree networks with interferences},
journal = { Ad Hoc and Sensor Wireless Networks},
volume= {9},
number= {1-2},
year= {2010},
pages={109-128},
PDF={ftp://ftp-sop.inria.fr/mascotte/personnel/Jean-Claude.Bermond//PUBLIS/BeYu10.pdf},
abstract={We study the problem of gathering information from the nodes of a multi-hop radio network into a pre-defined destination node under the interference constraints. In such a network, a message can only be properly received if there is no interference from another message being simultaneously transmitted. The network is modeled as a graph, where the vertices represent the nodes and the edges, the possible com- munications. The interference constraint is modeled by a fixed integer dI ? 1, which implies that nodes within distance d I in the graph from one sender cannot receive messages from another node. In this paper, we suppose that it takes one unit of time (slot) to transmit a unit-length message. A step (or round) consists of a set of non interfering (compat- ible) calls and uses one slot. We present optimal algorithms that give minimum number of steps (delay) for the gathering problem with buffer- ing possibility, when the network is a tree, the root is the destination and dI = 1. In fact we study the equivalent personalized broadcasting problem instead. },
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
x-pays = {CA},
sorte = "rev-int",
}
-
I. Caragiannis,
A. Ferreira,
C. Kaklamanis,
S. Pérennes,
and H. Rivano.
Fractional Path Coloring in Bounded Degree Trees with Applications.
Algorithmica,
58(2):516-540,
2010.
[WWW
] [PDF
]
| Abstract: |
This paper studies the natural linear programming relaxation of the path coloring problem. We prove constructively that finding an optimal fractional path coloring is Fixed Parameter Tractable (FPT), with the degree of the tree as parameter: the fractional coloring of paths in a bounded degree trees can be done in a time which is linear in the size of the tree, quadratic in the load of the set of paths, while exponential in the degree of the tree. We give an algorithm based on the generation of an efficient polynomial size linear program. Our algorithm is able to explore in polynomial time the exponential number of different fractional colorings, thanks to the notion of trace of a coloring that we introduce. We further give an upper bound on the cost of such a coloring in binary trees and extend this algorithm to bounded degree graphs with bounded treewidth. Finally, we also show some relationships between the integral and fractional problems, and derive a (1 + 5/3e) ~= 1.61 approximation algorithm for the path coloring problem in bounded degree trees, improving on existing results. This classic combinatorial problem finds applications in the minimization of the number of wavelengths in wavelength division multiplexing (WDM) optical networks. |
@ARTICLE{CFK+09,
sorte = "rev-int",
author = {I. Caragiannis and A. Ferreira and C. Kaklamanis and S. P\'erennes and H. Rivano},
title = {Fractional Path Coloring in Bounded Degree Trees with Applications},
journal = {Algorithmica},
volume = {58},
number = {2},
pages = {516-540},
year = {2010},
abstract = {This paper studies the natural linear programming relaxation of the path coloring problem. We prove constructively that finding an optimal fractional path coloring is Fixed Parameter Tractable (FPT), with the degree of the tree as parameter: the fractional coloring of paths in a bounded degree trees can be done in a time which is linear in the size of the tree, quadratic in the load of the set of paths, while exponential in the degree of the tree. We give an algorithm based on the generation of an efficient polynomial size linear program. Our algorithm is able to explore in polynomial time the exponential number of different fractional colorings, thanks to the notion of trace of a coloring that we introduce. We further give an upper bound on the cost of such a coloring in binary trees and extend this algorithm to bounded degree graphs with bounded treewidth. Finally, we also show some relationships between the integral and fractional problems, and derive a (1 + 5/3e) ~= 1.61 approximation algorithm for the path coloring problem in bounded degree trees, improving on existing results. This classic combinatorial problem finds applications in the minimization of the number of wavelengths in wavelength division multiplexing (WDM) optical networks.},
OPTciteulike-article-id = {4062435},
url = {http://dx.doi.org/10.1007/s00453-009-9278-3},
pdf = {ftp://ftp-sop.inria.fr/mascotte/personnel/Herve.Rivano/Biblio/cfkpr09.pdf},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
x-pays={GR},
}
-
N. Cohen,
D. Dimitrov,
R. Krakovski,
R. Skrekovski,
and V. Vukasinovic.
On Wiener Index of Graphs and Their Line Graphs.
MATCH Commun. Math. Comput. Chem.,
64(3):683-698,
2010.
[PDF
]
| Abstract: |
The Wiener index of a graph $G$, denoted by $W(G)$, is the sum of distances between all pairs of vertices in $G$. In this paper, we consider the relation between the Wiener index of a graph, $G$, and its line graph, $L(G)$. We show that if $G$ is of minimum de\ gree at least two, then $W(G) ⤠W(L(G))$. We prove that for every non-negative integer g0, there exists $g > g_0$, such that there are infinitely many graphs $G$ of girth $g$, satisfying $W(G) = W(L(G))$. This partially answers a question raised by Dobrynin and Melânikov \ [8] and encourages us to conjecture that the answer to a stronger form of their question is affirmative. |
@article{CDK+10,
title = "On Wiener Index of Graphs and Their Line Graphs",
journal = "MATCH Commun. Math. Comput. Chem.",
volume = "64",
number = "3",
pages = "683-698",
year = "2010",
author = "N. Cohen and D. Dimitrov and R. Krakovski and R. Skrekovski and V. Vukasinovic",
abstract = {The Wiener index of a graph $G$, denoted by $W(G)$, is the sum of distances between all pairs of vertices in $G$. In this paper, we consider the relation between the Wiener index of a graph, $G$, and its line graph, $L(G)$. We show that if $G$ is of minimum de\ gree at least two, then $W(G) ⤠W(L(G))$. We prove that for every non-negative integer g0, there exists $g > g_0$, such that there are infinitely many graphs $G$ of girth $g$, satisfying $W(G) = W(L(G))$. This partially answers a question raised by Dobrynin and Melânikov \ [8] and encourages us to conjecture that the answer to a stronger form of their question is affirmative.},
pdf = {http://www.imfm.si/preprinti/PDF/01113.pdf},
OPTx-editorial-board={yes},
OPTx-proceedings={no},
OPTx-international-audience={yes},
x-pays = {FR, SI, DE},
sorte = "rev-int",
}
-
N. Cohen,
F. V. Fomin,
G. Gutin,
E. Jung Kim,
S. Saurabh,
and A. Yeo.
Algorithm for finding k-vertex out-trees and its application to k-internal out-branching problem.
Journal of Computer and System Sciences,
76(7):650 - 662,
2010.
[WWW
] [PDF
]
| Abstract: |
" An out-tree T is an oriented tree with only one vertex of in-degree zero. A vertex x of T is internal if its out-degree is positive. We design randomized and deterministic algorithms for deciding whether an input digraph contains a given out-tree with k vertices. The algorithms are of running time O*(5.704k) and O*(6.14k), respectively. We apply the deterministic algorithm to obtain a deterministic algorithm of runtime O*(ck), where c is a constant, for deciding whether an input digraph contains a spanning out-tree with at least k internal vertices. This answers in affirmative a question of Gutin, Razgon and Kim (Proc. AAIM'08)." |
@article{CFG+10,
title = "Algorithm for finding k-vertex out-trees and its application to k-internal out-branching problem",
journal = "Journal of Computer and System Sciences",
volume = "76",
number = "7",
pages = "650 - 662",
year = "2010",
url = "http://www.sciencedirect.com/science/article/B6WJ0-4Y7P4VB-1/2/82e1f60c51c64592592c857c9c99062b",
pdf = {ftp://ftp-sop.inria.fr/mascotte/Publications/k-out-tree.pdf},
author = "N. Cohen and F. V. Fomin and G. Gutin and E. Jung Kim and S. Saurabh and A. Yeo",
abstract = " An out-tree T is an oriented tree with only one vertex of in-degree zero. A vertex x of T is internal if its out-degree is positive. We design randomized and deterministic algorithms for deciding whether an input digraph contains a given out-tree with k vertices. The algorithms are of running time O*(5.704k) and O*(6.14k), respectively. We apply the deterministic algorithm to obtain a deterministic algorithm of runtime O*(ck), where c is a constant, for deciding whether an input digraph contains a spanning out-tree with at least k internal vertices. This answers in affirmative a question of Gutin, Razgon and Kim (Proc. AAIM'08).",
OPTx-editorial-board={yes},
OPTx-proceedings={no},
OPTx-international-audience={yes},
sorte = "rev-int",
}
-
N. Cohen and F. Havet.
Planar graphs with maximum degree $\Delta\geq 9$ are ($\Delta+1$)-edge-choosable -- short proof.
Discrete Mathematics,
310(21):3049--3051,
2010.
[PDF
]
Keywords:
edge-colouring,
list colouring,
List Colouring Conjecture,
planar graphs.
| Abstract: |
{W}e give a short proof of the following theorem due to {B}orodin~\cite{{B}or90}. {E}very planar graph with maximum degree $\{D}elta\geq 9$ is $(\{D}elta+1)$-edge-choosable. |
@article{CoHa10,
title = { {P}lanar graphs with maximum degree $\Delta\geq 9$ are ($\Delta+1$)-edge-choosable -- short proof},
author = {N. Cohen and F. Havet},
journal = {Discrete Mathematics},
year = {2010},
volume = {310},
number = {21},
pages = {3049--3051},
abstract = {{W}e give a short proof of the following theorem due to {B}orodin~\cite{{B}or90}. {E}very planar graph with maximum degree $\{D}elta\geq 9$ is $(\{D}elta+1)$-edge-choosable.},
pdf = {ftp://ftp-sop.inria.fr/mascotte/Publications/CoHa10.pdf},
keywords = {edge-colouring, list colouring, {L}ist {C}olouring {C}onjecture, planar graphs},
x-editorial-board={yes},
x-proceedings={yes},
x-international-audience={yes},
x-pays={},
sorte = "rev-int",
}
-
D. Coudert,
N. Nepomuceno,
and H. Rivano.
Power-Efficient Radio Configuration in Fixed Broadband Wireless Networks.
Computer Communications, Special Section on Hot Topics in Mesh Networking,
33(8):898-906,
May 2010.
[WWW
] [PDF
]
| Abstract: |
In this work, we investigate on determining feasible radio configurations in fixed broadband wireless networks, focusing on power efficiency. Under this scenario, a power-efficient configuration can be characterized by a modulation constellation size and a transmission power level. Every link holds a set of power-efficient configurations, each of them associating a capacity with its energy cost. We introduce a joint optimization of data routing and radio configuration that minimizes the total energy consumption while handling all the traffic requirements simultaneously. An exact mathematical formulation of the problem is presented. It relies on a minimum cost multicommodity flow with step increasing cost functions, which is very hard to optimize. We then propose a piecewise linear convex function, obtained by linear interpolation of power-efficient points, that provides a good approximation of the energy consumption on the links, and present a relaxation of the previous formulation that exploits
the convexity of the cost functions. This yields lower bounds on the total energy expenditure, and finally heuristic algorithms based on the fractional optimum are employed to produce feasible configuration solutions. Our models are validated through extensive experiments that are reported and discussed. The results testify the potentialities behind this novel approach. |
@article{CNR10,
author = {D. Coudert and N. Nepomuceno and H. Rivano},
title = {Power-Efficient Radio Configuration in Fixed Broadband Wireless Networks},
journal = {Computer Communications, Special Section on Hot Topics in Mesh Networking},
publisher = {Elsevier},
year = {2010},
volume = {33},
number = {8},
pages = {898-906},
month = may,
OPTnote = {available online since January 18 2010.},
pdf = {ftp://ftp-sop.inria.fr/mascotte/personnel/David.Coudert/Publication/CNR10.pdf},
OPTpdf = {http://dx.doi.org/10.1016/j.comcom.2010.01.006},
url = {http://dx.doi.org/10.1016/j.comcom.2010.01.006},
abstract = {In this work, we investigate on determining feasible radio configurations in fixed broadband wireless networks, focusing on power efficiency. Under this scenario, a power-efficient configuration can be characterized by a modulation constellation size and a transmission power level. Every link holds a set of power-efficient configurations, each of them associating a capacity with its energy cost. We introduce a joint optimization of data routing and radio configuration that minimizes the total energy consumption while handling all the traffic requirements simultaneously. An exact mathematical formulation of the problem is presented. It relies on a minimum cost multicommodity flow with step increasing cost functions, which is very hard to optimize. We then propose a piecewise linear convex function, obtained by linear interpolation of power-efficient points, that provides a good approximation of the energy consumption on the links, and present a relaxation of the previous formulation that exploits
the convexity of the cost functions. This yields lower bounds on the total energy expenditure, and finally heuristic algorithms based on the fractional optimum are employed to produce feasible configuration solutions. Our models are validated through extensive experiments that are reported and discussed. The results testify the potentialities behind this novel approach.},
OPTx-editorial-board={yes},
OPTx-proceedings={no},
OPTx-international-audience={yes},
x-pays = {BR},
sorte = "rev-int",
}
-
O. Dalle,
Q. Liu,
G. Wainer,
and B. P. Zeigler.
Applying Cellular Automata and DEVS Methodologies to Digital Games: A Survey.
Simulation & Gaming,
41(6):796-823,
December 2010.
Note: EA DISSIMINET (Associated Team).
[WWW
]
| Abstract: |
Cellular automata were designed by John von Neumann in the 1940s, as a mathematical abstraction for modeling self-replicating algorithms. Since then, cellular automata have been widely studied theoretically and evolved into multiple variants. In the 1970s, Bernard P. Zeigler proposed a formalism rooted on systems theory principles, named DEVS (discrete-event systems specifications), which paved the way for component-based modeling and simulation and related methodologies. The purpose of this article is to survey how cellular automata and its variant, called cell-DEVS, may be used to implement computer simulations that can be used as digital serious games. The authors illustrate that implementation through some of the practical applications of such cellular automata. They show various serious game applications using real case studies: first, a simple bouncing ball and pinball game, a particle collision model, another on gossip propagation, and an application on human behavior at a metro station. Then, they show an application to social simulation using a voters game, a theoretical application (a model called Daisy World, which is derived from Gaia theory), and applications to physical phenomena such as a sandpile formation model or, finally, a three-dimensional model of a "virtual clay" that changes its shape when it is subject to pressure effects. |
@article {WQD+10,
author = {O. Dalle and Q. Liu and G. Wainer and B. P. Zeigler},
title = { Applying Cellular Automata and DEVS Methodologies to Digital Games: A Survey },
pages = {796-823},
journal = {Simulation \& Gaming},
publisher = {Sage Publications},
volume = {41},
number = {6},
year = {2010},
month = Dec,
doi = {doi:10.1177/1046878110378708},
url = {http://hal.inria.fr/inria-00530927},
abstract = {Cellular automata were designed by John von Neumann in the 1940s, as a mathematical abstraction for modeling self-replicating algorithms. Since then, cellular automata have been widely studied theoretically and evolved into multiple variants. In the 1970s, Bernard P. Zeigler proposed a formalism rooted on systems theory principles, named DEVS (discrete-event systems specifications), which paved the way for component-based modeling and simulation and related methodologies. The purpose of this article is to survey how cellular automata and its variant, called cell-DEVS, may be used to implement computer simulations that can be used as digital serious games. The authors illustrate that implementation through some of the practical applications of such cellular automata. They show various serious game applications using real case studies: first, a simple bouncing ball and pinball game, a particle collision model, another on gossip propagation, and an application on human behavior at a metro station. Then, they show an application to social simulation using a voters game, a theoretical application (a model called Daisy World, which is derived from Gaia theory), and applications to physical phenomena such as a sandpile formation model or, finally, a three-dimensional model of a "virtual clay" that changes its shape when it is subject to pressure effects.},
note = {EA DISSIMINET (Associated Team) },
OPTx-editorial-board={yes},
OPTx-proceedings={no},
OPTx-international-audience={yes},
}
-
N. Eggemann,
F. Havet,
and S. Noble.
k-L(2,1)-Labelling for Planar Graphs is NP-Complete for $k\geq 4$.
Discrete Applied Mathematics,
158(16):1777--1788,
2010.
[WWW
] [PDF
]
| Abstract: |
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)$-labelling 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 neighbour are mapped onto distinct integers. It is known that for any fixed $k\ge 4$, deciding the existence of such a labelling is an NP-complete problem while it is polynomial for $k\leq 3$. For even $k\geq 8$, it remains NP-complete when restricted to planar graphs. In this paper, we show that it remains NP-complete for any $k \ge 4$ by reduction from Planar Cubic Two-Colourable Perfect Matching. Schaefer stated without proof that Planar Cubic Two-Colourable Perfect Matching is NP-complete. In this paper we give a proof of this. |
@article{EHN10,
author = {N. Eggemann and F. Havet and S. Noble},
title = {k-L(2,1)-Labelling for Planar Graphs is NP-Complete for $k\geq 4$},
year = {2010},
journal = {Discrete Applied Mathematics},
volume = {158},
number = {16},
pages = {1777--1788},
abstract = {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)$-labelling 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 neighbour are mapped onto distinct integers. It is known that for any fixed $k\ge 4$, deciding the existence of such a labelling is an NP-complete problem while it is polynomial for $k\leq 3$. For even $k\geq 8$, it remains NP-complete when restricted to planar graphs. In this paper, we show that it remains NP-complete for any $k \ge 4$ by reduction from Planar Cubic Two-Colourable Perfect Matching. Schaefer stated without proof that Planar Cubic Two-Colourable Perfect Matching is NP-complete. In this paper we give a proof of this. },
url = {http://hal.inria.fr/inria-00360505/fr/},
pdf = {http://hal.inria.fr/docs/00/36/05/05/PDF/RR-6840.pdf} OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
x-pays={UK},
sorte = "rev-int",
}
-
C. Eslahchi,
H. Pezeshk,
M. Sadeghi,
P. Giabbanelli,
F. Movahedi,
and V. Dabbaghian.
A Probabilistic Model for the Spread of HIV Infection among Injection Drug Users.
World Journal of Modelling and Simulation (WJMS),
6(4):267-273,
November 2010.
[PDF
]
| Abstract: |
By sharing contaminated needles, injecting drug users contribute in a significant manner to the spread of the human immunodeficiency virus (HIV) in Asia and in some European countries. Furthermore, injecting drug users may also be sex workers, and risky sexual activities allow the virus to spread to other parts of the population. Mathematical models of needle sharing have been used to evaluate the success of needle exchange programs, and have led to advances such as new legislations. We use epidemiological classes to model how injecting drug users may start or cease sharing needles under social influences, and may become infected with HIV when sharing. Numerous models based on epidemiological classes were proposed regarding several aspects of HIV, and were commonly studied by differential equations. We instead show how to analyze the theoretical behaviour of the model using the technique of discrete Markov chains. Using simulations, we observed that the prevalence of HIV depended very little on the probability of transmission of HIV when sharing a needle, but almost only on the encouragement and discouragement regarding needle sharing in the community. By measuring the cost of resources required to decrease factors encouraging needle sharing and to increase discouraging ones, our model could be refined to provide an estimate of the expected prevalence of HIV among injecting drug users. |
@article{EPS+10,
author = {C. Eslahchi and H. Pezeshk and M. Sadeghi and P. Giabbanelli and F. Movahedi and V. Dabbaghian},
title = {A Probabilistic Model for the Spread of {HIV} Infection among Injection Drug Users},
journal = {World Journal of Modelling and Simulation (WJMS)},
year = {2010},
OPTkey = {},
volume = {6},
number = {4},
pages = {267-273},
month = nov,
OPTnote = {},
OPTannote = {},
abstract = {By sharing contaminated needles, injecting drug users contribute in a significant manner to the spread of the human immunodeficiency virus (HIV) in Asia and in some European countries. Furthermore, injecting drug users may also be sex workers, and risky sexual activities allow the virus to spread to other parts of the population. Mathematical models of needle sharing have been used to evaluate the success of needle exchange programs, and have led to advances such as new legislations. We use epidemiological classes to model how injecting drug users may start or cease sharing needles under social influences, and may become infected with HIV when sharing. Numerous models based on epidemiological classes were proposed regarding several aspects of HIV, and were commonly studied by differential equations. We instead show how to analyze the theoretical behaviour of the model using the technique of discrete Markov chains. Using simulations, we observed that the prevalence of HIV depended very little on the probability of transmission of HIV when sharing a needle, but almost only on the encouragement and discouragement regarding needle sharing in the community. By measuring the cost of resources required to decrease factors encouraging needle sharing and to increase discouraging ones, our model could be refined to provide an estimate of the expected prevalence of HIV among injecting drug users.},
pdf= {http://www.worldacademicunion.com/journal/1746-7233WJMS/wjmsvol06no04paper03.pdf},
OPTx-editorial-board={yes},
OPTx-proceedings={no},
OPTx-international-audience={yes},
sorte = "rev-int",
}
-
A. Ferreira.
Uma estratégia face à Revolução Digital.
Teoria e Debate,
87:20-23,
2010.
| Abstract: |
A revolu{\c{c}}{\~a}o digital {\'e} o principal motor do atual ritmo acelerado do progresso cient{\'\i}fico e da inova{\c{c}}{\~a}o. O poder criativo e a produtividade tecnol{\'o}gica dos indiv{\'\i}duos est{\~a}o sendo ativados em propor{\c{c}}{\~o}es antes desconhecidas, produzindo ininterruptamente novos produtos e processos, em quase todas as {\'a}reas do conhecimento humano.
O Information Economy Report 2007-2008 da CNUCED detalha como a ind{\'u}stria das Tecnologias da Informa{\c{c}}{\~a}o e da Comunica{\c{c}}{\~a}o (TIC) cresce mais rapidamente do que muitas ind{\'u}strias a n{\'\i}vel mundial. Atualmente, o setor das TIC representa cerca de 7\-1074313544o PIB mundial e emprega mais de 15 milh{\~o}es de pessoas nos pa{\'\i}ses da OECD. Em dados de 2007, as receitas mundiais das 250 maiores empresas em TIC atingiram 3,8 trilh{\~o}es de d{\'o}lares.
Como afirmado por Kofi Annan, antigo Secret{\'a}rio-Geral das Na{\c{c}}{\~o}es Unidas: \"Se o mundo pretende seriamente alcan{\c{c}}ar o Objectivo de Desenvolvimento do Mil{\^e}nio de reduzir em metade o n{\'u}mero de pessoas vivendo em extrema pobreza at{\'e} o ano de 2015, as TIC devem figurar proeminentemente neste esfor{\c{c}}o. Todos â governos, sociedade civil e as empresas do setor privado â devem ajudar a fomentar oportunidades na era digital e colocar as TIC ao servi{\c{c}}o do desenvolvimento.\"
Surpreendentemente, por{\'e}m, mesmo se tal contribui{\c{c}}{\~a}o enorme do setor econ{\^o}mico das TIC ao PIB mundial {\'e} bem compreendida e reconhecida, o impacto real de todas as Ci{\^e}ncias e Tecnologias da Computa{\c{c}}{\~a}o e da Comunica{\c{c}}{\~a}o como facilitadoras e catalisadoras da inova{\c{c}}{\~a}o e do progresso em outros setores econ{\^o}micos e outras disciplinas cient{\'\i}ficas, como a gen{\^o}mica por exemplo, que tamb{\'e}m impactam a sociedade, {\'e} largamente ignorado.
Neste artigo proponho-me a mostrar a import{\^a}ncia de um posicionamento estrat{\'e}gico em rela{\c{c}}{\~a}o {\`a} revolu{\c{c}}{\~a}o digital, informado por atividades multidisciplinares de prospectiva. |
@article{Fer10,
author = {Ferreira, A.},
title = {Uma estrat{\'e}gia face {\`a} Revolu{\c{c}}{\~a}o Digital},
journal = {Teoria e Debate},
year = {2010},
OPTkey = {},
volume = {87},
OPTnumber = {},
pages = {20-23},
OPTmonth = {},
OPTnote = {},
OPTannote = {},
publisher = {Editora Funda{\c{c}}{\~a}o Perseu Abramo},
abstract = {A revolu{\c{c}}{\~a}o digital {\'e} o principal motor do atual ritmo acelerado do progresso cient{\'\i}fico e da inova{\c{c}}{\~a}o. O poder criativo e a produtividade tecnol{\'o}gica dos indiv{\'\i}duos est{\~a}o sendo ativados em propor{\c{c}}{\~o}es antes desconhecidas, produzindo ininterruptamente novos produtos e processos, em quase todas as {\'a}reas do conhecimento humano.
O Information Economy Report 2007-2008 da CNUCED detalha como a ind{\'u}stria das Tecnologias da Informa{\c{c}}{\~a}o e da Comunica{\c{c}}{\~a}o (TIC) cresce mais rapidamente do que muitas ind{\'u}strias a n{\'\i}vel mundial. Atualmente, o setor das TIC representa cerca de 7\-1074313544o PIB mundial e emprega mais de 15 milh{\~o}es de pessoas nos pa{\'\i}ses da OECD. Em dados de 2007, as receitas mundiais das 250 maiores empresas em TIC atingiram 3,8 trilh{\~o}es de d{\'o}lares.
Como afirmado por Kofi Annan, antigo Secret{\'a}rio-Geral das Na{\c{c}}{\~o}es Unidas: \"Se o mundo pretende seriamente alcan{\c{c}}ar o Objectivo de Desenvolvimento do Mil{\^e}nio de reduzir em metade o n{\'u}mero de pessoas vivendo em extrema pobreza at{\'e} o ano de 2015, as TIC devem figurar proeminentemente neste esfor{\c{c}}o. Todos â governos, sociedade civil e as empresas do setor privado â devem ajudar a fomentar oportunidades na era digital e colocar as TIC ao servi{\c{c}}o do desenvolvimento.\"
Surpreendentemente, por{\'e}m, mesmo se tal contribui{\c{c}}{\~a}o enorme do setor econ{\^o}mico das TIC ao PIB mundial {\'e} bem compreendida e reconhecida, o impacto real de todas as Ci{\^e}ncias e Tecnologias da Computa{\c{c}}{\~a}o e da Comunica{\c{c}}{\~a}o como facilitadoras e catalisadoras da inova{\c{c}}{\~a}o e do progresso em outros setores econ{\^o}micos e outras disciplinas cient{\'\i}ficas, como a gen{\^o}mica por exemplo, que tamb{\'e}m impactam a sociedade, {\'e} largamente ignorado.
Neste artigo proponho-me a mostrar a import{\^a}ncia de um posicionamento estrat{\'e}gico em rela{\c{c}}{\~a}o {\`a} revolu{\c{c}}{\~a}o digital, informado por atividades multidisciplinares de prospectiva.},
}
-
A. Ferreira,
A. Goldman,
and J. Monteiro.
Performance evaluation of routing protocols for MANETs with known connectivity patterns using evolving graphs.
Wireless Networks,
16(3):627--640,
2010.
[WWW
] [PDF
]
| Abstract: |
The assessment of routing protocols for mobile wireless networks is a difficult task, because of the networksâ dynamic behavior and the absence of benchmarks. However, some of these networks, such as intermittent wireless sensors networks, periodic or cyclic networks, and some delay tolerant networks (DTNs), have more predictable dynamics, as the temporal variations in the network topology can be considered as deterministic, which may make them easier to study. Recently, a graph theoretic modelâÂÂthe evolving graphsâÂÂwas proposed to help capture the dynamic behavior of such networks, in view of the construction of least cost routing and other algorithms. The algorithms and insights obtained through this model are theoretically very efficient and intriguing. However, there is no study about the use of such theoretical results into practical situations. Therefore, the objective of our work is to analyze the applicability of the evolving graph theory in the construction of efficient routing protocols in realistic scenarios. In this paper, we use the NS2 network simulator to first implement an evolving graph based routing protocol, and then to use it as a benchmark when comparing the four major ad hoc routing protocols (AODV, DSR, OLSR and DSDV). Interestingly, our experiments show that evolving graphs have the potential to be an effective and powerful tool in the development and analysis of algorithms for dynamic networks, with predictable dynamics at least. In order to make this model widely applicable, however, some practical issues still have to be addressed and incorporated into the model, like adaptive algorithms. We also discuss such issues in this paper, as a result of our experience. |
@article{FGM09,
author = {Ferreira, A. and Goldman, A. and Monteiro, J.},
OPTauthor = {Ferreira, Afonso and Goldman, Alfredo and Monteiro, Julian},
title = {Performance evaluation of routing protocols for MANETs with known connectivity patterns using evolving graphs},
journal = {Wireless Networks},
volume = {16},
number = {3},
year = {2010},
issn = {1022-0038},
pages = {627--640},
doi = {http://dx.doi.org/10.1007/s11276-008-0158-6},
abstract = { The assessment of routing protocols for mobile wireless networks is a difficult task, because of the networksâ dynamic behavior and the absence of benchmarks. However, some of these networks, such as intermittent wireless sensors networks, periodic or cyclic networks, and some delay tolerant networks (DTNs), have more predictable dynamics, as the temporal variations in the network topology can be considered as deterministic, which may make them easier to study. Recently, a graph theoretic modelâÂÂthe evolving graphsâÂÂwas proposed to help capture the dynamic behavior of such networks, in view of the construction of least cost routing and other algorithms. The algorithms and insights obtained through this model are theoretically very efficient and intriguing. However, there is no study about the use of such theoretical results into practical situations. Therefore, the objective of our work is to analyze the applicability of the evolving graph theory in the construction of efficient routing protocols in realistic scenarios. In this paper, we use the NS2 network simulator to first implement an evolving graph based routing protocol, and then to use it as a benchmark when comparing the four major ad hoc routing protocols (AODV, DSR, OLSR and DSDV). Interestingly, our experiments show that evolving graphs have the potential to be an effective and powerful tool in the development and analysis of algorithms for dynamic networks, with predictable dynamics at least. In order to make this model widely applicable, however, some practical issues still have to be addressed and incorporated into the model, like adaptive algorithms. We also discuss such issues in this paper, as a result of our experience.},
url = {http://www.springerlink.com/content/c82014477847t646},
OPTx-editorial-board={yes},
pdf = {ftp://ftp-sop.inria.fr/mascotte/Publications/FGM09.pdf},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
sorte="rev-int"
}
-
M. Flammini,
G. Monaco,
L. Moscardelli,
H. Shachnai,
M. Shalom,
T. Tamir,
and S. Zaks.
Minimizing Total Busy Time in Parallel Scheduling with Application to Optical Networks.
Theoretical Computer Science,
411(40-42):3553-3562,
September 2010.
| Abstract: |
We consider a scheduling problem in which a bounded number of jobs can be processed simultaneously by a single machine. The input is a set of $n$ jobs $\mathcal{J}= \{J_1, \ldots , J_n \}$. Each job, $J_j$, is associated with an interval $[s_j, c_j]$ along which it should be processed. Also given is the parallelism parameter $g \ge 1$, which is the maximal number of jobs that can be processed simultaneously by a single machine. Each machine operates along a contiguous time interval, called its {\em busy interval}, which contains all the intervals corresponding to the jobs it processes. The goal is to assign the jobs to machines such that the total busy time of the machines is minimized. The problem is known to be NP-hard already for $g=2$. We present a $4$-approximation algorithm for general instances, and approximation algorithms with improved ratios for instances with bounded lengths, for instances where any two intervals intersect, and for instances where no interval is properly contained in another. Our study has important application in optimizing the switching costs of optical networks. |
@article{FMM+10,
sorte = "rev-int",
author = {M. Flammini and G. Monaco and L. Moscardelli and H. Shachnai and M. Shalom and T. Tamir and S. Zaks},
title = {Minimizing Total Busy Time in Parallel Scheduling with Application to Optical Networks},
year = {2010},
journal = {Theoretical Computer Science},
volume = {411},
number = {40-42},
pages = {3553-3562},
month = sep,
abstract = {We consider a scheduling problem in which a bounded number of jobs can be processed simultaneously by a single machine. The input is a set of $n$ jobs $\mathcal{J}= \{J_1, \ldots , J_n \}$. Each job, $J_j$, is associated with an interval $[s_j, c_j]$ along which it should be processed. Also given is the parallelism parameter $g \ge 1$, which is the maximal number of jobs that can be processed simultaneously by a single machine. Each machine operates along a contiguous time interval, called its {\em busy interval}, which contains all the intervals corresponding to the jobs it processes. The goal is to assign the jobs to machines such that the total busy time of the machines is minimized. The problem is known to be NP-hard already for $g=2$. We present a $4$-approximation algorithm for general instances, and approximation algorithms with improved ratios for instances with bounded lengths, for instances where any two intervals intersect, and for instances where no interval is properly contained in another. Our study has important application in optimizing the switching costs of optical networks.},
doi = {http://dx.doi.org/10.1016/j.tcs.2010.05.011},
OPTx-editorial-board={yes},
OPTx-proceedings={no},
OPTx-international-audience={yes},
sorte = "rev-int",
}
-
F. V. Fomin,
P. A. Golovach,
J. Kratochvil,
N. Nisse,
and K. Suchan.
Pursuing a fast robber on a graph.
Theoretical Computer Science,
411(7-9):1167-1181,
2010.
[WWW
] [PDF
]
| Abstract: |
The Cops and Robbers game as originally defined independently by Quillot and by Nowakowski and Winkler in the 1980â??s has been much studied, but very few results pertain to algorithmic and complexity aspects of it. In this paper we prove that computing the minimum number of cops that are guaranteed too catch a robber on a given graph is NP-hard and that the parametrized version of the problem is W[2]-hard; the proof extends to the case where the robber moves s time faster than the cops. We show that on split graphs, the problem is polynomially solvable if s=1 but is NP-hard if s=2. We further prove that on graphs of bounded cliquewidth the problem is polynomially solvable for s<=2. Finally, we show that for planar graphs the minimum number of cops is unbounded if the robber is faster than the cops. |
@article{FGK+10,
author = {F. V. Fomin and P. A. Golovach and J. Kratochvil and N. Nisse and K. Suchan},
title = {Pursuing a fast robber on a graph},
journal = {Theoretical Computer Science},
volume = {411},
number = {7-9},
year = {2010},
pages = {1167-1181},
abstract = {The Cops and Robbers game as originally defined independently by Quillot and by Nowakowski and Winkler in the 1980â??s has been much studied, but very few results pertain to algorithmic and complexity aspects of it. In this paper we prove that computing the minimum number of cops that are guaranteed too catch a robber on a given graph is NP-hard and that the parametrized version of the problem is W[2]-hard; the proof extends to the case where the robber moves s time faster than the cops. We show that on split graphs, the problem is polynomially solvable if s=1 but is NP-hard if s=2. We further prove that on graphs of bounded cliquewidth the problem is polynomially solvable for s<=2. Finally, we show that for planar graphs the minimum number of cops is unbounded if the robber is faster than the cops.},
url = {http://dx.doi.org/10.1016/j.tcs.2009.12.010},
pdf = {http://dx.doi.org/10.1016/j.tcs.2009.12.010},
OPTx-editorial-board={yes},
OPTx-proceedings={no},
OPTx-international-audience={yes},
x-pays ={NO,CZ,CL},
sorte = "rev-int",
}
-
F. Havet,
D. Král,
J.-S. Sereni,
and R. Skrekovski.
Facial coloring using Hall's theorems.
European Journal of Combinatorics,
31:1001--1019,
2010.
[WWW
] [PDF
]
| Abstract: |
A vertex coloring of a plane graph is $\ell$-facial if every two distinct vertices joined by a facial walk of length at most $\ell$ receive distinct colors. It has been conjectured that every plane graph has an $\ell$-facial coloring with at most $3\ell+1$ colors. We improve the currently best known bound and show that every plane graph has an $\ell$-facial coloring with at most $\lfloor 7\ell/2\rfloor+6$ colors. Our proof uses the standard discharging technique, however, in the reduction part we have successfully applied Hall's Theorem, which seems to be quite an innovative approach in this area. |
@article{HKS+10,
author = {F. Havet and D. Kr\'al and J.-S. Sereni and R. {\v{S}}krekovski},
title = {Facial coloring using {H}all's theorems},
journal = {European Journal of Combinatorics},
volume = {31},
pages={1001--1019},
year = {2010},
url = {http://dx.doi.org/10.1137/060664124},
pdf = {ftp://ftp-sop.inria.fr/mascotte/Publications/HKS+10.pdf},
abstract = {A vertex coloring of a plane graph is $\ell$-facial if every two distinct vertices joined by a facial walk of length at most $\ell$ receive distinct colors. It has been conjectured that every plane graph has an $\ell$-facial coloring with at most $3\ell+1$ colors. We improve the currently best known bound and show that every plane graph has an $\ell$-facial coloring with at most $\lfloor 7\ell/2\rfloor+6$ colors. Our proof uses the standard discharging technique, however, in the reduction part we have successfully applied Hall's Theorem, which seems to be quite an innovative approach in this area.},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
x-pays = {SI,CZ},
sorte = "rev-int",
}
-
C. Molle.
Optimization of the Capacity of Wireless Mesh Networks.
4OR: A Quarterly Journal of Operations Research,
8(4):425-428,
December 2010.
[WWW
]
@article{molle:2010:inria-00629556:1,
AUTHOR = {Molle, C.},
TITLE = {{Optimization of the Capacity of Wireless Mesh Networks}},
JOURNAL = {{4OR: A Quarterly Journal of Operations Research}},
PUBLISHER = {Springer Berlin / Heidelberg},
VOLUME = {8},
NUMBER = {4},
PAGES = {425-428},
YEAR = {2010},
MONTH = Dec,
DOI = {10.1007/s10288-010-0132-x},
URL = {http://hal.inria.fr/inria-00629556/en}
}
-
C. Molle and M-E. Voge.
A quantitative analysis of the capacity of wireless mesh networks.
IEEE Communications Letters,
14(5):438-440,
May 2010.
[WWW
]
@article{molle:2010:inria-00629560:1,
AUTHOR = {Molle, C. and Voge, M-E.},
TITLE = {{A quantitative analysis of the capacity of wireless mesh networks}},
JOURNAL = {{IEEE Communications Letters}},
PUBLISHER = {IEEE},
VOLUME = {14},
NUMBER = {5},
PAGES = {438-440},
YEAR = {2010},
MONTH = May,
DOI = {10.1109/LCOMM.2010.05.100028},
URL = {http://hal.inria.fr/inria-00629560/en}
}
-
H. Rivano,
F. Theoleyre,
and F. Valois.
A Framework for the Capacity Evaluation of Multihop Wireless Networks.
Ad Hoc and Sensor Wireless networks (AHSWN),
9(3-4):139-162,
2010.
[PDF
]
| Abstract: |
The specific challenges of multihop wireles networks lead to a strong research effort on efficient protocols design where the offered capacity is a key objective. More specifically, routing strategy largely impacts the network capacity, i.e. the throughput offered to each flow. In this work, we propose a complete framework to compute the upper and the lower bounds of the network capacity according to a physical topology and a given routing protocol. The radio resource sharing principles of CSMA-CA is modeled as a set of linear constraints with two models of fairness. The first one assumes that nodes have a fair access to the channel, while the second one assumes that on the radio links. We then develop a pessimistic and an optimistic scenarios for radio resource sharing, yielding a lower bound and an upper bound on the network capacity for each fairness case. Our approach is independent of the network topology and the routing protocols, and provides therefore a relevant framework for their comparison. We apply our models to a comparative analysis of a well-known flat routing protocol OLSR against two main self-organized structure approaches, VSR and localized CDS. |
@article{RTV10,
author = {H. Rivano and F. Theoleyre and F. Valois},
title = {A Framework for the Capacity Evaluation of Multihop Wireless Networks},
journal = {Ad Hoc and Sensor Wireless networks (AHSWN)},
volume = {9},
number = {3-4},
pages = {139-162},
year = {2010},
abstract = {The specific challenges of multihop wireles networks lead to a strong research effort on efficient protocols design where the offered capacity is a key objective. More specifically, routing strategy largely impacts the network capacity, i.e. the throughput offered to each flow. In this work, we propose a complete framework to compute the upper and the lower bounds of the network capacity according to a physical topology and a given routing protocol. The radio resource sharing principles of CSMA-CA is modeled as a set of linear constraints with two models of fairness. The first one assumes that nodes have a fair access to the channel, while the second one assumes that on the radio links. We then develop a pessimistic and an optimistic scenarios for radio resource sharing, yielding a lower bound and an upper bound on the network capacity for each fairness case. Our approach is independent of the network topology and the routing protocols, and provides therefore a relevant framework for their comparison. We apply our models to a comparative analysis of a well-known flat routing protocol OLSR against two main self-organized structure approaches, VSR and localized CDS.},
pdf = {ftp://ftp-sop.inria.fr/mascotte/personnel/Herve.Rivano/Biblio/rtv09.pdf},
OPTnote = {Accepted for publications : march 19th 2009. To be published},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
sorte = "rev-int",
}
-
I. Sau and D. M. Thilikos.
Subexponential Parameterized Algorithms for Degree-constrained Subgraph Problems on Planar Graphs.
Journal of Discrete Algorithms,
8(3):330-338,
September 2010.
[WWW
] [PDF
]
| Abstract: |
We present subexponential parameterized algorithms on planar graphs for a family of problems of the following shape: given a graph, find a connected (induced) subgraph with bounded maximum degree and with maximum number of edges (or vertices). These problems are natural generalisations of the \textsc{Longest Path} problem. Our approach uses bidimensionality theory combined with novel dynamic programming techniques over branch decompositions of the input graph. These techniques can be applied to a more general family of problems that deal with finding connected subgraphs under certain degree constraints. |
@ARTICLE{SaTh10,
sorte = "rev-int",
AUTHOR = {I. Sau and D. M. Thilikos},
TITLE = {Subexponential Parameterized Algorithms for Degree-constrained Subgraph Problems on Planar Graphs},
JOURNAL = {Journal of Discrete Algorithms},
volume = {8},
number = {3},
pages = {330-338},
YEAR = {2010},
month = sep,
ABSTRACT = {We present subexponential parameterized algorithms on planar graphs for a family of problems of the following shape: given a graph, find a connected (induced) subgraph with bounded maximum degree and with maximum number of edges (or vertices). These problems are natural generalisations of the \textsc{Longest Path} problem. Our approach uses bidimensionality theory combined with novel dynamic programming techniques over branch decompositions of the input graph. These techniques can be applied to a more general family of problems that deal with finding connected subgraphs under certain degree constraints.},
url = {http://dx.doi.org/10.1016/j.jda.2010.02.002},
PDF = {http://www.cs.technion.ac.il/~ignasi/Pubs/SaTh10.pdf},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
x-pays = {GR,ES},
}
-
E. Alvarez-Miranda,
A. Candia,
X. Chen,
X. Hu,
and B. Li.
Efficient Algorithms for the Prize Collecting Steiner Tree Problems with Interval Data.
In Proceedings of the 6th International Conference on Algorithmic Aspects in Information and Management (AAIM),
volume 6124 of Lecture Notes in Computer Science,
Weihai, China,
pages 13-24,
July 2010.
Springer.
[WWW
] [PDF
]
| Abstract: |
Given a graph $G=(V,E)$ with a cost on each edge in $E$ and a prize at each vertex in $V$, and a target set $V'\subseteq V$, the Prize Collecting Steiner Tree (PCST) problem is to find a tree $T$ interconnecting vertices in $V'$ that has minimum total costs on edges and maximum total prizes at vertices in $T$. This problem is NP-hard in general, and it is polynomial-time solvable when graphs $G$ are restricted to 2-trees. In this paper, we study how to deal with PCST problem with uncertain costs and prizes. We assume that edge $e$ could be included in $T$ by paying cost $x_e\in[c_e^-,c_e^+]$ while taking risk $\frac{ c_e^+-x_e}{ c_e^+-c_e^-}$ of losing $e$, and vertex $v$ could be awarded prize $p_v\in [p_v^-,p_v^+]$ while taking risk $\frac{ y_v-p_v^-}{p_v^+-p_v^-}$ of losing the prize. We establish two risk models for the PCST problem, one minimizing the maximum risk over edges and vertices in $T$ and the other minimizing the sum of risks. Both models are subject to upper bounds on the budget for constructing a tree. We propose two polynomial-time algorithms for these problems on 2-trees, respectively. Our study shows that the risk models have advantages over the tradional robust optimization model, which yields NP-hard problems even if the original optimization problems are polynomial-time solvable. |
@inproceedings{ACC+10,
author = {Alvarez-Miranda, E. and Candia, A. and Chen, X. and Hu, X. and Li, B. },
title = {Efficient Algorithms for the Prize Collecting Steiner Tree Problems with Interval Data},
booktitle = {Proceedings of the 6th International Conference on Algorithmic Aspects in Information and Management (AAIM)},
address ={Weihai, China},
month =jul,
year = {2010},
volume = {6124},
series = {Lecture Notes in Computer Science},
publisher = {Springer},
pages = {13-24},
x-editorial-board={yes},
x-proceedings={yes},
x-international-audience={yes},
x-pays = {CL,CN},
URL-HAL = {},
X-ID-HAL = {},
abstract = {Given a graph $G=(V,E)$ with a cost on each edge in $E$ and a prize at each vertex in $V$, and a target set $V'\subseteq V$, the Prize Collecting Steiner Tree (PCST) problem is to find a tree $T$ interconnecting vertices in $V'$ that has minimum total costs on edges and maximum total prizes at vertices in $T$. This problem is NP-hard in general, and it is polynomial-time solvable when graphs $G$ are restricted to 2-trees. In this paper, we study how to deal with PCST problem with uncertain costs and prizes. We assume that edge $e$ could be included in $T$ by paying cost $x_e\in[c_e^-,c_e^+]$ while taking risk $\frac{ c_e^+-x_e}{ c_e^+-c_e^-}$ of losing $e$, and vertex $v$ could be awarded prize $p_v\in [p_v^-,p_v^+]$ while taking risk $\frac{ y_v-p_v^-}{p_v^+-p_v^-}$ of losing the prize. We establish two risk models for the PCST problem, one minimizing the maximum risk over edges and vertices in $T$ and the other minimizing the sum of risks. Both models are subject to upper bounds on the budget for constructing a tree. We propose two polynomial-time algorithms for these problems on 2-trees, respectively. Our study shows that the risk models have advantages over the tradional robust optimization model, which yields NP-hard problems even if the original optimization problems are polynomial-time solvable. },
pdf = {ftp://ftp-sop.inria.fr/mascotte/Publications/ACC+10.pdf},
url = {http://dx.doi.org/10.1007/978-3-642-14355-7_3},
sorte = "conf-int",
}
-
J. Araujo,
C. Linhares Sales,
and I. Sau.
Weighted Coloring on $P_4$-sparse Graphs.
In 11es Journées Doctorales en Informatique et Réseaux (JDIR 2010),
Sophia Antipolis, France,
pages 33--38,
March 2010.
[PDF
]
| Abstract: |
Given an undirected graph G = (V, E) and a weight function w : V â R+, a vertex coloring of G is a partition of V into independent sets, or color classes. The weight of a vertex coloring of G is defined as the sum of the weights of its color classes, where the weight of a color class is the weight of a heaviest vertex belonging to it. In the WEIGHTED COLORING problem, we want to determine the minimum weight among all vertex colorings of G [1]. This problem is NP-hard on general graphs, as it reduces to determining the chromatic number when all the weights are equal. In this article we study the WEIGHTED COLORING problem on P4-sparse graphs, which are defined as graphs in which every subset of five vertices induces at most one path on four vertices [2]. This class of graphs has been extensively studied in the literature during the last decade, and many hard optimization problems are known to be in P when restricted to this class. Note that cographs (that is, P4-free graphs) are P4-sparse, and that P4-sparse graphs are P5-free. The WEIGHTED COLORING problem is in P on cographs [3] and NP-hard on P5-free graphs [4]. We show that WEIGHTED COLORING can be solved in polynomial time on a subclass of P4-sparse graphs that strictly contains cographs, and we present a 2-approximation algorithm on general P4-sparse graphs. The complexity of WEIGHTED COLORING on P4- sparse graphs remains open. |
@inproceedings{ASL10,
author = {Araujo, J. and Linhares Sales, C. and Sau, I.},
title = {Weighted Coloring on $P_4$-sparse Graphs},
booktitle = {11es Journ\'{e}es Doctorales en Informatique et R\'{e}seaux (JDIR 2010)},
pages = {33--38},
year = {2010},
address = {Sophia Antipolis, France},
month = mar,
abstract = {Given an undirected graph G = (V, E) and a weight function w : V â R+, a vertex coloring of G is a partition of V into independent sets, or color classes. The weight of a vertex coloring of G is defined as the sum of the weights of its color classes, where the weight of a color class is the weight of a heaviest vertex belonging to it. In the WEIGHTED COLORING problem, we want to determine the minimum weight among all vertex colorings of G [1]. This problem is NP-hard on general graphs, as it reduces to determining the chromatic number when all the weights are equal. In this article we study the WEIGHTED COLORING problem on P4-sparse graphs, which are defined as graphs in which every subset of five vertices induces at most one path on four vertices [2]. This class of graphs has been extensively studied in the literature during the last decade, and many hard optimization problems are known to be in P when restricted to this class. Note that cographs (that is, P4-free graphs) are P4-sparse, and that P4-sparse graphs are P5-free. The WEIGHTED COLORING problem is in P on cographs [3] and NP-hard on P5-free graphs [4]. We show that WEIGHTED COLORING can be solved in polynomial time on a subclass of P4-sparse graphs that strictly contains cographs, and we present a 2-approximation algorithm on general P4-sparse graphs. The complexity of WEIGHTED COLORING on P4- sparse graphs remains open.},
pdf = {ftp://ftp-sop.inria.fr/mascotte/Publications/ASL10.pdf},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
x-pays={FR},
sorte = "conf-nat",
}
-
J. Beauquier and J. Burman.
Self-stabilizing Synchronization in Mobile Sensor Networks with Covering.
In Distributed Computing in Sensor Systems, 6th IEEE International Conference, DCOSS 2010,
volume 6131 of Lecture Notes in Computer Science,
pages 362-378,
2010.
Springer.
[PDF
]
| Abstract: |
Synchronization is widely considered as an important service in distributed systems which may simplify protocol design. \emph{Phase clock} is a general synchronization tool that provides a form of a logical time. This paper presents a \emph{self-stabilizing} (a tolerating state-corrupting transient faults) phase clock algorithm suited to the model of \emph{population protocols with covering}. This model has been proposed recently for sensor networks with a very large, possibly \emph{unknown} number of \emph{anonymous} mobile agents having \emph{small memory}. Agents interact in pairs in an \emph{asynchronous} way subject to the constraints expressed in terms of the \emph{cover times} of agents. The cover time expresses the ``frequency'' of an agent to communicate with all the others and abstracts agent's communication characteristics (e.g. moving speed/patterns, transmitting/receiving capabilities). We show that a phase clock is impossible in the model with only constant-state agents. Hence, we assume an existence of resource-unlimited agent - the base station.
The clock size and duration of each phase of the proposed phase clock tool are adjustable by the user. We provide application examples of this tool and demonstrate how it can simplify the design of protocols. In particular, it yields a solution to Group Mutual Exclusion problem. |
@inproceedings{BeBu10,
author = {Beauquier, J. and Burman, J.},
title = {Self-stabilizing Synchronization in Mobile Sensor Networks with Covering},
booktitle = {Distributed Computing in Sensor Systems, 6th IEEE International Conference, DCOSS 2010},
publisher = {Springer},
series = {Lecture Notes in Computer Science},
volume = {6131},
year = {2010},
pages = {362-378},
abstract = {Synchronization is widely considered as an important service in distributed systems which may simplify protocol design. \emph{Phase clock} is a general synchronization tool that provides a form of a logical time. This paper presents a \emph{self-stabilizing} (a tolerating state-corrupting transient faults) phase clock algorithm suited to the model of \emph{population protocols with covering}. This model has been proposed recently for sensor networks with a very large, possibly \emph{unknown} number of \emph{anonymous} mobile agents having \emph{small memory}. Agents interact in pairs in an \emph{asynchronous} way subject to the constraints expressed in terms of the \emph{cover times} of agents. The cover time expresses the ``frequency'' of an agent to communicate with all the others and abstracts agent's communication characteristics (e.g. moving speed/patterns, transmitting/receiving capabilities). We show that a phase clock is impossible in the model with only constant-state agents. Hence, we assume an existence of resource-unlimited agent - the base station.
The clock size and duration of each phase of the proposed phase clock tool are adjustable by the user. We provide application examples of this tool and demonstrate how it can simplify the design of protocols. In particular, it yields a solution to Group Mutual Exclusion problem.},
pdf = {http://dx.doi.org/10.1007/978-3-642-13651-1_26},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
sorte = "conf-int"
}
-
J. Beauquier,
J. Burman,
J. Clement,
and S. Kutten.
On Utilizing Speed in Networks of Mobile Agents.
In Proceedings of the 29th Annual ACM Symposium on Principles of Distributed Computing, PODC 2010,
pages 305-314,
2010.
ACM.
[PDF
]
| Abstract: |
Population protocols are a model presented recently for networks with a very large, possibly unknown number of mobile agents having small memory. This model has certain advantages over alternative models (such as DTN) for such networks. However, it was shown that the computational power of this model is limited to semi-linear predicates only. Hence, various extensions were suggested.
We present a model that enhances the original model of population protocols by introducing a (weak) notion of speed of the agents. This enhancement allows us to design fast converging protocols with only weak requirements (for example, suppose that there are different types of agents, say agents attached to sick animals and to healthy animals, two meeting agents just need to be able to estimate which of them is faster, e.g., using their types, but not to actually know the speeds of their types).
Then, using the new model, we study the gathering problem, in which there is an unknown number of anonymous agents that have values they should deliver to a base station (without replications). We develop efficient protocols step by step searching for an optimal solution and adapting to the size of the available memory. The protocols are simple, though their analysis is somewhat involved. We also present a more involved result - a lower bound on the length of the worst execution for any protocol. Our proofs introduce several techniques that may prove useful also in future studies of time in population protocols. |
@inproceedings{BBC+10,
author = {Beauquier, J. and Burman, J. and Clement, J. and Kutten, S.},
title = {On Utilizing Speed in Networks of Mobile Agents},
booktitle = {Proceedings of the 29th Annual ACM Symposium on Principles of Distributed Computing, PODC 2010},
publisher = {ACM},
year = {2010},
pages = {305-314},
abstract = {Population protocols are a model presented recently for networks with a very large, possibly unknown number of mobile agents having small memory. This model has certain advantages over alternative models (such as DTN) for such networks. However, it was shown that the computational power of this model is limited to semi-linear predicates only. Hence, various extensions were suggested.
We present a model that enhances the original model of population protocols by introducing a (weak) notion of speed of the agents. This enhancement allows us to design fast converging protocols with only weak requirements (for example, suppose that there are different types of agents, say agents attached to sick animals and to healthy animals, two meeting agents just need to be able to estimate which of them is faster, e.g., using their types, but not to actually know the speeds of their types).
Then, using the new model, we study the gathering problem, in which there is an unknown number of anonymous agents that have values they should deliver to a base station (without replications). We develop efficient protocols step by step searching for an optimal solution and adapting to the size of the available memory. The protocols are simple, though their analysis is somewhat involved. We also present a more involved result - a lower bound on the length of the worst execution for any protocol. Our proofs introduce several techniques that may prove useful also in future studies of time in population protocols.},
pdf = {http://doi.acm.org/10.1145/1835698.1835775},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
x-pays = {IL},
sorte = "conf-int"
}
-
J-C. Bermond,
D. Mazauric,
V. Misra,
and P. Nain.
A Distributed Scheduling Algorithm for Wireless Networks with Constant Overhead and Arbitrary Binary Interference.
In SIGMETRICS 2010,
pages 2p,
2010.
ACM.
[PDF
]
| Abstract: |
This work investigates distributed transmission scheduling in wireless networks. Due to interference constraints, "neighboring links" cannot be simultaneously activated, otherwise transmissions will fail. Here, we consider any binary model of interference. We follow the model described by Bui, Sanghavi, and Srikant in SBS07,SBS09. We suppose that time is slotted and during each slot we have two phases: one control phase which determines what links will be activated and send data during the second phase. We assume random arrivals on each link during each slot, therefore a queue is associated to each link. Since nodes do not have a global knowledge of the network, our aim (like in SBS07,SBS09) is to design for the control phase, a distributed algorithm which determines a set of non interfering links. To be efficient the control phase should be as short as possible; this is done by exchanging control messages during a constant number of mini-slots (constant overhead). In this article we design the first fully distributed local algorithm with the following properties: it works for any arbitrary binary interference model; it has a constant overhead (independent of the size of the network and the values of the queues); and it needs no knowledge. Indeed contrary to other existing algorithms, we do not need to know the values of the queues of the "neighboring links", which are difficult to obtain in a wireless network with interference. We prove that this algorithm gives a maximal set of active links (in each interference set, there is at least one active edge). We also give sufficient conditions for stability under Markovian assumptions. Finally the performance of our algorithm (throughput, stability) is investigated and compared via simulations to that of previously proposed schemes. |
@inproceedings{BMM+10,
author = {J-C. Bermond and D. Mazauric and V. Misra and P. Nain},
title = {A Distributed Scheduling Algorithm for Wireless Networks with Constant Overhead and Arbitrary Binary Interference},
booktitle = {SIGMETRICS 2010},
year = {2010},
publisher = {ACM},
pages = {2p},
url={},
pdf = {ftp://ftp-sop.inria.fr/mascotte/personnel/Jean-Claude.Bermond/PUBLIS/BMMN10.pdf},
abstract = {This work investigates distributed transmission scheduling in wireless networks. Due to interference constraints, "neighboring links" cannot be simultaneously activated, otherwise transmissions will fail. Here, we consider any binary model of interference. We follow the model described by Bui, Sanghavi, and Srikant in SBS07,SBS09. We suppose that time is slotted and during each slot we have two phases: one control phase which determines what links will be activated and send data during the second phase. We assume random arrivals on each link during each slot, therefore a queue is associated to each link. Since nodes do not have a global knowledge of the network, our aim (like in SBS07,SBS09) is to design for the control phase, a distributed algorithm which determines a set of non interfering links. To be efficient the control phase should be as short as possible; this is done by exchanging control messages during a constant number of mini-slots (constant overhead). In this article we design the first fully distributed local algorithm with the following properties: it works for any arbitrary binary interference model; it has a constant overhead (independent of the size of the network and the values of the queues); and it needs no knowledge. Indeed contrary to other existing algorithms, we do not need to know the values of the queues of the "neighboring links", which are difficult to obtain in a wireless network with interference. We prove that this algorithm gives a maximal set of active links (in each interference set, there is at least one active edge). We also give sufficient conditions for stability under Markovian assumptions. Finally the performance of our algorithm (throughput, stability) is investigated and compared via simulations to that of previously proposed schemes.},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
sorte = "conf-int",
}
-
C. Caillouet,
F. Huc,
N. Nisse,
S. Pérennes,
and H. Rivano.
Stability of a localized and greedy routing algorithm.
In 12th Workshop on Advances in Parallel and Distributed Computational Models,
pages 8p,
2010.
IEEE.
[WWW
] [PDF
]
| Abstract: |
In this work, we study the problem of routing packets between undifferentiated sources and sinks in a network modeled by a multigraph. We consider a distributed and local algorithm that transmits packets hop by hop in the network and study its behavior. At each step, a node transmits its queued packets to its neighbors in order to optimize a local gradient. This protocol is greedy since it does not require to record the history about the past actions, and localized since nodes only need information about their neighborhood.
A transmission protocol is \emph{stable} if the number of packets in the network does not diverge. To prove the stability, it is sufficient to prove that the number of packets stored in the network remains bounded as soon as the sources inject a flow that another method could have exhausted. The localized and greedy protocol considered has been shown to be stable in some specific cases related to the arrival rate of the packets. We investigate its stability in a more general context and therefore reinforce results from the literature that worked for differentiated suboptimal flows.
We show that, to prove the stability of this protocol, it is sufficient to prove the intuitive following conjecture: roughly, if the protocol is stable when all sources inject the maximum number of packets at each turn and no packets are lost, then the protocol is stable whatever be the behavior of the network (i.e., when less packets are injected and some of them may be lost). |
@inproceedings{HCN+10,
author = {C. Caillouet and F. Huc and N. Nisse and S. P\'erennes and H. Rivano},
title = {Stability of a localized and greedy routing algorithm},
booktitle = {12th Workshop on Advances in Parallel and Distributed Computational Models},
OPTcrossref = {},
OPTkey = {},
pages = {8p},
year = {2010},
publisher = {IEEE},
OPTnote = {to appear},
OPTannote = {},
url = {http://hal.inria.fr/inria-00331807},
pdf = {ftp://ftp-sop.inria.fr/mascotte/Publications/HCN+10.pdf},
abstract = {In this work, we study the problem of routing packets between undifferentiated sources and sinks in a network modeled by a multigraph. We consider a distributed and local algorithm that transmits packets hop by hop in the network and study its behavior. At each step, a node transmits its queued packets to its neighbors in order to optimize a local gradient. This protocol is greedy since it does not require to record the history about the past actions, and localized since nodes only need information about their neighborhood.
A transmission protocol is \emph{stable} if the number of packets in the network does not diverge. To prove the stability, it is sufficient to prove that the number of packets stored in the network remains bounded as soon as the sources inject a flow that another method could have exhausted. The localized and greedy protocol considered has been shown to be stable in some specific cases related to the arrival rate of the packets. We investigate its stability in a more general context and therefore reinforce results from the literature that worked for differentiated suboptimal flows.
We show that, to prove the stability of this protocol, it is sufficient to prove the intuitive following conjecture: roughly, if the protocol is stable when all sources inject the maximum number of packets at each turn and no packets are lost, then the protocol is stable whatever be the behavior of the network (i.e., when less packets are injected and some of them may be lost).},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
sorte = "conf-int",
}
-
C. Caillouet,
S. Perennes,
and H. Rivano.
Cross line and column generation for the cut covering problem in wireless networks.
In International Symposium on Combinatorial Optimization (ISCO),
pages 8p,
March 2010.
Note: To appear.
[WWW
] [PDF
]
| Abstract: |
In this paper, we address the problem of bandwidth allocation and routing in wire- less networks. A first model of this problem is known as the Round Weighting Problem (RWP) in which a weight is assigned to the set of rounds, i.e. a set of pairwise non-interfering links. We present a new formulation that forgets about the routing and concentrate on the capacity available on the network cuts. We use the maximum flow/minimum cut theorem known in graph theory to develop the Cut Covering Problem (CCP) and prove that it computes equivalent optimal round weights than RWP. We develop a primal/dual algorithm combining line and column generation to deal with the exponential number of variables and constraints of CCP. |
@inproceedings{CPR10,
author = {C. Caillouet and S. Perennes and H. Rivano},
title = {Cross line and column generation for the cut covering problem in wireless networks},
booktitle = {International Symposium on Combinatorial Optimization (ISCO)},
year = {2010},
pages = {8p},
month = mar,
note = {To appear},
url = {http://www.lamsade.dauphine.fr/~isco/},
pdf = {ftp://ftp-sop.inria.fr/mascotte/Publications/CPR10.pdf},
abstract = {In this paper, we address the problem of bandwidth allocation and routing in wire- less networks. A first model of this problem is known as the Round Weighting Problem (RWP) in which a weight is assigned to the set of rounds, i.e. a set of pairwise non-interfering links. We present a new formulation that forgets about the routing and concentrate on the capacity available on the network cuts. We use the maximum flow/minimum cut theorem known in graph theory to develop the Cut Covering Problem (CCP) and prove that it computes equivalent optimal round weights than RWP. We develop a primal/dual algorithm combining line and column generation to deal with the exponential number of variables and constraints of CCP.},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
sorte = "conf-int",
}
-
S. Caron,
F. Giroire,
D. Mazauric,
J. Monteiro,
and S. Pérennes.
Data Life Time for Different Placement Policies in P2P Storage Systems.
In Proceedings of the 3rd Intl. Conference on Data Management in Grid and P2P Systems (Globe),
volume 6265 of Lecture Notes in Computer Science,
Bilbao, Spain,
pages 75--88,
September 2010.
[PDF
]
Keywords:
P2P storage system,
data placement,
performance,
data durability,
Markov chain model.
| Abstract: |
Peer-to-peer systems are foreseen as an efficient solution to achieve reliable data storage at low cost. To deal with common P2P problems such as peer failures or churn, such systems encode the user data into redundant fragments and distribute them among peers. The way they distribute it, known as placement policy, has a significant impact on their behavior and reliability. In this paper, we study the impact of different placement policies on the data life time. More precisely, we describe methods to compute and approximate the mean time before the system loses data (Mean Time to Data Loss). We compare this metric for three placement policies: two of them local, in which the data is stored in logical peer neighborhoods, and one of them global in which fragments are parted uniformly at random among the different peers. |
@inproceedings{CGM+10c,
author = {S. Caron and F. Giroire and D. Mazauric and J. Monteiro and S. P\'erennes},
title = { Data Life Time for Different Placement Policies in P2P Storage Systems},
booktitle = {Proceedings of the 3rd Intl. Conference on Data Management in Grid and P2P Systems (Globe)},
abstract = {Peer-to-peer systems are foreseen as an efficient solution to achieve reliable data storage at low cost. To deal with common P2P problems such as peer failures or churn, such systems encode the user data into redundant fragments and distribute them among peers. The way they distribute it, known as placement policy, has a significant impact on their behavior and reliability. In this paper, we study the impact of different placement policies on the data life time. More precisely, we describe methods to compute and approximate the mean time before the system loses data (Mean Time to Data Loss). We compare this metric for three placement policies: two of them local, in which the data is stored in logical peer neighborhoods, and one of them global in which fragments are parted uniformly at random among the different peers.},
year = {2010},
pages = {75--88},
address = {Bilbao, Spain},
volume = {6265},
series = {Lecture Notes in Computer Science},
month = sep,
audience = {internationale },
keywords = {{P2P} storage system;data placement;performance;data durability;{M}arkov chain model},
language = {{A}nglais},
pdf = {ftp://ftp-sop.inria.fr/mascotte/Publications/CGM+10c.pdf},
OPTx-editorial-board = {yes},
OPTx-international-audience = {yes},
OPTx-proceedings = {yes},
sorte = {conf-int},
}
-
S. Caron,
F. Giroire,
D. Mazauric,
J. Monteiro,
and S. Pérennes.
P2P Storage Systems: Data Life Time for Different Placement Policies.
In Maria Gradinariu Potop-Butucaru et Hervé Rivano, editor,
12èmes Rencontres Francophones sur les Aspects Algorithmiques de Télécommunications (AlgoTel),
Belle Dune France,
pages 4p,
2010.
[WWW
] [PDF
]
Keywords:
P2P storage system,
data placement,
performance,
data durability,
Markov chain model.
| Abstract: |
{L}es syst{\`e}mes pair-{\`a}-pair {\`a} grande {\'e}chelle repr{\'e}sentent un moyen fiable pour stocker des donn{\'e}es {\`a} faible co{\^u}t. {A}fin d'assurer la p{\'e}rennit{\'e} des donn{\'e}es des utilisateurs, il est n{\'e}cessaire d'ajouter de la redondance. {A}insi {\`a} partir de s fragments initiaux composant un bloc de donn{\'e}es, s+r fragments sont g{\'e}n{\'e}r{\'e}s et r{\'e}partis entre les pairs du r{\'e}seau. {N}ous {\'e}tudions dans ce papier l'impact des diff{\'e}rentes politiques de placement sur la dur{\'e}e de vie des donn{\'e}es. {P}lus particuli{\`e}rement nous d{\'e}crivons des m{\'e}thodes pour calculer et approximer le temps moyen avant que le syst{\`e}me perde une donn{\'e}e ({M}ean {T}ime to {D}ata {L}oss). {N}ous comparons cette m{\'e}trique pour trois politiques de placement: deux sont locales, distribuant les fragments sur des voisins logiques, et la troisi{\`e}me est globale. |
@inproceedings{CGM+10b,
title = { {P}2{P} {S}torage {S}ystems: {D}ata {L}ife {T}ime for {D}ifferent {P}lacement {P}olicies},
author = {Caron, S. and Giroire, F. and Mazauric, D. and Monteiro, J. and P\'erennes, S.},
abstract = {{L}es syst{\`e}mes pair-{\`a}-pair {\`a} grande {\'e}chelle repr{\'e}sentent un moyen fiable pour stocker des donn{\'e}es {\`a} faible co{\^u}t. {A}fin d'assurer la p{\'e}rennit{\'e} des donn{\'e}es des utilisateurs, il est n{\'e}cessaire d'ajouter de la redondance. {A}insi {\`a} partir de s fragments initiaux composant un bloc de donn{\'e}es, s+r fragments sont g{\'e}n{\'e}r{\'e}s et r{\'e}partis entre les pairs du r{\'e}seau. {N}ous {\'e}tudions dans ce papier l'impact des diff{\'e}rentes politiques de placement sur la dur{\'e}e de vie des donn{\'e}es. {P}lus particuli{\`e}rement nous d{\'e}crivons des m{\'e}thodes pour calculer et approximer le temps moyen avant que le syst{\`e}me perde une donn{\'e}e ({M}ean {T}ime to {D}ata {L}oss). {N}ous comparons cette m{\'e}trique pour trois politiques de placement: deux sont locales, distribuant les fragments sur des voisins logiques, et la troisi{\`e}me est globale.},
keywords = {{P}2{P} storage system;data placement;performance;data durability;{M}arkov chain model},
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 - {MAESTRO} - {INRIA} {S}ophia {A}ntipolis - {INRIA} - {U}niversit{\'e} {M}ontpellier {II} - {S}ciences et {T}echniques du {L}anguedoc },
booktitle = {12{\`e}mes {R}encontres {F}rancophones sur les {A}spects {A}lgorithmiques de {T}{\'e}l{\'e}communications ({A}lgo{T}el)},
pages = {4p},
address = {{B}elle {D}une {F}rance },
editor = {{M}aria {G}radinariu {P}otop-{B}utucaru et {H}erv{\'e} {R}ivano },
audience = {internationale },
year = {2010},
url = {http://hal.inria.fr/inria-00479537/en/},
pdf = {http://hal.inria.fr/inria-00479537/PDF/placement-algotel2010-finale.pdf},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
sorte = "conf-nat",
}
-
J. Chalopin,
V. Chepoi,
N. Nisse,
and Y. Vaxes.
Cop and robber games when the robber can hide and ride.
In 8th French Combinatorial Conference,
Orsay,
June 2010.
Note: Selection on abstract.
| Abstract: |
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 dismantlable graphs. In this talk, we will characterize in a similar way the class CWFR(s, s') of cop-win graphs in the game in which the cop and the robber move at different speeds s' and s, s' ? s. We also establish some connections between cop-win graphs for this game with s'< s and Gromovâs hyperbolicity. In the particular case s' = 1 and s = 2, we prove that the class of cop-win graphs is exactly the well-known class of dually chordal graphs. We show that all classes CWFR(s,1), s ? 3, coincide and we provide a structural characterization of these graphs. We also investigate several dismantling schemes necessary or sufficient for the cop-win graphs (which we call k-winnable and denote by CWW(k)) 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 k-winnable for any value of k. |
@inproceedings{CCN+10b,
author = {J. Chalopin and V. Chepoi and N. Nisse and Y. Vaxes},
title = {Cop and robber games when the robber can hide and ride},
booktitle = {8th French Combinatorial Conference},
year = {2010},
address = {Orsay},
month = jun,
note = {selection on abstract},
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 dismantlable graphs. In this talk, we will characterize in a similar way the class CWFR(s, s') of cop-win graphs in the game in which the cop and the robber move at different speeds s' and s, s' ? s. We also establish some connections between cop-win graphs for this game with s'< s and Gromovâs hyperbolicity. In the particular case s' = 1 and s = 2, we prove that the class of cop-win graphs is exactly the well-known class of dually chordal graphs. We show that all classes CWFR(s,1), s ? 3, coincide and we provide a structural characterization of these graphs. We also investigate several dismantling schemes necessary or sufficient for the cop-win graphs (which we call k-winnable and denote by CWW(k)) 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 k-winnable for any value of k.},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
sorte = "conf-sa",
}
-
N. Cohen,
D. Coudert,
D. Mazauric,
N. Nepomuceno,
and N. Nisse.
Tradeoffs in process strategy games with application in the WDM reconfiguration problem.
In P. Boldi and L. Gargano, editors,
Fifth International conference on Fun with Algorithms (FUN 2010),
volume 6099 of Lecture Notes in Computer Science,
Ischia Island, Italy,
pages 121-132,
June 2010.
Springer.
Note: Http://hal.inria.fr/inria-00495443.
[WWW
] [PDF
]
| Abstract: |
We consider a variant of the graph searching games that is closely related to the routing reconfiguration problem in WDM networks. In the digraph processing game, a team of agents is aiming at clearing, or processing, the vertices of a digraph D. In this game, two important measures arise: 1) the total number of agents used, and 2) the total number of vertices occupied by an agent during the processing of D. Previous works have studied the problem of minimizing each of these parameters independently. In particular, both of these optimization problems are not in APX. In this paper, we study the tradeoff between both these conflicting objectives. More precisely, we prove that there exist some instances 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 in the case of basic network topologies. On the other hand, we exhibit classes of instances where good tradeoffs can be achieved. We also show that minimizing one of these parameters while the other is constrained is not in APX. |
@inproceedings{CCM+10,
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},
booktitle = {Fifth International conference on Fun with Algorithms (FUN 2010)},
year = {2010},
pages = {121-132},
publisher = {Springer},
editor = {P. Boldi and L. Gargano},
volume = {6099},
series = {Lecture Notes in Computer Science},
address = {Ischia Island, Italy},
month = jun,
note = {http://hal.inria.fr/inria-00495443},
url = {http://dx.doi.org/10.1007/978-3-642-13122-6_14},
ee = {http://dx.doi.org/10.1007/978-3-642-13122-6_14},
PDF = {ftp://ftp-sop.inria.fr/mascotte/Publications/CCM+10.pdf},
ABSTRACT = {We consider a variant of the graph searching games that is closely related to the routing reconfiguration problem in WDM networks. In the digraph processing game, a team of agents is aiming at clearing, or processing, the vertices of a digraph D. In this game, two important measures arise: 1) the total number of agents used, and 2) the total number of vertices occupied by an agent during the processing of D. Previous works have studied the problem of minimizing each of these parameters independently. In particular, both of these optimization problems are not in APX. In this paper, we study the tradeoff between both these conflicting objectives. More precisely, we prove that there exist some instances 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 in the case of basic network topologies. On the other hand, we exhibit classes of instances where good tradeoffs can be achieved. We also show that minimizing one of these parameters while the other is constrained is not in APX.},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
x-pays = {BR},
sorte = "conf-int",
}
-
N. Cohen,
D. Coudert,
D. Mazauric,
N. Nepomuceno,
and N. Nisse.
Tradeoffs in routing reconfiguration problems.
In Maria Gradinariu Potop-Butucaru et Hervé Rivano, editor,
12èmes Rencontres Francophones sur les Aspects Algorithmiques de Télécommunications (AlgoTel),
Belle Dune France,
pages 4p,
2010.
[WWW
] [PDF
]
| Abstract: |
{N}ous {\'e}tudions le probl{\`e}me du reroutage d'un ensemble de connexion dans un r{\'e}seau. {I}l consiste {\`a} passer d'un routage initial (ensemble de chemins reliant des paires de noeuds) {\`a} un autre, en traitant s{\'e}quentiellement chaque connexion. {I}l est parfois indispensable d'en interrompre temporairement certaines au cours du processus de reconfiguration, ce qui nous am{\`e}ne {\`a} {\'e}tudier les compromis possibles entre deux mesures d'efficacit{\'e} : le nombre total de connexions interrompues et le nombre maximum de connexions interrompues simultan{\'e}ment. {N}ous prouvons qu'{\'e}tablir de tels compromis m{\`e}ne {\`a} des probl{\`e}mes {NP}-complets et difficiles {\`a} approcher ({APX}-difficiles voir non {APX}). {N}ous montrons ensuite que de bons compromis sont impossibles en g{\'e}n{\'e}ral. {E}nfin, nous exhibons une classe d'instances de reroutage pour laquelle il est possible de minimiser le nombre de requ{\^e}tes interrompues simultan{\'e}ment sans "trop" augmenter le nombre total de connexions interrompues. {C}es r{\'e}sultats sont obtenus en mod{\'e}lisant ce probl{\`e}me par un jeu {\`a} l'aide d'agents mobiles. |
@inproceedings{CCM+10b,
title = { {T}radeoffs in routing reconfiguration problems},
OPTauthor = {{C}ohen, {N}athann and {C}oudert, {D}avid and {M}azauric, {D}orian and {N}epomuceno, {N}apole{\~a}o and {N}isse, {N}icolas},
author = {Cohen, N. and Coudert, D. and Mazauric, D. and Nepomuceno, N. and Nisse, N.},
abstract = {{N}ous {\'e}tudions le probl{\`e}me du reroutage d'un ensemble de connexion dans un r{\'e}seau. {I}l consiste {\`a} passer d'un routage initial (ensemble de chemins reliant des paires de noeuds) {\`a} un autre, en traitant s{\'e}quentiellement chaque connexion. {I}l est parfois indispensable d'en interrompre temporairement certaines au cours du processus de reconfiguration, ce qui nous am{\`e}ne {\`a} {\'e}tudier les compromis possibles entre deux mesures d'efficacit{\'e} : le nombre total de connexions interrompues et le nombre maximum de connexions interrompues simultan{\'e}ment. {N}ous prouvons qu'{\'e}tablir de tels compromis m{\`e}ne {\`a} des probl{\`e}mes {NP}-complets et difficiles {\`a} approcher ({APX}-difficiles voir non {APX}). {N}ous montrons ensuite que de bons compromis sont impossibles en g{\'e}n{\'e}ral. {E}nfin, nous exhibons une classe d'instances de reroutage pour laquelle il est possible de minimiser le nombre de requ{\^e}tes interrompues simultan{\'e}ment sans "trop" augmenter le nombre total de connexions interrompues. {C}es r{\'e}sultats sont obtenus en mod{\'e}lisant ce probl{\`e}me par un jeu {\`a} l'aide d'agents mobiles.},
language = {{A}nglais},
booktitle = {12{\`e}mes {R}encontres {F}rancophones sur les {A}spects {A}lgorithmiques de {T}{\'e}l{\'e}communications ({A}lgo{T}el)},
pages = {4p},
address = {{B}elle {D}une {F}rance },
editor = {{M}aria {G}radinariu {P}otop-{B}utucaru et {H}erv{\'e} {R}ivano },
audience = {internationale },
year = {2010},
URL = {http://hal.inria.fr/inria-00477413/en/},
PDF = {http://hal.inria.fr/inria-00477413/PDF/algotel.pdf},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
sorte = "conf-nat",
}
-
D. Coudert.
Graph searching games for the WDM reconfiguration problem.
In 24th European Conference on Operational Research (EURO),
Lisbon, Portugal,
pages 1p,
July 2010.
Note: Invited talk.
[WWW
]
| Abstract: |
The routing reconfiguration problem in WDM networks is to schedule the switching's of a set of lightpaths from one routing to a new predetermined one. This problem is modeled as a digraph processing game, closely related to graph searching games, in which a team of agents is aiming at clearing, or processing, the vertices of a digraph. In this talk, we will survey the main results on digraph processing games, and in particular the complexity and hardness of optimizing tradeoffs between the total number of agents used and the total number of vertices occupied by an agent during the strategy |
@inproceedings{Cou10b,
author = {D. Coudert},
title = {Graph searching games for the {WDM} reconfiguration problem},
OPTcrossref = {},
OPTkey = {},
booktitle = {24th European Conference on Operational Research (EURO)},
pages = {1p},
year = {2010},
OPTeditor = {},
OPTvolume = {},
OPTnumber = {},
OPTseries = {},
address = {Lisbon, Portugal},
month = jul,
OPTorganization = {},
OPTpublisher = {},
note = {Invited talk},
OPTannote = {},
url = {http://hal.inria.fr/inria-00482113},
abstract = {The routing reconfiguration problem in WDM networks is to schedule the switching's of a set of lightpaths from one routing to a new predetermined one. This problem is modeled as a digraph processing game, closely related to graph searching games, in which a team of agents is aiming at clearing, or processing, the vertices of a digraph. In this talk, we will survey the main results on digraph processing games, and in particular the complexity and hardness of optimizing tradeoffs between the total number of agents used and the total number of vertices occupied by an agent during the strategy},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
sorte = "inv-conf",
}
-
P. Giabbanelli.
Impact of complex network properties on routing in backbone networks.
In Proceedings of the IEEE Globecom 2010 Workshop on Complex and Communication Networks (CCNet 2010),
2010.
[PDF
]
| Abstract: |
The properties found in complex networks (e.g., small-world, scale-free) have been used to characterize the behaviour of several processes such as epidemics or oscillators. We analyze the impact of such properties on the quality of a routing process. Using a Mixed Integer/Linear Program, the routing minimizes the number of ports installed in the network. Ports are network components which we use as a simplification of the capital cost in communication networks. Using data mining techniques, we are able to predict the minimal number of ports of a network with small error rate given the networkâs properties and under the assumption of a realistic traffic distribution. We find that the average betweenness and the average path length are good indicators of the number of ports. We then present exploratory work on the dynamic aspects by considering that nodes join the network, which corresponds to the deployment of communication equipment. We consider several approaches to deploy the equipment, and report on the number of ports for each approach. By comparing approaches, having less edges can still yield better performances which motivates investigations on the design. Furthermore, this dynamic case confirms the static one since a tradeoff between the average betweenness and the average path length seems to be a key element in efficient designs. |
@inproceedings{Gia10b,
author = "P. Giabbanelli",
title="Impact of complex network properties on routing in backbone networks",
year={2010},
booktitle={Proceedings of the IEEE Globecom 2010 Workshop on Complex and Communication Networks (CCNet 2010)},
pdf = {ftp://ftp-sop.inria.fr/mascotte/Publications/gia10b.pdf},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
sorte = "conf-int",
abstract= { The properties found in complex networks (e.g., small-world, scale-free) have been used to characterize the behaviour of several processes such as epidemics or oscillators. We analyze the impact of such properties on the quality of a routing process. Using a Mixed Integer/Linear Program, the routing minimizes the number of ports installed in the network. Ports are network components which we use as a simplification of the capital cost in communication networks. Using data mining techniques, we are able to predict the minimal number of ports of a network with small error rate given the networkâs properties and under the assumption of a realistic traffic distribution. We find that the average betweenness and the average path length are good indicators of the number of ports. We then present exploratory work on the dynamic aspects by considering that nodes join the network, which corresponds to the deployment of communication equipment. We consider several approaches to deploy the equipment, and report on the number of ports for each approach. By comparing approaches, having less edges can still yield better performances which motivates investigations on the design. Furthermore, this dynamic case confirms the static one since a tradeoff between the average betweenness and the average path length seems to be a key element in efficient designs. },
}
-
P. Giabbanelli,
A. Alimadad,
V. Dabbaghian,
and D. T. Finegood.
Modeling the influence of social networks and environment on energy balance and obesity.
In XI International Conference on Obesity (ICO),
July 2010.
Note: Acceptance rate 8.6%.
@inproceedings{GAD+10,
author = {P. Giabbanelli and A. Alimadad and V. Dabbaghian and D. T. Finegood},
title = {Modeling the influence of social networks and environment on energy balance and obesity},
booktitle = {XI International Conference on Obesity (ICO)},
month = jul,
year = {2010},
note = {Acceptance rate 8.6%},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
sorte = "conf-int",
}
-
P. Giabbanelli,
D. Mazauric,
and J-C. Bermond.
Average path length of deterministic and stochastics recursive networks.
In Proceedings of the 2nd Workshop on Complex Networks (CompleNet),
volume 116 of Communications in Computer and Information Science (CCIS),
pages 1--12,
2010.
Springer-Verlag.
[PDF
]
| Abstract: |
The average shortest path distance between all pairs of nodes in real-world networks tends to be small compared to the number of nodes. Providing a closed-form formula for remains challenging in several network models, as shown by recent papers dedicated to this sole topic. For example, Zhang et al. proposed the deterministic model ZRG and studied an upper bound on . In this paper, we use graph-theoretic techniques to establish a closed-form formula for in ZRG. Our proof is of particular interests for other network models relying on similar re- cursive structures, as found in fractal models. We extend our approach to a stochastic version of ZRG in which layers of triangles are added with probability p. We find a first-order phase transition at the critical probability pc = 0.5, from which the expected number of nodes becomes infinite whereas expected distances remain finite. We show that if tri- angles are added independently instead of being constrained in a layer, the first-order phase transition holds for the very same critical probabil- ity. Thus, we provide an insight showing that models can be equivalent, regardless of whether edges are added with grouping constraints. Our detailed computations also provide thorough practical cases for readers unfamiliar with graph-theoretic and probabilistic techniques. |
@inproceedings{GMB10,
author={P. Giabbanelli and D. Mazauric and J-C. Bermond},
title="Average path length of deterministic and stochastics recursive networks",
year={2010},
booktitle={Proceedings of the 2nd Workshop on Complex Networks (CompleNet)},
publisher={Springer-Verlag},
series={Communications in Computer and Information Science (CCIS)},
volume = {116},
pages={1--12},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
PDF={ftp://ftp-sop.inria.fr/mascotte/Publications/GMB10.pdf},
sorte = "conf-int",
abstract = {The average shortest path distance between all pairs of nodes in real-world networks tends to be small compared to the number of nodes. Providing a closed-form formula for remains challenging in several network models, as shown by recent papers dedicated to this sole topic. For example, Zhang et al. proposed the deterministic model ZRG and studied an upper bound on . In this paper, we use graph-theoretic techniques to establish a closed-form formula for in ZRG. Our proof is of particular interests for other network models relying on similar re- cursive structures, as found in fractal models. We extend our approach to a stochastic version of ZRG in which layers of triangles are added with probability p. We find a first-order phase transition at the critical probability pc = 0.5, from which the expected number of nodes becomes infinite whereas expected distances remain finite. We show that if tri- angles are added independently instead of being constrained in a layer, the first-order phase transition holds for the very same critical probabil- ity. Thus, we provide an insight showing that models can be equivalent, regardless of whether edges are added with grouping constraints. Our detailed computations also provide thorough practical cases for readers unfamiliar with graph-theoretic and probabilistic techniques.},
}
-
P. Giabbanelli,
D. Mazauric,
and S. Pérennes.
Computing the average path length and a label-based routing in a small-world graph.
In 12èmes Rencontres Francophones sur les Aspects Algorithmiques de Télécommunications (AlgoTel'10),
Belle Dune France,
pages 4p,
2010.
[WWW
] [PDF
]
Keywords:
Recursive graph,
Labeling scheme,
Decentralized routing.
| Abstract: |
{W}e study two characteristics of a small-world graph proposed by {Z}hang et al. to model complex networks. {O}ur study relies on the recursive structure of the graph. {F}irstly, we use it to design a labelling scheme in order to create an implicit routing (i.e., a routing scheme based on the label of vertices). {S}econdly, proving the average distance in this graph was arduous, thus {Z}hang et al. chose to study the diameter: we establish a closed-form formula of the average distance, proved using the recursive structure. {T}hus, we characterize that the graph is small-world and not ultra small-world as was still possible. {O}ur proof is of particular interest for other graphs based on similar recursive structures. |
@inproceedings{GMP10,
title = { {C}omputing the average path length and a label-based routing in a small-world graph},
author = {Giabbanelli, P. and Mazauric, D. and P\'erennes, S.},
abstract = {{W}e study two characteristics of a small-world graph proposed by {Z}hang et al. to model complex networks. {O}ur study relies on the recursive structure of the graph. {F}irstly, we use it to design a labelling scheme in order to create an implicit routing (i.e., a routing scheme based on the label of vertices). {S}econdly, proving the average distance in this graph was arduous, thus {Z}hang et al. chose to study the diameter: we establish a closed-form formula of the average distance, proved using the recursive structure. {T}hus, we characterize that the graph is small-world and not ultra small-world as was still possible. {O}ur proof is of particular interest for other graphs based on similar recursive structures.},
keywords = {{R}ecursive graph; {L}abeling scheme; {D}ecentralized routing},
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 - {MAESTRO} - {INRIA} {S}ophia {A}ntipolis - {INRIA} - {U}niversit{\'e} {M}ontpellier {II} - {S}ciences et {T}echniques du {L}anguedoc },
booktitle = {12{\`e}mes {R}encontres {F}rancophones sur les {A}spects {A}lgorithmiques de {T}{\'e}l{\'e}communications (AlgoTel'10)},
pages = {4p },
address = {{B}elle {D}une {F}rance },
year = {2010},
url = {http://hal.archives-ouvertes.fr/inria-00472215/en/},
pdf = {http://hal.archives-ouvertes.fr/inria-00472215/PDF/algotel.pdf},
OPTx-editorial-board={yes},
OPTx-proceedings={no},
OPTx-international-audience={yes},
sorte = "conf-nat",
}
-
F. Giroire,
D. Mazauric,
J. Moulierac,
and B. Onfroy.
Minimizing Routing Energy Consumption: from Theoretical to Practical Results.
In IEEE/ACM International Conference on Green Computing and Communications (GreenCom'10),
Hangzhou, China,
pages 8,
2010.
[PDF
]
| Abstract: |
Several studies exhibit that the traffic load of the routers only has a small influence on their energy consumption. Hence, the power consumption in networks is strongly related to the number of active network elements, such as interfaces, line cards, base chassis,... The goal thus is to find a routing that minimizes the (weighted) number of active network elements used when routing. In this paper, we consider a simplified architecture where a connection between two routers is represented as a link joining two network interfaces. When a connection is not used, both network interfaces can be turned off. Therefore, in order to reduce power consumption, the goal is to find the routing that minimizes the number of used links while satisfying all the demands. We first define formally the problem and we model it as an integer linear program. Then, we prove that this problem is not in APX, that is there is no polynomial-time constant-factor approximation algorithm. We propose a heuristic algorithm for this problem and we also prove some negative results about basic greedy and probabilistic algorithms. Thus we present a study on specific topologies, such as trees, grids and complete graphs, that provide bounds and results useful for real topologies. We then exhibit the gain in terms of number of network interfaces (leading to a global reduction of approximately 33 MWh for a medium-sized backbone network) for a set of existing network topologies: we see that for almost all topologies more than one third of the network interfaces can be spared for usual ranges of operation. Finally, we discuss the impact of energy efficient routing on the stretch factor and on fault tolerance. |
@inproceedings{GMM10b,
title = {Minimizing Routing Energy Consumption: from Theoretical to Practical Results},
author = {Giroire, F. and Mazauric, D. and Moulierac, J. and Onfroy, B.},
language = {Anglais},
booktitle = {IEEE/ACM International Conference on Green Computing and Communications (GreenCom'10)},
pages = {8},
address = {Hangzhou, China},
year = {2010},
abstract = {Several studies exhibit that the traffic load of the routers only has a small influence on their energy consumption. Hence, the power consumption in networks is strongly related to the number of active network elements, such as interfaces, line cards, base chassis,... The goal thus is to find a routing that minimizes the (weighted) number of active network elements used when routing. In this paper, we consider a simplified architecture where a connection between two routers is represented as a link joining two network interfaces. When a connection is not used, both network interfaces can be turned off. Therefore, in order to reduce power consumption, the goal is to find the routing that minimizes the number of used links while satisfying all the demands. We first define formally the problem and we model it as an integer linear program. Then, we prove that this problem is not in APX, that is there is no polynomial-time constant-factor approximation algorithm. We propose a heuristic algorithm for this problem and we also prove some negative results about basic greedy and probabilistic algorithms. Thus we present a study on specific topologies, such as trees, grids and complete graphs, that provide bounds and results useful for real topologies. We then exhibit the gain in terms of number of network interfaces (leading to a global reduction of approximately 33 MWh for a medium-sized backbone network) for a set of existing network topologies: we see that for almost all topologies more than one third of the network interfaces can be spared for usual ranges of operation. Finally, we discuss the impact of energy efficient routing on the stretch factor and on fault tolerance.},
pdf = {http://hal.archives-ouvertes.fr/inria-00464318/PDF/RR-7234.pdf},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
sorte = "conf-int",
}
-
F. Giroire,
J. Monteiro,
and S. Pérennes.
Peer-to-Peer Storage Systems: a Practical Guideline to be Lazy.
In Proceedings of the IEEE Global Communications Conference (GLOBECOM),
Miami, EUA,
pages 1-6,
12 2010.
[WWW
] [PDF
]
| Abstract: |
Distributed and peer-to-peer storage systems are foreseen as an alternative to the traditional data centers and in-house backup solutions. In the past few years many peer-to- peer storage systems have been proposed. Most of them rely on the use of erasure codes to introduce redundancy to the data. This kind of system depends on many parameters that need to be well tuned, such as the factor of redundancy, the frequency of data repair and the size of a data block. In this paper we give closed-form mathematical expressions that estimate the system average behavior. These expressions are derived from a Markov chain. Our contribution is a guideline to system designers and administrators to choose the best set of parameters. That is, how to tune the system parameters to obtain a desired level of reliability under a given constraint of bandwidth consumption. We confirm that a lazy repair strategy can be employed to amortize the repairing cost. Moreover, we propose a formula to calculate the optimal threshold value that minimizes the bandwidth consumption. Finally, we additionally discuss the impact of different system characteristics on the performance metrics, such as the number of peers, the amount of stored data, and the disk failure rate. To the best of our knowledge this is the first work to give close-form formulas to estimate the bandwidth consumption for a lazy repair, and the loss rate taking into account the repair time. |
@inproceedings{GMP10b,
title = {Peer-to-Peer Storage Systems: a Practical Guideline to be Lazy},
author = {F. Giroire and J. Monteiro and S. P\'erennes},
language = {{A}nglais},
booktitle = {Proceedings of the IEEE Global Communications Conference (GLOBECOM)},
abstract = {Distributed and peer-to-peer storage systems are foreseen as an alternative to the traditional data centers and in-house backup solutions. In the past few years many peer-to- peer storage systems have been proposed. Most of them rely on the use of erasure codes to introduce redundancy to the data. This kind of system depends on many parameters that need to be well tuned, such as the factor of redundancy, the frequency of data repair and the size of a data block. In this paper we give closed-form mathematical expressions that estimate the system average behavior. These expressions are derived from a Markov chain. Our contribution is a guideline to system designers and administrators to choose the best set of parameters. That is, how to tune the system parameters to obtain a desired level of reliability under a given constraint of bandwidth consumption. We confirm that a lazy repair strategy can be employed to amortize the repairing cost. Moreover, we propose a formula to calculate the optimal threshold value that minimizes the bandwidth consumption. Finally, we additionally discuss the impact of different system characteristics on the performance metrics, such as the number of peers, the amount of stored data, and the disk failure rate. To the best of our knowledge this is the first work to give close-form formulas to estimate the bandwidth consumption for a lazy repair, and the loss rate taking into account the repair time.},
pages={1-6},
address = {Miami, EUA},
year = {2010},
month = {12},
x-pays={FR},
url = {http://dx.doi.org/10.1109/GLOCOM.2010.5683761},
pdf = {ftp://ftp-sop.inria.fr/mascotte/Publications/GMP10.pdf},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
sorte = "conf-int",
}
-
N. Hanusse,
D. Ilcinkas,
A. Kosowski,
and N. Nisse.
Comment battre la marche aléatoire en comptant ?.
In 12ème Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications (AlgoTel'10),
pages 4p,
2010.
[WWW
] [PDF
]
| Abstract: |
Nous \'etudions le probl\`eme consistant \`a trouver une destination t dans un r\'eseau, non fiable, gr\^ace \`a un agent mobile. Chaque noeud du r\'eseau peut donner un conseil quant au prochain sommet \`a visiter pour se rapprocher de t. Malheureusement, k noeuds, appel\'es menteurs, donnent de mauvais conseils. Il est connu que pour un graphe G de n sommets et de degr\'e maximum Delta >= 3, atteindre une cible \`a distance d de la position initiale peut demander un temps moyen de 2^{Omega(min{d,k})}, pour tout d,k=O(log n), même lorsque G est un arbre. Ce papier \'etudie une strat\'egie, appel\'ee R/A, utilisant un compteur (d'\'etapes) pour alterner entre les phases al\'eatoires (R) où l'agent choisit al\'eatoirement une arête incidente, et celles (A) où l'agent suit le conseil local. Aucune connaissance des param\`etres n, d, ou k n'est requise, et l'agent n'a pas besoin de se rappeler par quel lien il est entr\'e dans le sommet qu'il occupe. Nous \'etudions les performances de cette strat\'egie pour deux classes de graphes, extrêmes pour ce qui est de l'expansion: les anneaux et les graphes r\'eguliers al\'eatoires (une importante classe d' expanders). Pour l'anneau, l'algorithme R/A requiert un temps moyen de 2d+k^{Theta(1)} (polynomial en d et k) pour une distribution des menteurs la plus d\'efavorable. A l'oppos\'e, nous montrons que dans un anneau, une marche al\'eatoire biais\'ee requiert un temps moyen exponentiel en d et k. Pour les graphes al\'eatoires r\'eguliers, le temps de recherche moyen de l'algorithme R/A est O(k3 log3 n) a.a.s.\ Le terme polylogarithmique de cette borne ne peut pas être am\'elior\'e, puisque nous montrons une borne inf\'erieure de Omega(log n) pour d,k=Omega(log log n) dans les graphes al\'eatoires r\'eguliers a.a.s. qui s'applique même lorsque l'agent a le sens de l'orientation. |
@inproceedings{HIK+10c,
author = {N. Hanusse and D. Ilcinkas and A. Kosowski and N. Nisse},
title = {Comment battre la marche al\'eatoire en comptant ?},
booktitle = {12\`eme Rencontres Francophones sur les Aspects Algorithmiques des T\'el\'ecommunications (AlgoTel'10)},
pages = {4p},
year = {2010},
OPTnote = {to appear},
url = {http://hal.archives-ouvertes.fr/inria-00475863/fr/},
pdf = {http://hal.archives-ouvertes.fr/docs/00/47/58/63/PDF/Menteurs-algotel2010.pdf},
abstract = {Nous \'etudions le probl\`eme consistant \`a trouver une destination t dans un r\'eseau, non fiable, gr\^ace \`a un agent mobile. Chaque noeud du r\'eseau peut donner un conseil quant au prochain sommet \`a visiter pour se rapprocher de t. Malheureusement, k noeuds, appel\'es menteurs, donnent de mauvais conseils. Il est connu que pour un graphe G de n sommets et de degr\'e maximum Delta >= 3, atteindre une cible \`a distance d de la position initiale peut demander un temps moyen de 2^{Omega(min{d,k})}, pour tout d,k=O(log n), même lorsque G est un arbre. Ce papier \'etudie une strat\'egie, appel\'ee R/A, utilisant un compteur (d'\'etapes) pour alterner entre les phases al\'eatoires (R) où l'agent choisit al\'eatoirement une arête incidente, et celles (A) où l'agent suit le conseil local. Aucune connaissance des param\`etres n, d, ou k n'est requise, et l'agent n'a pas besoin de se rappeler par quel lien il est entr\'e dans le sommet qu'il occupe. Nous \'etudions les performances de cette strat\'egie pour deux classes de graphes, extrêmes pour ce qui est de l'expansion: les anneaux et les graphes r\'eguliers al\'eatoires (une importante classe d' expanders). Pour l'anneau, l'algorithme R/A requiert un temps moyen de 2d+k^{Theta(1)} (polynomial en d et k) pour une distribution des menteurs la plus d\'efavorable. A l'oppos\'e, nous montrons que dans un anneau, une marche al\'eatoire biais\'ee requiert un temps moyen exponentiel en d et k. Pour les graphes al\'eatoires r\'eguliers, le temps de recherche moyen de l'algorithme R/A est O(k3 log3 n) a.a.s.\ Le terme polylogarithmique de cette borne ne peut pas être am\'elior\'e, puisque nous montrons une borne inf\'erieure de Omega(log n) pour d,k=Omega(log log n) dans les graphes al\'eatoires r\'eguliers a.a.s. qui s'applique même lorsque l'agent a le sens de l'orientation.},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
sorte = "conf-nat",
}
-
N. Hanusse,
D. Ilcinkas,
A. Kosowski,
and N. Nisse.
Locating a target with an agent guided by unreliable local advice.
In 29th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC'10),
volume XXXX,
pages 10p,
2010.
ACM.
Note: To appear.
[PDF
]
| Abstract: |
{W}e study the problem of finding a destination node $t$ by a mobile agent in an unreliable network having the structure of an unweighted graph, in a model first proposed by {H}anusse {\it et al.}~\cite{{HKK}00,{HKKK}08}. {E}ach node of the network is able to give advice concerning the next node to visit so as to go closer to the target $t$. {U}nfortunately, exactly $k$ of the nodes, called \emph{liars}, give advice which is incorrect. {I}t is known that for an $n$-node graph ${G}$ of maximum degree $\{D}elta \geq 3$, reaching a target at a distance of $d$ from the initial location may require an expected time of $2^{\{O}mega(\min\{d,k\})}$, for any $d,k={O}(\log n)$, even when ${G}$ is a tree. {T}his paper focuses on strategies which efficiently solve the search problem in scenarios in which, at each node, the agent may only choose between following the local advice, or randomly selecting an incident edge. {T}he strategy which we put forward, called \algo{{R}/{A}}, makes use of a timer (step counter) to alternate between phases of ignoring advice (\algo{{R}}) and following advice (\algo{{A}}) for a certain number of steps. {N}o knowledge of parameters $n$, $d$, or $k$ is required, and the agent need not know by which edge it entered the node of its current location. {T}he performance of this strategy is studied for two classes of regular graphs with extremal values of expansion, namely, for rings and for random $\maxdeg$-regular graphs (an important class of expanders). {F}or the ring, \algo{{R}/{A}} is shown to achieve an expected searching time of $2d+k^{\{T}heta(1)}$ for a worst-case distribution of liars, which is polynomial in both $d$ and $k$. {F}or random $\maxdeg$-regular graphs, the expected searching time of the \algo{{R}/{A}} strategy is ${O}(k3 \log3 n)$ a.a.s. {T}he polylogarithmic factor with respect to $n$ cannot be dropped from this bound; in fact, we show that a lower time bound of $\{O}mega (\log n)$ steps holds for all $d,k=\{O}mega(\log\log n)$ in random $\maxdeg$-regular graphs a.a.s.\ and applies even to strategies which make use of some knowledge of the environment. {F}inally, we study oblivious strategies which do not use any memory (in particular, with no timer). {S}uch strategies are essentially a form of a random walk, possibly biased by local advice. {W}e show that such biased random walks sometimes achieve drastically worse performance than the \algo{{R}/{A}} strategy. {I}n particular, on the ring, no biased random walk can have a searching time which is polynomial in $d$ and $k$ |
@inproceedings{HIK+10b,
title = {Locating a target with an agent guided by unreliable local advice},
author = {Hanusse, {N}. and Ilcinkas, {D}. and Kosowski, {A}. and Nisse, {N}.},
booktitle = {29th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC'10)},
year = {2010},
publisher = {ACM},
volume = {XXXX},
pages = {10p},
note = {to appear},
url={},
PDF = {http://www-sop.inria.fr/members/Nicolas.Nisse/publications/podc2010.pdf},
abstract = {{W}e study the problem of finding a destination node $t$ by a mobile agent in an unreliable network having the structure of an unweighted graph, in a model first proposed by {H}anusse {\it et al.}~\cite{{HKK}00,{HKKK}08}. {E}ach node of the network is able to give advice concerning the next node to visit so as to go closer to the target $t$. {U}nfortunately, exactly $k$ of the nodes, called \emph{liars}, give advice which is incorrect. {I}t is known that for an $n$-node graph ${G}$ of maximum degree $\{D}elta \geq 3$, reaching a target at a distance of $d$ from the initial location may require an expected time of $2^{\{O}mega(\min\{d,k\})}$, for any $d,k={O}(\log n)$, even when ${G}$ is a tree. {T}his paper focuses on strategies which efficiently solve the search problem in scenarios in which, at each node, the agent may only choose between following the local advice, or randomly selecting an incident edge. {T}he strategy which we put forward, called \algo{{R}/{A}}, makes use of a timer (step counter) to alternate between phases of ignoring advice (\algo{{R}}) and following advice (\algo{{A}}) for a certain number of steps. {N}o knowledge of parameters $n$, $d$, or $k$ is required, and the agent need not know by which edge it entered the node of its current location. {T}he performance of this strategy is studied for two classes of regular graphs with extremal values of expansion, namely, for rings and for random $\maxdeg$-regular graphs (an important class of expanders). {F}or the ring, \algo{{R}/{A}} is shown to achieve an expected searching time of $2d+k^{\{T}heta(1)}$ for a worst-case distribution of liars, which is polynomial in both $d$ and $k$. {F}or random $\maxdeg$-regular graphs, the expected searching time of the \algo{{R}/{A}} strategy is ${O}(k3 \log3 n)$ a.a.s. {T}he polylogarithmic factor with respect to $n$ cannot be dropped from this bound; in fact, we show that a lower time bound of $\{O}mega (\log n)$ steps holds for all $d,k=\{O}mega(\log\log n)$ in random $\maxdeg$-regular graphs a.a.s.\ and applies even to strategies which make use of some knowledge of the environment. {F}inally, we study oblivious strategies which do not use any memory (in particular, with no timer). {S}uch strategies are essentially a form of a random walk, possibly biased by local advice. {W}e show that such biased random walks sometimes achieve drastically worse performance than the \algo{{R}/{A}} strategy. {I}n particular, on the ring, no biased random walk can have a searching time which is polynomial in $d$ and $k$},
language = {{A}nglais},
affiliation = {{L}aboratoire {B}ordelais de {R}echerche en {I}nformatique - {L}a{BRI} - {CNRS} : {UMR}5800 - {U}niversit{\'e} {S}ciences et {T}echnologies - {B}ordeaux {I} - {E}cole {N}ationale {S}up{\'e}rieure d'{E}lectronique, {I}nformatique et {R}adiocommunications de {B}ordeaux - {U}niversit{\'e} {V}ictor {S}egalen - {B}ordeaux {II} - {CEPAGE} - {INRIA} {B}ordeaux - {S}ud-{O}uest - {INRIA} - {CNRS} : {UMR}5800 - {U}niversit{\'e} {S}ciences et {T}echnologies - {B}ordeaux {I} - {ENSEIRB} - {D}epartment of {A}lgorithms and {S}ystem {M}odeling - {G}dansk {U}niversity of {T}echnology - {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 },
x-pays = {PL},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
sorte = "conf-int",
}
-
F. Havet and L. Sampaio.
On the Grundy number of a graph.
In Proceedings of the International Symposium on Parameterized and Exact Computation(IPEC),
number 6478 of Lecture Notes on Computer science,
pages 170-179,
December 2010.
[PDF
]
| Abstract: |
The Grundy number of a graph $G$, denoted by $\Gamma (G)$, is the largest $k$ such that $G$ has a greedy $k$-colouring, that is a colouring with $k$ colours obtained by applying the greedy algorithm according to some ordering of the vertices of $G$. Trivially $\Gamma(G)\leq \Delta(G)+1$. In this paper, we show that deciding if $\Gamma(G)\leq \Delta(G)$ is NP-complete. We then show that deciding if $\Gamma(G)\geq |V(G)|-k$ is fixed parameter tractable with respect to the parameter $k$. |
@inproceedings{HaSa10,
author = {F. Havet and L. Sampaio},
title = {On the Grundy number of a graph},
booktitle = {Proceedings of the International Symposium on Parameterized and Exact Computation(IPEC)},
number = {6478},
series = {Lecture Notes on Computer science},
pages = {170-179},
year = {2010},
month = dec,
abstract = {The Grundy number of a graph $G$, denoted by $\Gamma (G)$, is the largest $k$ such that $G$ has a greedy $k$-colouring, that is a colouring with $k$ colours obtained by applying the greedy algorithm according to some ordering of the vertices of $G$. Trivially $\Gamma(G)\leq \Delta(G)+1$. In this paper, we show that deciding if $\Gamma(G)\leq \Delta(G)$ is NP-complete. We then show that deciding if $\Gamma(G)\geq |V(G)|-k$ is fixed parameter tractable with respect to the parameter $k$.},
pdf = {ftp://ftp-sop.inria.fr/mascotte/Publications/HaSa10.pdf},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
x-pays = {BR},
sorte = "conf-int",
}
-
L. Hogie,
D. Papadimitriou,
I. Tahiri,
and F. Majorczyk.
Simulating routing schemes on large-scale topologies.
In 24th ACM/IEEE/SCS Workshop on Principles of Advanced and Distributed Simulation (PADS),
Atlanta,
pages 8p,
May 2010.
| Abstract: |
The expansion of the Internet routing system results in a number of research challenges, in particular, the Border Gateway Protocol (BGP) starts to show its limits a.o. in terms of the number of routing table entries it can dynamically process and control. Dynamic routing protocols showing better scaling properties are thus under investigation. However, because deploying under-development routing protocols on the Internet is not practicable at a large-scale (due to the size of the Internet topology), simulation is an unavoidable step to validate the properties of a newly proposed routing scheme. Unfortunately, the simulation of inter-domain routing protocols over large networks (order of tens of thousands of nodes) poses real challenges due to the limited memory and computational power that computers impose. This paper presents the Dynamic Routing Model simulator \drmsim which addresses the specific problem of large-scale simulations of (inter-domain) routing models on large networks. The motivation for developing a new simulator lies in the limitation of existing simulation tools in terms of the number of nodes they can handle and in the models they propose. |
@inproceedings{HPT+10,
author = {L. Hogie and D. Papadimitriou and I. Tahiri and F. Majorczyk},
title = {Simulating routing schemes on large-scale topologies},
booktitle = {24th ACM/IEEE/SCS Workshop on Principles of Advanced and Distributed Simulation (PADS)},
pages = {8p},
year = {2010},
address = {Atlanta},
month = {May},
abstract = {The expansion of the Internet routing system results in a number of research challenges, in particular, the Border Gateway Protocol (BGP) starts to show its limits a.o. in terms of the number of routing table entries it can dynamically process and control. Dynamic routing protocols showing better scaling properties are thus under investigation. However, because deploying under-development routing protocols on the Internet is not practicable at a large-scale (due to the size of the Internet topology), simulation is an unavoidable step to validate the properties of a newly proposed routing scheme. Unfortunately, the simulation of inter-domain routing protocols over large networks (order of tens of thousands of nodes) poses real challenges due to the limited memory and computational power that computers impose. This paper presents the Dynamic Routing Model simulator \drmsim which addresses the specific problem of large-scale simulations of (inter-domain) routing models on large networks. The motivation for developing a new simulator lies in the limitation of existing simulation tools in terms of the number of nodes they can handle and in the models they propose.},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
sorte = "conf-int",
}
-
B. Jaumard,
N.N. Bhuiyan,
S. Sebbah,
F. Huc,
and D. Coudert.
A New Framework for Efficient Shared Segment Protection Scheme for WDM Networks.
In IEEE High Performance Switching and Routing (HPSR),
Richardson, TX, USA,
pages 8p,
June 2010.
IEEE.
[WWW
] [PDF
]
| Abstract: |
This work introduces a new shared segment protection scheme that ensures both node and link protection in an efficient manner in terms of cost and bandwidth, while taking full advantage of the optical hop endpoints of the primary logical hops (induced by the routing) without adding extra ones for protection. As opposed to the link or path protection schemes, the segment protection scheme has been less studied although it offers an interesting compromise between those two protection schemes, attempting to encompass all their advantages.
We investigate two different Shared Segment Protection (SSP) schemes: Basic Shared Segment Protection (BSSP) and Shared Segment Protection with segment Overlap (SSPO), and propose a design of 100\¸F÷¿Põ È!
ingle segment protections. In SSPO, we study the extra protection capabilities, node failure and dual link failure survivability, offered by the single 100\é2ingle segment protection.
For both BSSP and SSPO schemes, we propose two novel efficient ILP formulations, based on a column generation mathematical modeling. While (SSPO) offers the advantage over (BSSP) to ensure both node and link protection, it is not necessarily much more costly. Indeed, depending on the network topology and the traffic instances, it can be shown that none of the two SSP schemes dominates the other one. Therefore, the SSPO protection scheme should be favored as it offers more protection, i.e., it adds the node protection to the link protection at the expense of a minor additional cost. |
@inproceedings{JBS+10a,
author = {B. Jaumard and N.N. Bhuiyan and S. Sebbah and F. Huc and D. Coudert},
title = {A New Framework for Efficient Shared Segment Protection Scheme for {WDM} Networks},
booktitle = {IEEE High Performance Switching and Routing (HPSR)},
pages = {8p},
year = {2010},
address = {Richardson, TX, USA},
month = jun,
publisher = {IEEE},
pdf = {ftp://ftp-sop.inria.fr/mascotte/Publications/JBS+10a.pdf},
url = {http://dx.doi.org/10.1109/HPSR.2010.5580274},
abstract = { This work introduces a new shared segment protection scheme that ensures both node and link protection in an efficient manner in terms of cost and bandwidth, while taking full advantage of the optical hop endpoints of the primary logical hops (induced by the routing) without adding extra ones for protection. As opposed to the link or path protection schemes, the segment protection scheme has been less studied although it offers an interesting compromise between those two protection schemes, attempting to encompass all their advantages.
We investigate two different Shared Segment Protection (SSP) schemes: Basic Shared Segment Protection (BSSP) and Shared Segment Protection with segment Overlap (SSPO), and propose a design of 100\¸F÷¿ÂPõ È!
ingle segment protections. In SSPO, we study the extra protection capabilities, node failure and dual link failure survivability, offered by the single 100\é2ingle segment protection.
For both BSSP and SSPO schemes, we propose two novel efficient ILP formulations, based on a column generation mathematical modeling. While (SSPO) offers the advantage over (BSSP) to ensure both node and link protection, it is not necessarily much more costly. Indeed, depending on the network topology and the traffic instances, it can be shown that none of the two SSP schemes dominates the other one. Therefore, the SSPO protection scheme should be favored as it offers more protection, i.e., it adds the node protection to the link protection at the expense of a minor additional cost. },
OPTx-editorial-board={yes},
OPTx-proceedings={no},
OPTx-international-audience={yes},
sorte = "conf-int",
}
-
B. Jaumard,
N.N. Bhuiyan,
S. Sebbah,
F. Huc,
and D. Coudert.
A New Framework for Efficient Shared Segment Protection Scheme for WDM Networks.
In 10th INFORMS Telecommunications Conference,
Montréal, Canada,
pages 2p,
May 2010.
Informs.
[WWW
]
| Abstract: |
This work introduces a new shared segment protection scheme that ensures both node and link protection in an efficient manner in terms of cost and bandwidth, while taking full advantage of the optical hop endpoints of the primary logical hops (induced by the routing) without adding extra ones for protection. As opposed to the link or path protection schemes, the segment protection scheme has been less studied although it offers an interesting compromise between those two protection schemes, attempting to encompass all their advantages. We investigate two different Shared Segment Protection (SSP) schemes: Basic Shared Segment Protection (BSSP) and Shared Segment Protection with segment Overlap (SSPO), and propose a design of 100\¸F÷¿Põ (!
ingle segment protections. In SSPO, we study the extra protection capabilities, node failure and dual link failure survivability, offered by the single 100\é2ingle segment protection.
For both BSSP and SSPO schemes, we propose two novel efficient ILP formulations, based on a column generation mathematical modeling. While (SSPO) offers the advantage over (BSSP) to ensure both node and link protection, it is not necessarily much more costly. Indeed, depending on the network topology and the traffic instances, it can be shown that none of the two SSP schemes dominates the other one. Therefore, the SSPO protection scheme should be favored as it offers more protection, i.e., it adds the node protection to the link protection at the expense of a minor additional cost. |
@inproceedings{JBS+10b,
author = {B. Jaumard and N.N. Bhuiyan and S. Sebbah and F. Huc and D. Coudert},
title = {A New Framework for Efficient Shared Segment Protection Scheme for {WDM} Networks},
booktitle = {10th INFORMS Telecommunications Conference},
pages = {2p},
year = {2010},
address = {Montr\'eal, Canada},
month = may,
organization = {Informs},
url = {https://symposia.cirrelt.ca/Informs-Telecom2010/},
pdf = {},
abstract = { This work introduces a new shared segment protection scheme that ensures both node and link protection in an efficient manner in terms of cost and bandwidth, while taking full advantage of the optical hop endpoints of the primary logical hops (induced by the routing) without adding extra ones for protection. As opposed to the link or path protection schemes, the segment protection scheme has been less studied although it offers an interesting compromise between those two protection schemes, attempting to encompass all their advantages. We investigate two different Shared Segment Protection (SSP) schemes: Basic Shared Segment Protection (BSSP) and Shared Segment Protection with segment Overlap (SSPO), and propose a design of 100\¸F÷¿ÂPõ (!
ingle segment protections. In SSPO, we study the extra protection capabilities, node failure and dual link failure survivability, offered by the single 100\é2ingle segment protection.
For both BSSP and SSPO schemes, we propose two novel efficient ILP formulations, based on a column generation mathematical modeling. While (SSPO) offers the advantage over (BSSP) to ensure both node and link protection, it is not necessarily much more costly. Indeed, depending on the network topology and the traffic instances, it can be shown that none of the two SSP schemes dominates the other one. Therefore, the SSPO protection scheme should be favored as it offers more protection, i.e., it adds the node protection to the link protection at the expense of a minor additional cost. },
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
sorte = "conf-int",
}
-
G. B. Mertzios,
I. Sau,
and S. Zaks.
The Recognition of Tolerance and Bounded Tolerance Graphs.
In Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science (STACS),
volume 5 of LIPIcs,
pages 585-596,
2010.
Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik.
[WWW
] [PDF
]
| Abstract: |
Tolerance graphs model interval relations in such a way that intervals can tolerate a certain degree of overlap without being in conflict. This subclass of perfect graphs has been extensively studied, due to both its interesting structure and its numerous applications. Several efficient algorithms for optimization problems that are NP-hard on general graphs have been designed for tolerance graphs. In spite of this, the recognition of tolerance graphs --~namely, the problem of deciding whether a given graph is a tolerance graph~-- as well as the recognition of their main subclass of bounded tolerance graphs, have been the most fundamental open problems on this class of graphs (cf.~the book on tolerance graphs~\cite{GolTol04}) since their introduction in 1982~\cite{GoMo82}. In this article we prove that both recognition problems are NP-complete, even in the case where the input graph is a trapezoid graph. The presented results are surprising because, on the one hand, most subclasses of perfect graphs admit polynomial recognition algorithms and, on the other hand, bounded tolerance graphs were believed to be efficiently recognizable as they are a natural special case of trapezoid graphs (which can be recognized in polynomial time) and share a very similar structure with them. For our reduction we extend the notion of an \emph{acyclic orientation} of permutation and trapezoid graphs. Our main tool is a new algorithm that uses \emph{vertex splitting} to transform a given trapezoid graph into a permutation graph, while preserving this new acyclic orientation property. This method of vertex splitting is of independent interest; very recently, it has been proved a powerful tool also in the design of efficient recognition algorithms for other classes of graphs~\cite{MC-Trapezoid}. |
@inproceedings{MSZ10b,
author = {G. B. Mertzios and I. Sau and S. Zaks},
title = {{The Recognition of Tolerance and Bounded Tolerance Graphs}},
abstract = {Tolerance graphs model interval relations in such a way that intervals can tolerate a certain degree of overlap without being in conflict. This subclass of perfect graphs has been extensively studied, due to both its interesting structure and its numerous applications. Several efficient algorithms for optimization problems that are NP-hard on general graphs have been designed for tolerance graphs. In spite of this, the recognition of tolerance graphs --~namely, the problem of deciding whether a given graph is a tolerance graph~-- as well as the recognition of their main subclass of bounded tolerance graphs, have been the most fundamental open problems on this class of graphs (cf.~the book on tolerance graphs~\cite{GolTol04}) since their introduction in 1982~\cite{GoMo82}. In this article we prove that both recognition problems are NP-complete, even in the case where the input graph is a trapezoid graph. The presented results are surprising because, on the one hand, most subclasses of perfect graphs admit polynomial recognition algorithms and, on the other hand, bounded tolerance graphs were believed to be efficiently recognizable as they are a natural special case of trapezoid graphs (which can be recognized in polynomial time) and share a very similar structure with them. For our reduction we extend the notion of an \emph{acyclic orientation} of permutation and trapezoid graphs. Our main tool is a new algorithm that uses \emph{vertex splitting} to transform a given trapezoid graph into a permutation graph, while preserving this new acyclic orientation property. This method of vertex splitting is of independent interest; very recently, it has been proved a powerful tool also in the design of efficient recognition algorithms for other classes of graphs~\cite{MC-Trapezoid}.},
BOOKTITLE = {Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science (STACS)},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik},
series = {LIPIcs},
volume = {5},
pages = {585-596},
year = {2010},
isbn = {978-3-939897-16-3},
url = {http://dx.doi.org/10.4230/LIPIcs.STACS.2010.2487},
pdf = {ftp://ftp-sop.inria.fr/mascotte/Publications/MSZ10b.pdf},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
sorte = "conf-int",
}
-
J. Monteiro and S. Pérennes.
Systèmes de stockage P2P : un guide pratique.
In 11es Journées Doctorales en Informatique et Réseaux (JDIR 2010),
Sophia Antipolis France,
pages 15--20,
2010.
[WWW
]
| Abstract: |
{L}es syst{\`e}mes pair-{\`a}-pair {\`a} grande {\'e}chelle ont {\'e}t{\'e} propos{\'e} comme un moyen fiable d'assurer un stockage de donn{\'e}e {\`a} faible c{\^o}ut. {P}our assurer la p{\'e}rennit{\'e} des donn{\'e}es, ces syst{\`e}mes codent les fichiers des utilisateurs en un ensemble de fragments redondants qui sont répartis entre les pairs. {N}ous étudions dans ce rapport l'impact des différents param{\`e}tres de configuration du syst{\`e}me, comme par exemple, le facteur de redondance et la fr{\'e}quence de r{\'e}paration des donn{\'e}es. {P}lus particulièrement, dans ce papier nous derivons des formules approch{\'e}es {\`a} partir d'une chaine de {M}arkov. {C}es formules nous donnent une estimation de la bande passante n{\'e}cessaire pour maintenir la redondance et de la probabilit{\'e} de perdre un bloc de donn{\'e}e. |
@inproceedings{MoPe10,
title = { {S}yst{\`e}mes de stockage {P}2{P} : un guide pratique},
author = {Monteiro, J. and P\'erennes, S.},
abstract = {{L}es syst{\`e}mes pair-{\`a}-pair {\`a} grande {\'e}chelle ont {\'e}t{\'e} propos{\'e} comme un moyen fiable d'assurer un stockage de donn{\'e}e {\`a} faible c{\^o}ut. {P}our assurer la p{\'e}rennit{\'e} des donn{\'e}es, ces syst{\`e}mes codent les fichiers des utilisateurs en un ensemble de fragments redondants qui sont répartis entre les pairs. {N}ous étudions dans ce rapport l'impact des différents param{\`e}tres de configuration du syst{\`e}me, comme par exemple, le facteur de redondance et la fr{\'e}quence de r{\'e}paration des donn{\'e}es. {P}lus particulièrement, dans ce papier nous derivons des formules approch{\'e}es {\`a} partir d'une chaine de {M}arkov. {C}es formules nous donnent une estimation de la bande passante n{\'e}cessaire pour maintenir la redondance et de la probabilit{\'e} de perdre un bloc de donn{\'e}e.},
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 },
booktitle = {11es Journ\'{e}es Doctorales en Informatique et R\'{e}seaux (JDIR 2010)},
address = {{S}ophia {A}ntipolis {F}rance },
URL = {http://hal.inria.fr/inria-00483214/en/},
year = {2010},
pages={15--20},
x-pays={FR},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
sorte = "conf-nat",
}
-
N. Nisse.
Graph Searching and Graph Decompositions.
In 24th European Conference on Operational Research (EURO),
Lisbon, Portugal,
pages 1p,
July 2010.
Note: Invited talk.
[WWW
]
| Abstract: |
Graph searching is a game where a team of mobile agents must catch a fugitive hidden in a network (modelled by a graph). Equivalently, graph search- ing may be defined in terms of clearing a contaminated network. Besides of its practical interests, graph searching has been widely studied for its relationship with important graph parameters, in particular pathwidth and treewidth. Many versions of graph searching problems have been considered. They all look for a strategy that allows to catch the fugitive using the minimum number of agents. Variants of graph searching differ on various parameters. We first give a brief survey of the numerous research directions in this field. Then, we focus on the relationship between search games and graph decompositions (path- and tree- decompositions). Namely, search games provide a very interesting algorithmic interpretation of the pathwidth and the treewidth of graphs. we explain the equivalence between theses games and graph decompositions through an impor- tant property of these two search games: the monotonicity. This point of view allowed us to obtain new duality results generalyzing those obtained by Robert- son and Seymour in the Graph Minors Theory |
@inproceedings{Nis10,
author = {N. Nisse},
title = {Graph Searching and Graph Decompositions},
OPTcrossref = {},
OPTkey = {},
booktitle = {24th European Conference on Operational Research (EURO)},
pages = {1p},
year = {2010},
OPTeditor = {},
OPTvolume = {},
OPTnumber = {},
OPTseries = {},
address = {Lisbon, Portugal},
month = jul,
OPTorganization = {},
OPTpublisher = {},
note = {Invited talk},
OPTannote = {},
url = {http://hal.inria.fr/inria-00482115},
abstract = {Graph searching is a game where a team of mobile agents must catch a fugitive hidden in a network (modelled by a graph). Equivalently, graph search- ing may be defined in terms of clearing a contaminated network. Besides of its practical interests, graph searching has been widely studied for its relationship with important graph parameters, in particular pathwidth and treewidth. Many versions of graph searching problems have been considered. They all look for a strategy that allows to catch the fugitive using the minimum number of agents. Variants of graph searching differ on various parameters. We first give a brief survey of the numerous research directions in this field. Then, we focus on the relationship between search games and graph decompositions (path- and tree- decompositions). Namely, search games provide a very interesting algorithmic interpretation of the pathwidth and the treewidth of graphs. we explain the equivalence between theses games and graph decompositions through an impor- tant property of these two search games: the monotonicity. This point of view allowed us to obtain new duality results generalyzing those obtained by Robert- son and Seymour in the Graph Minors Theory},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
sorte = "inv-conf",
}
-
J. Ribault,
O. Dalle,
D. Conan,
and S. Leriche.
OSIF: A Framework To Instrument, Validate, and Analyze Simulations.
In In Proc. of 3rd Intl. ICST Conference on Simulation Tools and Techniques (SIMUTools'2010),
Torremolinos, Spain,
15-19 March 2010.
[WWW
]
| Abstract: |
{I}n most existing simulators, the outputs of a simulation run consist either in a simulat ion report generated at the end of the run and summarizing the statistics of interest, or in a (set of) trace file(s) containing raw data samples produced and saved regularly during the run, for later post-processing. {I}n this paper, we address issues related to the management of these data and their on-line processing, such as: (i)~the instrumentation code is mixed in the modeling code; (ii)~the amount of data to be stored may be enormous, and often, a significant part of these data are useless while their collect may consume a significant amount of the computing resources; and (iii)~it is difficult to have confidence in the treatment applied to the data and then make comparisons between studies since each user (model developer) builds its own ad-hoc instrumentation and data processing. {I}n this paper, we propose {OSIF}, a new component-based instrumentation framework designed to solve the above mentioned issues. {OSIF} is based on several mature software engineering techniques and frameworks, such as {COSMOS}, {F}ractal and its {ADL}, and {AOP}. |
@inproceedings{RDD+10,
title = { {OSIF}: {A} {F}ramework {T}o {I}nstrument, {V}alidate, and {A}nalyze {S}imulations},
author = {J. Ribault and O. Dalle and D. Conan and S. Leriche},
abstract = {{I}n most existing simulators, the outputs of a simulation run consist either in a simulat ion report generated at the end of the run and summarizing the statistics of interest, or in a (set of) trace file(s) containing raw data samples produced and saved regularly during the run, for later post-processing. {I}n this paper, we address issues related to the management of these data and their on-line processing, such as: (i)~the instrumentation code is mixed in the modeling code; (ii)~the amount of data to be stored may be enormous, and often, a significant part of these data are useless while their collect may consume a significant amount of the computing resources; and (iii)~it is difficult to have confidence in the treatment applied to the data and then make comparisons between studies since each user (model developer) builds its own ad-hoc instrumentation and data processing. {I}n this paper, we propose {OSIF}, a new component-based instrumentation framework designed to solve the above mentioned issues. {OSIF} is based on several mature software engineering techniques and frameworks, such as {COSMOS}, {F}ractal and its {ADL}, and {AOP}.},
language = {English},
booktitle = {In Proc. of 3rd Intl. ICST Conference on Simulation Tools and Techniques (SIMUTools'2010)},
address = {Torremolinos, Spain},
audience = {internationale },
month = {15-19 March},
year = {2010},
URL = {http://hal.inria.fr/inria-00465141/en/},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
sorte = "conf-int",
}
-
P. Uribe,
J-C. Maureira Bravo,
and O. Dalle.
Extending INET Framework for Directional and Asymmetrical Wireless Communications.
In Proc. of the 2010 Intl. ICST Workshop on OMNeT++ (OMNeT++ 2010),
Torremolinos, Spain,
pages 1--8,
15-19 March 2010.
@inproceedings{UMD10a,
author = {P. Uribe and J-C. {Maureira Bravo} and O. Dalle},
title = {Extending INET Framework for Directional and Asymmetrical Wireless Communications},
booktitle = {Proc. of the 2010 Intl. ICST Workshop on {OMNeT}++ ({OMNeT}++ 2010)},
year = {2010},
pages = {1--8},
month = {15-19 March},
address = {Torremolinos, Spain},
isbn = {78-963-9799-87-5},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
sorte = "conf-int",
}
-
J. Bang-Jensen,
F. Havet,
and N. Trotignon.
Finding an induced subdivision of a digraph.
Research Report 7430,
INRIA,
10 2010.
[WWW
] [PDF
]
| 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. |
@techReport{BHT10,
author = {J. Bang-Jensen and F. Havet and N. Trotignon},
title = {Finding an induced subdivision of a digraph},
year = {2010},
month = {10},
institution = {INRIA},
number = {7430},
type = {Research Report},
URL={http://hal.inria.fr/inria-00527518/fr/},
PDF = {http://hal.inria.fr/docs/00/52/75/18/PDF/RR-7430.pdf},
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.},
x-editorial-board={yes},
x-proceedings={yes},
x-international-audience={yes},
x-pays={DK},
}
-
L. Barrière,
P. Flocchini,
F. V. Fomin,
P. Fraigniaud,
N. Nisse,
N. Santoro,
and D. Thilikos.
Connected Graph Searching.
Research Report 7363,
INRIA,
August 2010.
[WWW
] [PDF
]
| Abstract: |
In graph searching game the opponents are a set of searchers and a fugitive in a graph. The searchers try to capture the fugitive by applying some sequence moves that include placement, removal, or sliding of a searcher along an edge. The fugitive tries to avoid capture by moving along unguarded paths. The search number of a graph is the minimum number of searchers required to guarantee the capture of the fugitive. In this paper, we initiate the study of this game under the natural restriction of connectivity where we demand that in each step of the search the locations of the graph that are clean (i.e. non-accessible to the fugitive) remain connected. We give evidence that many of the standard mathematical tools used so far in the classic graph searching fail under the connectivity requirement. We also settle the question on ``the price of connectivity'' that is how many searchers more are required for searching a graph when the connectivity demand is imposed. We make estimations of the price of
connectivity on general graphs and we provide tight bounds for the case of trees. In particular, for an $n$-vertex graph the ratio between the connected searching number and the non-connected one is $O(\log n)$ while for trees this ratio is always at most 2. We also conjecture that this constant-ratio upper bound for trees holds also for all graphs. Our combinatorial results imply a complete characterization of connected graph searching on trees. It is based on a forbidden-graph characterization of the connected search number. We prove that the connected search game is monotone for trees, i.e. restricting search strategies to only those where the clean territories increase monotonically does not require more searchers. A consequence of our results is that the connected search number can be computed in polynomial time on trees, moreover, we show how to make this algorithm distributed. Finally, we reveal connections of this parameter to other invariants on trees such as the Horton-Stralher number. |
@techreport{BFF+10,
author = {{B}arri{\`e}re, L. and {F}locchini, P. and {F}omin, F. {V}. and {F}raigniaud, P. and {N}isse, N. and {S}antoro, N. and {T}hilikos, D.},
title = {{C}onnected {G}raph {S}earching},
institution = {INRIA},
type = {Research Report},
number = {7363},
year = {2010},
month = aug,
x-pays={ES,CA,NO,GR},
url = {http://hal.inria.fr/inria-00508888},
pdf = {http://hal.inria.fr/docs/00/50/88/88/PDF/RR-7363.pdf},
abstract = {In graph searching game the opponents are a set of searchers and a fugitive in a graph. The searchers try to capture the fugitive by applying some sequence moves that include placement, removal, or sliding of a searcher along an edge. The fugitive tries to avoid capture by moving along unguarded paths. The search number of a graph is the minimum number of searchers required to guarantee the capture of the fugitive. In this paper, we initiate the study of this game under the natural restriction of connectivity where we demand that in each step of the search the locations of the graph that are clean (i.e. non-accessible to the fugitive) remain connected. We give evidence that many of the standard mathematical tools used so far in the classic graph searching fail under the connectivity requirement. We also settle the question on ``the price of connectivity'' that is how many searchers more are required for searching a graph when the connectivity demand is imposed. We make estimations of the price of
connectivity on general graphs and we provide tight bounds for the case of trees. In particular, for an $n$-vertex graph the ratio between the connected searching number and the non-connected one is $O(\log n)$ while for trees this ratio is always at most 2. We also conjecture that this constant-ratio upper bound for trees holds also for all graphs. Our combinatorial results imply a complete characterization of connected graph searching on trees. It is based on a forbidden-graph characterization of the connected search number. We prove that the connected search game is monotone for trees, i.e. restricting search strategies to only those where the clean territories increase monotonically does not require more searchers. A consequence of our results is that the connected search number can be computed in polynomial time on trees, moreover, we show how to make this algorithm distributed. Finally, we reveal connections of this parameter to other invariants on trees such as the Horton-Stralher number.},
}
-
F. Becker,
M. Matamala,
N. Nisse,
I. Rapaport,
K. Suchan,
and I. Todinca.
Adding a referee to an interconnection network: What can(not) be computed in one round.
Research Report arXiv:1009.4447,
arXiv,
September 2010.
[WWW
] [PDF
]
| Abstract: |
{In this paper we ask which properties of a distributed network can be computed from a few 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. }, OPTx-editorial-board={yes}, OPTx-proceedings={no}, OPTx-international-audience={yes}, sorte = "Rapports", |
@techreport{BMN+10,
author = {F. Becker and M. Matamala and N. Nisse and I. Rapaport and K. Suchan and I. Todinca},
title = {Adding a referee to an interconnection network: What can(not) be computed in one round},
institution = {arXiv},
type = {Research Report},
number = {arXiv:1009.4447},
year = {2010},
month = sep,
x-pays={CL},
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 few 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. }, OPTx-editorial-board={yes}, OPTx-proceedings={no}, OPTx-international-audience={yes}, sorte = "Rapports",
}
-
J-C. Bermond,
F. Havet,
F. Huc,
and C. Linhares Sales.
Improper colouring of weighted grid and hexagonal graphs.
Research Report RR-7250,
INRIA,
April 2010.
[WWW
] [PDF
]
Keywords:
Improper colouring,
Weighted colouring,
Approximation algorithms.
| Abstract: |
{W}e study a weighted improper colouring problem on graph, and in particular of triangular and hexagonal grid graphs. {T}his problem is motivated by a frequency allocation problem. {W}e propose approximation algorithms to compute such colouring. |
@techreport{BHH+10,
title = { {I}mproper colouring of weighted grid and hexagonal graphs},
author = {Bermond, J-C. and Havet, F. and Huc, F. and Linhares Sales, C.},
abstract = {{W}e study a weighted improper colouring problem on graph, and in particular of triangular and hexagonal grid graphs. {T}his problem is motivated by a frequency allocation problem. {W}e propose approximation algorithms to compute such colouring.},
keywords = {{I}mproper colouring, {W}eighted colouring, {A}pproximation 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 - {C}entre {U}niversitaire d'{I}nformatique - {U}niversit{\'e} de {G}en{\`e}ve - {L}aborat{\'o}rios de {P}esqu{I}sa em {C}omputao - {LIA} - {U}niversite {F}ederale du {C}eara },
pages = {19 },
type = {Research Report},
institution = {INRIA},
number = {{RR}-7250},
collaboration = {{U}niversite de {G}eneve, {TCS} {S}ensor{L}ab },
day = {13},
month = {apr},
year = {2010},
URL = {http://hal.inria.fr/inria-00472819/en/},
PDF = {http://hal.inria.fr/inria-00472819/PDF/RR-7250.pdf},
OPTx-editorial-board={yes},
OPTx-proceedings={no},
OPTx-international-audience={yes},
x-pays = {BR},
sorte = "Rapports",
}
-
V. Campos,
A. Gyárfás,
F. Havet,
C. Linhares Sales,
and F. Maffray.
New bounds on the Grundy number of products of graphs.
Research Report 7243,
INRIA,
April 2010.
[WWW
] [PDF
]
| Abstract: |
The Grundy number of a graph $G$ is the largest $k$ such that $G$ has a greedy $k$-colouring, that is, a colouring with $k$ colours obtained by applying the greedy algorithm according to some ordering of the vertices of $G$. In this paper, we give new bounds on the Grundy number of the product of two graphs. |
@techreport{CGH+10,
author = {Campos, V. and Gy\'arf\'as, A. and Havet, F. and Linhares Sales, C. and Maffray, F.},
title = {New bounds on the Grundy number of products of graphs},
year = {2010},
month = apr,
institution = {INRIA},
number = {7243},
type = {Research Report},
url = {http://hal.archives-ouvertes.fr/inria-00470158/fr/},
pdf = {http://hal.archives-ouvertes.fr/docs/00/47/01/58/PDF/RR-7243.pdf },
abstract = { The Grundy number of a graph $G$ is the largest $k$ such that $G$ has a greedy $k$-colouring, that is, a colouring with $k$ colours obtained by applying the greedy algorithm according to some ordering of the vertices of $G$. In this paper, we give new bounds on the Grundy number of the product of two graphs.},
x-editorial-board={yes},
x-proceedings={yes},
x-international-audience={yes},
x-pays={BR, HU},
sorte = "Rapports",
}
-
S. Caron,
F. Giroire,
D. Mazauric,
J. Monteiro,
and S. Pérennes.
P2P Storage Systems: Data Life Time for Different Placement Policies.
Research Report RR-7209,
INRIA,
February 2010.
[WWW
] [PDF
]
Keywords:
P2P storage system,
data placement,
data life time,
mean time to data loss,
performance evaluation,
Markov chains.
| Abstract: |
{P}eer-to-peer systems are foreseen as an efficient solution to achieve reliable data storage at low cost. {T}o deal with common {P}2{P} problems such as peer failures or churn, such systems encode the user data into redundant fragments and distribute them among peers. {T}he way they distribute it, known as placement policy, has a significant impact on their behavior and reliability. {I}n this report, after a brief state-of-the-art of the technology used in {P}2{P} storage systems, we compare three different placement policies: two of them local, in which the data is stored in logical peer neighborhoods, and on of them global in which fragments are parted at random among the different peers. {F}or each policy, we give either {M}arkov {C}hain {M}odels to efficiently compute the {M}ean {T}ime {T}o {D}ata {L}oss (which is closely related to the probability to lose data) or approximations of this quantity under certain assumptions. {W}e also attempt to give lower bounds on {P}2{P} storage systems introducing the {BIG} system, in which we consider information globally. {W}e propose various ways to compute a bound on the probability to lose data, in relation with parameters such as the peer failure rate of the peer bandwidth. |
@techreport{CGM+10a,
title = {{P}2{P} {S}torage {S}ystems: {D}ata {L}ife {T}ime for {D}ifferent {P}lacement {P}olicies},
author = {Caron, S. and Giroire, F. and Mazauric, D. and Monteiro, J. and P\'erennes, S.},
abstract = {{P}eer-to-peer systems are foreseen as an efficient solution to achieve reliable data storage at low cost. {T}o deal with common {P}2{P} problems such as peer failures or churn, such systems encode the user data into redundant fragments and distribute them among peers. {T}he way they distribute it, known as placement policy, has a significant impact on their behavior and reliability. {I}n this report, after a brief state-of-the-art of the technology used in {P}2{P} storage systems, we compare three different placement policies: two of them local, in which the data is stored in logical peer neighborhoods, and on of them global in which fragments are parted at random among the different peers. {F}or each policy, we give either {M}arkov {C}hain {M}odels to efficiently compute the {M}ean {T}ime {T}o {D}ata {L}oss (which is closely related to the probability to lose data) or approximations of this quantity under certain assumptions. {W}e also attempt to give lower bounds on {P}2{P} storage systems introducing the {BIG} system, in which we consider information globally. {W}e propose various ways to compute a bound on the probability to lose data, in relation with parameters such as the peer failure rate of the peer bandwidth.},
keywords = {{P}2{P} storage system; data placement; data life time; mean time to data loss; performance evaluation;{M}arkov chains},
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 - {MAESTRO} - {INRIA} {S}ophia {A}ntipolis - {INRIA} - {U}niversit{\'e} {M}ontpellier {II} - {S}ciences et {T}echniques du {L}anguedoc },
type = {Research Report},
institution = {INRIA},
number = {{RR}-7209},
day = {19},
month = feb,
year = {2010},
URL = {http://hal.inria.fr/inria-00458190/en/},
PDF = {http://hal.inria.fr/inria-00458190/PDF/RR-7209.pdf},
OPTx-editorial-board={yes},
OPTx-proceedings={no},
OPTx-international-audience={yes},
sorte = "Rapports",
}
-
J. Chalopin,
V. Chepoi,
N. Nisse,
and Y. Vaxès.
Cop and robber games when the robber can hide and ride..
Technical report INRIA-RR7178,
INRIA,
January 2010.
[WWW
] [PDF
]
| Abstract: |
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. |
@techreport{CCN+10a,
author = {J. Chalopin and V. Chepoi and N. Nisse and Y. Vax\`es},
title = {Cop and robber games when the robber can hide and ride.},
institution = {INRIA},
number = {INRIA-RR7178},
year = {2010},
month = jan,
url = {http://hal.archives-ouvertes.fr/inria-00448243/fr/},
pdf = {http://hal.archives-ouvertes.fr/docs/00/44/82/43/PDF/RR-7178.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.},
OPTx-editorial-board={yes},
OPTx-proceedings={no},
OPTx-international-audience={yes},
sorte = "Rapports",
}
-
N. Cohen and F. Havet.
Linear and 2-frugal choosability of graphs of small maximum average degree.
Research Report RR-7213,
INRIA,
02 2010.
[WWW
]
| 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})$. {I}f ${G}$ is 2-frugally (resp. linearly) ${L}$-list colourable for any list assignment such that $|{L}(v)|\ge k$ for all $v\in{V}({G})$, then ${G}$ is {\it 2-frugally} (resp. {\it linearly}) {\it $k$-choosable}. {I}n this paper, we improve some bounds on the 2-frugal choosability and linear choosability of graphs with small maximum average degree. |
@techreport{CoHa10b,
url = {http://hal.inria.fr/inria-00459692/en/},
title = { {L}inear and 2-frugal choosability of graphs of small maximum average degree},
author = {N. Cohen and F. Havet},
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})$. {I}f ${G}$ is 2-frugally (resp. linearly) ${L}$-list colourable for any list assignment such that $|{L}(v)|\ge k$ for all $v\in{V}({G})$, then ${G}$ is {\it 2-frugally} (resp. {\it linearly}) {\it $k$-choosable}. {I}n this paper, we improve some bounds on the 2-frugal choosability and linear choosability of graphs with small maximum average degree.},
language = {{E}nglish},
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 },
type = {{R}esearch {R}eport},
institution = {INRIA},
number = {{RR}-7213},
day = {24},
month = {02},
year = {2010},
URL = {http://hal.inria.fr/inria-00459692/PDF/RR-7213.pdf},
OPTx-editorial-board={no},
OPTx-proceedings={no},
OPTx-international-audience={yes},
sorte = "Rapports",
}
-
F. Giroire,
D. Mazauric,
J. Moulierac,
and B. Onfroy.
Minimizing Routing Energy Consumption: from Theoretical to Practical Results.
Research Report inria-00464318,
May 2010.
[WWW
] [PDF
]
Keywords:
power consumption,
energy-efficient routing,
graphs,
linear programming.
| Abstract: |
{S}everal studies exhibit that the traffic load of the routers only has a small influence on their energy consumption. {H}ence, the power consumption in networks is strongly related to the number of active network elements, such as interfaces, line cards, base chassis,... {T}he goal thus is to find a routing that minimizes the (weighted) number of active network elements used when routing. {I}n this paper, we consider a simplified architecture where a connection between two routers is represented as a link joining two network equipments. {W}hen a connection is not used, both network equipments can be turned off. {T}herefore, in order to reduce power consumption, the goal is to find the routing that minimizes the number of used links while satisfying all the demands. {W}e first present a study on specific topologies, such as trees and complete graphs, that provide bounds and results useful for real topologies. {W}e model the problem as a linear program and propose a heuristic to solve large instances. {W}e exhibit the gain in terms of number of network equipments (leading to a global reduction of the power consumption) for a set of network topologies: we see that for almost all topologies more than one third of the network equipments can be spared for usual ranges of operation. {F}inally, we discuss the impact of energy efficient routing on the stretch factor and on fault tolerance. |
@techreport{GMM+10a,
URL = {http://hal.archives-ouvertes.fr/inria-00464318/en/},
title = { {M}inimizing {R}outing {E}nergy {C}onsumption: from Theoretical to Practical Results},
OPTauthor = {Giroire, Frédéric and Mazauric, Dorian and Moulierac, Joanna and Onfroy, Brice},
author = {Giroire, F. and Mazauric, D. and Moulierac, J. and Onfroy, B.},
month = may,
year = {2010},
type = {Research Report},
number = {inria-00464318},
abstract = {{S}everal studies exhibit that the traffic load of the routers only has a small influence on their energy consumption. {H}ence, the power consumption in networks is strongly related to the number of active network elements, such as interfaces, line cards, base chassis,... {T}he goal thus is to find a routing that minimizes the (weighted) number of active network elements used when routing. {I}n this paper, we consider a simplified architecture where a connection between two routers is represented as a link joining two network equipments. {W}hen a connection is not used, both network equipments can be turned off. {T}herefore, in order to reduce power consumption, the goal is to find the routing that minimizes the number of used links while satisfying all the demands. {W}e first present a study on specific topologies, such as trees and complete graphs, that provide bounds and results useful for real topologies. {W}e model the problem as a linear program and propose a heuristic to solve large instances. {W}e exhibit the gain in terms of number of network equipments (leading to a global reduction of the power consumption) for a set of network topologies: we see that for almost all topologies more than one third of the network equipments can be spared for usual ranges of operation. {F}inally, we discuss the impact of energy efficient routing on the stretch factor and on fault tolerance.},
keywords = {power consumption ; energy-efficient routing ; graphs ; linear programming},
language = {Anglais},
affiliation = {{MASCOTTE} - {INRIA} {S}ophia {A}ntipolis / {L}aboratoire {I}3{S} - {INRIA} - {U}niversité de {N}ice {S}ophia-{A}ntipolis - {CNRS} : {UMR}6070 },
pdf = {http://hal.archives-ouvertes.fr/inria-00464318/PDF/RR-7234.pdf},
OPTx-editorial-board={yes},
OPTx-proceedings={no},
OPTx-international-audience={yes},
sorte = "Rapports",
}
-
N. Hanusse,
D. Ilcinkas,
A. Kosowski,
and N. Nisse.
How to beat the random walk when you have a clock?.
Research Report RR-7210,
INRIA,
February 2010.
[WWW
] [PDF
]
| Abstract: |
{W}e study the problem of finding a destination node $t$ by a mobile agent in an unreliable network having the structure of an unweighted graph, in a model first proposed by {H}anusse {\it et al.}~\cite{{HKK}00,{HKKK}08}. {E}ach node of the network is able to give advice concerning the next node to visit so as to go closer to the target $t$. {U}nfortunately, exactly $k$ of the nodes, called \emph{liars}, give advice which is incorrect. {I}t is known that for an $n$-node graph ${G}$ of maximum degree $\{D}elta \geq 3$, reaching a target at a distance of $d$ from the initial location may require an expected time of $2^{\{O}mega(\min\{d,k\})}$, for any $d,k={O}(\log n)$, even when ${G}$ is a tree. {T}his paper focuses on strategies which efficiently solve the search problem in scenarios in which, at each node, the agent may only choose between following the local advice, or randomly selecting an incident edge. {T}he strategy which we put forward, called \algo{{R}/{A}}, makes use of a timer (step counter) to alternate between phases of ignoring advice (\algo{{R}}) and following advice (\algo{{A}}) for a certain number of steps. {N}o knowledge of parameters $n$, $d$, or $k$ is required, and the agent need not know by which edge it entered the node of its current location. {T}he performance of this strategy is studied for two classes of regular graphs with extremal values of expansion, namely, for rings and for random $\maxdeg$-regular graphs (an important class of expanders). {F}or the ring, \algo{{R}/{A}} is shown to achieve an expected searching time of $2d+k^{\{T}heta(1)}$ for a worst-case distribution of liars, which is polynomial in both $d$ and $k$. {F}or random $\maxdeg$-regular graphs, the expected searching time of the \algo{{R}/{A}} strategy is ${O}(k3 \log3 n)$ a.a.s. {T}he polylogarithmic factor with respect to $n$ cannot be dropped from this bound; in fact, we show that a lower time bound of $\{O}mega (\log n)$ steps holds for all $d,k=\{O}mega(\log\log n)$ in random $\maxdeg$-regular graphs a.a.s.\ and applies even to strategies which make use of some knowledge of the environment. {F}inally, we study oblivious strategies which do not use any memory (in particular, with no timer). {S}uch strategies are essentially a form of a random walk, possibly biased by local advice. {W}e show that such biased random walks sometimes achieve drastically worse performance than the \algo{{R}/{A}} strategy. {I}n particular, on the ring, no biased random walk can have a searching time which is polynomial in $d$ and $k$ |
@techreport{HIK+10a,
title = { {H}ow to beat the random walk when you have a clock?},
author = {Hanusse, {N}. and Ilcinkas, {D}. and Kosowski, {A}. and Nisse, N.},
abstract = {{W}e study the problem of finding a destination node $t$ by a mobile agent in an unreliable network having the structure of an unweighted graph, in a model first proposed by {H}anusse {\it et al.}~\cite{{HKK}00,{HKKK}08}. {E}ach node of the network is able to give advice concerning the next node to visit so as to go closer to the target $t$. {U}nfortunately, exactly $k$ of the nodes, called \emph{liars}, give advice which is incorrect. {I}t is known that for an $n$-node graph ${G}$ of maximum degree $\{D}elta \geq 3$, reaching a target at a distance of $d$ from the initial location may require an expected time of $2^{\{O}mega(\min\{d,k\})}$, for any $d,k={O}(\log n)$, even when ${G}$ is a tree. {T}his paper focuses on strategies which efficiently solve the search problem in scenarios in which, at each node, the agent may only choose between following the local advice, or randomly selecting an incident edge. {T}he strategy which we put forward, called \algo{{R}/{A}}, makes use of a timer (step counter) to alternate between phases of ignoring advice (\algo{{R}}) and following advice (\algo{{A}}) for a certain number of steps. {N}o knowledge of parameters $n$, $d$, or $k$ is required, and the agent need not know by which edge it entered the node of its current location. {T}he performance of this strategy is studied for two classes of regular graphs with extremal values of expansion, namely, for rings and for random $\maxdeg$-regular graphs (an important class of expanders). {F}or the ring, \algo{{R}/{A}} is shown to achieve an expected searching time of $2d+k^{\{T}heta(1)}$ for a worst-case distribution of liars, which is polynomial in both $d$ and $k$. {F}or random $\maxdeg$-regular graphs, the expected searching time of the \algo{{R}/{A}} strategy is ${O}(k3 \log3 n)$ a.a.s. {T}he polylogarithmic factor with respect to $n$ cannot be dropped from this bound; in fact, we show that a lower time bound of $\{O}mega (\log n)$ steps holds for all $d,k=\{O}mega(\log\log n)$ in random $\maxdeg$-regular graphs a.a.s.\ and applies even to strategies which make use of some knowledge of the environment. {F}inally, we study oblivious strategies which do not use any memory (in particular, with no timer). {S}uch strategies are essentially a form of a random walk, possibly biased by local advice. {W}e show that such biased random walks sometimes achieve drastically worse performance than the \algo{{R}/{A}} strategy. {I}n particular, on the ring, no biased random walk can have a searching time which is polynomial in $d$ and $k$},
OPTkeywords = {{D}istributed {C}omputing; {M}obile {A}gent; {R}andom {W}alks; {E}xpanders; {F}aulty {N}etworks},
language = {{A}nglais},
affiliation = {{L}aboratoire {B}ordelais de {R}echerche en {I}nformatique - {L}a{BRI} - {CNRS} : {UMR}5800 - {U}niversit{\'e} {S}ciences et {T}echnologies - {B}ordeaux {I} - {E}cole {N}ationale {S}up{\'e}rieure d'{E}lectronique, {I}nformatique et {R}adiocommunications de {B}ordeaux - {U}niversit{\'e} {V}ictor {S}egalen - {B}ordeaux {II} - {CEPAGE} - {INRIA} {B}ordeaux - {S}ud-{O}uest - {INRIA} - {CNRS} : {UMR}5800 - {U}niversit{\'e} {S}ciences et {T}echnologies - {B}ordeaux {I} - {ENSEIRB} - {D}epartment of {A}lgorithms and {S}ystem {M}odeling - {G}dansk {U}niversity of {T}echnology - {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 = {19},
type = {Research Report},
institution = {INRIA},
number = {{RR}-7210},
month = feb,
year = {2010},
URL = {http://hal.inria.fr/inria-00458808/en/},
pdf = {http://hal.inria.fr/inria-00458808/PDF/RR-7210.pdf},
x-pays = {PL},
sorte = "Rapports",
}
-
F. Havet,
C. Linhares Sales,
and L. Sampaio.
b-coloring of tight graphs.
Research Report 7241,
INRIA,
March 2010.
[WWW
] [PDF
]
| Abstract: |
A coloring $c$ of a graph $G = (V, E)$ is a \emph{$b$-coloring} if in every color class there is a vertex whose neighborhood intersects every other color classes. The \emph{$b$-chromatic number} of $G$, denoted $\chi_b(G)$, is the greatest integer $k$ such that $G$ admits a $b$-coloring with $k$ colors. A graph $G$ is \emph{tight} if it has exactly $m(G)$ vertices of degree $m(G) - 1$, where $m(G)$ is the largest integer $m$ such that $G$ has at least $m$ vertices of degree at least $m-1$. Determining the $b$-chromatic number of a tight graph $G$ is NP-hard even for a connected bipartite graph \cite{KTV02}. In this paper we show that it is also NP-hard for a tight chordal graph. We also show that the $b$-chromatic number of a split graph can be computed is polynomial. Then we define the $b$-closure and the partial $b$-closure of a tight graph, and use these concepts to give a characterization of tight graphs whose $b$-chromatic number is equal to $m(G)$. This characterization is used to develop polynomial time algorithms for deciding whether $\chi_b(G) = m(G)$, for tight graphs that are complement of bipartite graphs, $P_4$-sparse and block graphs. We generalize the concept of pivoted tree introduced by Irving and Manlove \cite{IM99} and show its relation with the $b$-chromatic number of tight graphs. Finally, we give an alternative formulation of the Erd\"os-Faber-Lov\'asz conjecture in terms of $b$-colorings of tight graphs. |
@techReport{HLS10,
author = {Havet, F. and Linhares Sales, C. and Sampaio, L.},
title = {b-coloring of tight graphs},
year = {2010},
month = mar,
institution = {INRIA},
number = {7241},
type = {Research Report},
url = {http://hal.archives-ouvertes.fr/inria-00468734/fr/},
pdf = {http://hal.archives-ouvertes.fr/docs/00/46/87/34/PDF/RR-7241.pdf },
abstract = {A coloring $c$ of a graph $G = (V, E)$ is a \emph{$b$-coloring} if in every color class there is a vertex whose neighborhood intersects every other color classes. The \emph{$b$-chromatic number} of $G$, denoted $\chi_b(G)$, is the greatest integer $k$ such that $G$ admits a $b$-coloring with $k$ colors. A graph $G$ is \emph{tight} if it has exactly $m(G)$ vertices of degree $m(G) - 1$, where $m(G)$ is the largest integer $m$ such that $G$ has at least $m$ vertices of degree at least $m-1$. Determining the $b$-chromatic number of a tight graph $G$ is NP-hard even for a connected bipartite graph \cite{KTV02}. In this paper we show that it is also NP-hard for a tight chordal graph. We also show that the $b$-chromatic number of a split graph can be computed is polynomial. Then we define the $b$-closure and the partial $b$-closure of a tight graph, and use these concepts to give a characterization of tight graphs whose $b$-chromatic number is equal to $m(G)$. This characterization is used to develop polynomial time algorithms for deciding whether $\chi_b(G) = m(G)$, for tight graphs that are complement of bipartite graphs, $P_4$-sparse and block graphs. We generalize the concept of pivoted tree introduced by Irving and Manlove \cite{IM99} and show its relation with the $b$-chromatic number of tight graphs. Finally, we give an alternative formulation of the Erd\"os-Faber-Lov\'asz conjecture in terms of $b$-colorings of tight graphs.},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
x-pays={BR},
sorte = "Rapports",
}
-
P. Uribe,
J-C. Maureira Bravo,
and O. Dalle.
Extending INET Framework for Directional and Asymmetrical Wireless Communications.
Research Report RR-7120,
INRIA,
03 2010.
[WWW
] [PDF
]
Keywords:
OMNeT++,
INET Framework,
Directional Radios,
Asymmetrical communication.
| Abstract: |
{T}his paper reports our work on extending the {O}mnet {INET} {F}ramework with a directional radio model, putting a special emphasis on the implementation of asymmetrical communications. {W}e first analyze the original {INET} radio model, focusing on its design and components. {T}hen we discuss the modifications that have been done to support directional communications. {O}ur preliminary results show that the new model is flexible enough to allow the user to provide any antenna pattern shape, with only an additional reasonable computational cost. |
@techreport{UMD10b,
url = {http://hal.inria.fr/inria-00448033/en/},
title = { {E}xtending {INET} {F}ramework for {D}irectional and {A}symmetrical {W}ireless {C}ommunications},
author = {Uribe, P. and {Maureira Bravo}, J-C. and Dalle, O.},
abstract = {{T}his paper reports our work on extending the {O}mnet {INET} {F}ramework with a directional radio model, putting a special emphasis on the implementation of asymmetrical communications. {W}e first analyze the original {INET} radio model, focusing on its design and components. {T}hen we discuss the modifications that have been done to support directional communications. {O}ur preliminary results show that the new model is flexible enough to allow the user to provide any antenna pattern shape, with only an additional reasonable computational cost.},
keywords = {{OMN}e{T}++, {INET} {F}ramework, {D}irectional {R}adios, {A}symmetrical communication},
language = {{E}nglish},
affiliation = {{C}enter for {M}athematical {M}odeling - {CMM} - {CNRS} : {UMR}2071 - {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 },
type = {{R}esearch {R}eport},
institution = {INRIA},
number = {{RR}-7120},
day = {31},
month = {03},
year = {2010},
pdf = {http://hal.inria.fr/inria-00448033/PDF/RR-7120.pdf},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
sorte = "Rapports",
}
-
N. Cohen.
Several Graph Problems and their LP formulation,
2010.
[PDF
]
| Abstract: |
In this document are given Linear Program formulations of several graph problems involving acyclicity constraints without the use of constraint generations. |
@Misc{Coh10,
author = {N. Cohen},
title = {Several Graph Problems and their LP formulation},
year = {2010},
ABSTRACT = {In this document are given Linear Program formulations of several graph problems involving acyclicity constraints without the use of constraint generations.},
PDF = {http://hal.archives-ouvertes.fr/docs/00/50/49/14/PDF/LP_formulations.pdf},
sorte = "Rapports",
}
BACK TO MASCOTTE PUBLICATION INDEX
Last modified: Thu Oct 10 14:10:00 2013
This document was translated from BibTEX by
bibtex2html
|
