-
J. Bang-Jensen,
B. Reed,
M. Schacht,
R. Sámal,
B. Toft,
and U. Wagner.
Topics in Discrete Mathematics, Dedicated to Jarik Nesetril on the Occasion of his 60th birthday,
volume 26 of Algorithms and Combinatorics,
chapter On six problems posed by Jarik Nesetril,
pages 613--627.
Springer,
Berlin,
M. Klazar, J. Kratochvil, M. Loebl, J. Matousek, R. Thomas and P. Valtr edition,
2006.
@InBook{BRS+06,
sorte = "livres-chap",
author = {J. Bang-Jensen and B. Reed and M. Schacht and R. \v{S}\'amal and B. Toft and U. Wagner},
OPTALTeditor = {},
title = {Topics in Discrete Mathematics, Dedicated to Jarik Ne\v{s}et\v{r}il on the Occasion of his 60th birthday},
chapter = {On six problems posed by Jarik Ne\v{s}et\v{r}il},
publisher = {Springer},
year = {2006},
OPTkey = {},
volume = {26},
OPTnumber = {},
series = {Algorithms and Combinatorics},
OPTtype = {},
address = {Berlin},
edition = {{M. Klazar, J. Kratochvil, M. Loebl, J. Matousek, R. Thomas and P. Valtr}},
OPTmonth = {},
pages = {613--627},
OPTnote = {},
OPTannote = {}
}
-
J-C. Bermond and D. Coudert.
Handbook of Combinatorial Designs (2nd edition),
volume 42 of Discrete mathematics and Applications,
chapter VI.27, Grooming,
pages 494-496.
Chapman & Hall- CRC Press, editors C.J. Colbourn and J.H. Dinitz,
November 2006.
[WWW
] [PDF
]
| Abstract: |
|
State-of-the-art on traffic grooming with a design theory approach |
@INBOOK{BeCo06,
chapter = {VI.27, Grooming},
pages = {494-496},
title = { Handbook of Combinatorial Designs (2nd edition)},
publisher = {Chapman \& Hall- CRC Press, editors C.J. Colbourn and J.H. Dinitz},
year = {2006},
editor = { },
author = {J-C. Bermond and D. Coudert},
volume = {42},
series = {Discrete mathematics and Applications},
month = nov,
abstract = {State-of-the-art on traffic grooming with a design theory approach},
isbn = {1584885068},
sorte = "livres-chap",
pdf = {http://www-sop.inria.fr/members/Jean-Claude.Bermond//PUBLIS/BeCo06.pdf},
url = {http://www.cems.uvm.edu/~dinitz/hcd.shtml}
}
-
S. Alouf,
E. Altman,
J. Galtier,
J.-F. Lalande,
and C. Touati.
Quasi-Optimal Resource Allocation in Multi-Spot MFTDMA Satellite Networks.
In M. Cheng,
Y. Li,
and D.-Z. Du, editors,Combinatorial Optimization in Communication Networks,
chapter 12,
pages 325-366.
Kluwer Academic Publishers,
2006.
[PDF
]
@InCollection{AAG+06,
author = {S. Alouf and E. Altman and J. Galtier and J.-F. Lalande and C. Touati},
title = {Quasi-Optimal Resource Allocation in Multi-Spot {MFTDMA} Satellite Networks},
booktitle = {Combinatorial Optimization in Communication Networks},
pages = {325-366},
publisher = {Kluwer Academic Publishers},
year = {2006},
editor = {M. Cheng and Y. Li and D.-Z. Du},
chapter = {12},
pdf = {ftp://ftp-sop.inria.fr/mascotte/Publications/AAG+06.pdf},
sorte = "livres-chap",
}
-
D. Bartha,
P. Berthomé,
M. Diallo,
and A. Ferreira.
Revisiting parametric multi-terminal problems: Maximum flows, minimum cuts and cut-tree computations.
Discrete Optimization,
3(3):195--205,
September 2006.
@Article{BBDF06,
author = {D. Bartha and P. Berthom\'e and M. Diallo and A. Ferreira},
title = {Revisiting parametric multi-terminal problems: Maximum flows, minimum cuts and cut-tree computations},
journal = {Discrete Optimization},
year = {2006},
OPTkey = {},
volume = {3},
number = {3},
pages = {195--205},
month = {September},
sorte = "rev-int",
OPTnote = {},
OPTannote = {}
}
-
J. Becker,
Z. Csizmadia,
J. Galtier,
A. Laugier,
J. Szabó,
and L. Szego.
An integer programming approach to routing in Daisy networks.
Networks,
47(2):116--121,
2006.
[PDF
]
@article{BCG+06,
author = {J. Becker and Z. Csizmadia and J. Galtier and A. Laugier and J. Szab\'o and L. Szeg\H{o}},
title = {An integer programming approach to routing in Daisy networks},
journal = {Networks},
year = {2006},
volume = {47},
number = {2},
pages={116--121},
sorte = "rev-int",
pdf = {ftp://ftp-sop.inria.fr/mascotte/Publications/BCG+06.pdf},
}
-
J-C. Bermond,
J. Galtier,
R. Klasing,
N. Morales,
and S. Pérennes.
Hardness and approximation of Gathering in static radio networks.
Parallel Processing Letters,
16(2):165--183,
2006.
[PDF
]
| Abstract: |
|
In this paper, we address the problem of gathering information in a specific node (or \emph{sink}) of a radio network, where interference constraints are present. We take into account the fact that, when a node transmits, it produces interference in an area bigger than the area in which its message can actually be received. The network is modeled by a graph; a node is able to transmit one unit of information to the set of vertices at distance at most $\dt$ in the graph, but when doing so it generates interference that does not allow nodes at distance up to $\di$ ($\di \ge \dt$) to listen to other transmissions. Time is synchronous and divided into time-steps in each of which a round (set of non-interfering radio transmissions) is performed. We give general lower bounds on the number of rounds required to gather into a sink of a general graph, and present an algorithm working on any graph, with an approximation factor of 4. We also show that the problem of finding an optimal strategy for gathering is \textsc{NP-hard}, for any values of $\di$ and $\dt$. If $\di>\dt$, we show that the problem remains hard when restricted to the uniform case where each vertex in the network has exactly one piece of information to communicate to the sink. |
@article{BGKM+06a,
author= { J-C. Bermond and J. Galtier and R. Klasing and N. Morales and S. P\'erennes },
title= { Hardness and approximation of Gathering in static radio networks },
journal= { Parallel Processing Letters },
year= { 2006 },
volume= { 16 },
number= { 2 },
pages= { 165--183 },
sorte = "rev-int",
pdf= { http://www-sop.inria.fr/members/Jean-Claude.Bermond/PUBLIS/BGK+06c.pdf },
abstract={In this paper, we address the problem of gathering information in a specific node (or \emph{sink}) of a radio network, where interference constraints are present. We take into account the fact that, when a node transmits, it produces interference in an area bigger than the area in which its message can actually be received. The network is modeled by a graph; a node is able to transmit one unit of information to the set of vertices at distance at most $\dt$ in the graph, but when doing so it generates interference that does not allow nodes at distance up to $\di$ ($\di \ge \dt$) to listen to other transmissions. Time is synchronous and divided into time-steps in each of which a round (set of non-interfering radio transmissions) is performed. We give general lower bounds on the number of rounds required to gather into a sink of a general graph, and present an algorithm working on any graph, with an approximation factor of 4. We also show that the problem of finding an optimal strategy for gathering is \textsc{NP-hard}, for any values of $\di$ and $\dt$. If $\di>\dt$, we show that the problem remains hard when restricted to the uniform case where each vertex in the network has exactly one piece of information to communicate to the sink. },
}
-
J-C. Bermond,
F. Havet,
and D. Tóth.
Fault tolerant on board networks with priorities.
Networks,
47(1):9--25,
2006.
[PDF
]
| Abstract: |
|
We consider on-board networks in satellites interconnecting entering signals (inputs) to amplifiers (outputs). The connections are made via expensive switches, each of which has four available links. The paths connecting inputs to outputs should be link-disjoint. Some of the input signals, called priorities, must be connected to the amplifiers which provide the best quality of service (that is to some specific outputs). In practice, amplifiers are prone to fail and the faults cannot be repaired. Therefore, extra outputs have to be built into the network to ensure that every input can be routed to operational outputs. Given three integers, $n$, $p$, and $f$, we would like to design a low cost network (where the network cost is proportional to the total number of switches) such that it is possible to route all $n$ inputs to $n$ operational amplifiers, and to route the $p$ priorities to the $p$ best quality amplifiers for any set of $f$ faulty and $p$ best-quality amplifiers. Let $R(n,p,f)$ be the minimum number of switches of such a network. We prove here that $R(n,p,f)\leq \frac{n+f}{2} \lceil \log_2 p \rceil +\frac{5}{2}(n-p) +g(f)$ with $g$ a function depending only on $f$. We then compute $R(n,p,f)$ exactly for a few small values of $p$ and $f$. |
@article{BHT06,
author={J-C. Bermond and F. Havet and D. T\'oth},
title={Fault tolerant on board networks with priorities},
journal={Networks},
year={2006},
pages={9--25},
volume={47},
number={1},
sorte = "rev-int",
PDF={http://www-sop.inria.fr/members/Jean-Claude.Bermond/PUBLIS/BHT06.pdf},
abstract={We consider on-board networks in satellites interconnecting entering signals (inputs) to amplifiers (outputs). The connections are made via expensive switches, each of which has four available links. The paths connecting inputs to outputs should be link-disjoint. Some of the input signals, called priorities, must be connected to the amplifiers which provide the best quality of service (that is to some specific outputs). In practice, amplifiers are prone to fail and the faults cannot be repaired. Therefore, extra outputs have to be built into the network to ensure that every input can be routed to operational outputs. Given three integers, $n$, $p$, and $f$, we would like to design a low cost network (where the network cost is proportional to the total number of switches) such that it is possible to route all $n$ inputs to $n$ operational amplifiers, and to route the $p$ priorities to the $p$ best quality amplifiers for any set of $f$ faulty and $p$ best-quality amplifiers. Let $R(n,p,f)$ be the minimum number of switches of such a network. We prove here that $R(n,p,f)\leq \frac{n+f}{2} \lceil \log_2 p \rceil +\frac{5}{2}(n-p) +g(f)$ with $g$ a function depending only on $f$. We then compute $R(n,p,f)$ exactly for a few small values of $p$ and $f$. },
}
-
S. Bessy,
E. Birmelé,
and F. Havet.
Arc-chromatic number of digraphs in which each vertex has bounded outdegree or bounded indegree.
Journal of Graph Theory,
53(4):315--332,
2006.
[WWW
] [PDF
]
@article{BBH06,
author={Bessy, S. and Birmel\'e, E. and F. Havet},
title={Arc-chromatic number of digraphs in which each vertex has bounded outdegree or bounded indegree},
journal = {Journal of Graph Theory},
year = {2006},
number = {4},
volume = {53},
pages = {315--332},
sorte = "rev-int",
PDF = {ftp://ftp.inria.fr/INRIA/publication/publi-pdf/RR/RR-5364.pdf},
URL = {http://www.inria.fr/rrrt/rr-5364.shtml},
}
-
A. Bondy,
J. Shen,
S. Thomassé,
and C. Thomassen.
Density conditions for triangles in multipartite graphs.
Combinatorica,
26(2):121--131,
2006.
@article{MR2223630,
sorte = "rev-int",
AUTHOR = {Bondy, A. and Shen, J. and Thomass\'e, S. and {T}homassen, C.},
TITLE = {Density conditions for triangles in multipartite graphs},
JOURNAL = {Combinatorica},
VOLUME = {26},
YEAR = {2006},
NUMBER = {2},
PAGES = {121--131},
}
-
D. J. Dougherty,
P. Lescanne,
and L. Liquori.
Addressed Term Rewriting Systems: Application to a Typed Object Calculus.
Journal of Mathematical Structures in Computer Science,
16(4):667--709,
2006.
[PDF
]
@article{DLL06,
sorte = "rev-int",
author = {D. J. Dougherty and P. Lescanne and L. Liquori},
title = {Addressed Term Rewriting Systems: Application to a Typed Object Calculus},
JOURNAL = {Journal of Mathematical Structures in Computer Science},
year = {2006},
volume = {16},
number = {4},
pages = {667--709},
PDF = {http://www-sop.inria.fr/mascotte/Luigi.Liquori/PAPERS/mscs-06.pdf}
}
-
M. Flammini,
A. Navarra,
and S. Pérennes.
The Real Approximation Factor of the MST heuristic for the Minimum Energy Broadcasting.
ACM Journal of Experimental Algorithmics,
11:1--13,
2006.
Note: (Special Issue associated to the 4th International Workshop on Efficient and Experimental Algorithms (WEA 2005)).
@article{FNP06,
sorte = "rev-int",
author= { M. Flammini and A. Navarra and S. P\'erennes },
title= { The Real Approximation Factor of the {MST} heuristic for the Minimum Energy Broadcasting },
journal= { ACM Journal of Experimental Algorithmics },
note= { (Special Issue associated to the 4th International Workshop on Efficient and Experimental Algorithms (WEA 2005)) },
year= { 2006 },
volume= { 11 },
OPTnumber = {une seule issue dans l'annee},
pages= { 1--13 },
}
-
F. Havet.
Repartitors, selectors and superselectors.
Journal of Interconnection Networks,
7(3):391--415,
2006.
[PDF
]
@Article{Hav06a,
author = {F. Havet},
title = {Repartitors, selectors and superselectors},
journal = {Journal of Interconnection Networks},
year = {2006},
pages = {391--415},
volume ={7},
number={3},
sorte = "rev-int",
pdf = {ftp://ftp-sop.inria.fr/mascotte/Publications/Hav06a.pdf},
}
-
F. Havet and J.-S. Sereni.
Improper choosability of graphs and maximum average degree.
Journal of Graph Theory,
52(3):181--199,
2006.
[PDF
]
@Article{HaSe06,
author={F. Havet and J.-S. Sereni},
title={Improper choosability of graphs and maximum average degree},
journal={Journal of Graph Theory},
volume={52},
number={3},
pages={181--199},
year={2006},
sorte = "rev-int",
PDF={http://kam.mff.cuni.cz/~sereni/Articles/HaSe06.pdf},
}
-
C. McDiarmid and B. Reed.
Concentration for self-bounding functions and an inequality of talagrand.
Random Structures and Algorithms,
29:549--557,
2006.
@Article{McRe06,
sorte = "rev-int",
author = {C. McDiarmid and B. Reed},
title = {Concentration for self-bounding functions and an inequality of talagrand},
journal = {Random Structures and Algorithms},
year = {2006},
OPTkey = {},
volume = {29},
OPTnumber = {},
pages = {549--557},
OPTmonth = {},
OPTannote = {}
}
-
J. Moulierac,
A. Guitton,
and M. Molnár.
Hierarchical Aggregation of Multicast Trees in Large Domains.
Journal of Communications (JCM),
6(1):33--44,
September 2006.
[PDF
]
| Abstract: |
|
Multicast tree aggregation is a technique that reduces the control overhead and the number of states induced by multicast. The main idea of this protocol is to route several groups to the same distribution tree in order to reduce the total number of multicast forwarding states. In this article, we show that this technique cannot be applied to large domains. Indeed, when the number of border routers is large, actual tree aggregation protocols are unable to find similar groups to aggregate to the same tree. However, by dividing the domain into several smaller sub-domains, we prove that it is possible to achieve important savings. A hierarchical protocol is designed to interconnect the trees of the sub-domains together. While previous protocols cannot cope with more than 25 border routers, our protocol still shows significant benefits for domains with 200 border routers. |
@Article{MGM06a,
sorte = "rev-int",
author = {J. Moulierac and A. Guitton and M. Moln\'ar},
title = {{Hierarchical Aggregation of Multicast Trees in Large Domains}},
journal = {Journal of Communications (JCM)},
year = {2006},
volume = {6},
number = {1},
pages = {33--44},
series= {Academy Publisher},
month = {September},
PDF={ftp://ftp-sop.inria.fr/mascotte/personnel/Joanna.Moulierac/pdf/moulierac06hierarchical.pdf},
ABSTRACT={Multicast tree aggregation is a technique that reduces the control overhead and the number of states induced by multicast. The main idea of this protocol is to route several groups to the same distribution tree in order to reduce the total number of multicast forwarding states. In this article, we show that this technique cannot be applied to large domains. Indeed, when the number of border routers is large, actual tree aggregation protocols are unable to find similar groups to aggregate to the same tree. However, by dividing the domain into several smaller sub-domains, we prove that it is possible to achieve important savings. A hierarchical protocol is designed to interconnect the trees of the sub-domains together. While previous protocols cannot cope with more than 25 border routers, our protocol still shows significant benefits for domains with 200 border routers.}
}
-
C. Touati,
E. Altman,
and J. Galtier.
Generalized Nash Bargaining Solution for bandwidth allocation.
Computer Networks,
50:3242--3263,
2006.
[PDF
]
@Article{TAG06,
author = {C. Touati and E. Altman and J. Galtier},
title = {Generalized {Nash} Bargaining Solution for bandwidth allocation},
journal = {Computer Networks},
year = {2006},
volume = {50},
pages = {3242--3263},
sorte = "rev-int",
PDF = {ftp://ftp-sop.inria.fr/mascotte/Publications/TAG06.pdf},
}
-
E. Altman,
J. Galtier,
and C. Touati.
Fair power and transmission rate control in wireless networks.
In The Third Annual Conference on Wireless On demand Network Systems and Services,
pages 134--143,
2006.
[PDF
]
@InProceedings{AGT06,
author = {E. Altman and J. Galtier and C. Touati},
title = {Fair power and transmission rate control in wireless networks},
booktitle = {The Third Annual Conference on Wireless On demand Network Systems and Services},
pages = {134--143},
year = {2006},
sorte = "conf-int",
pdf = {ftp://ftp-sop.inria.fr/mascotte/Publications/AGT06.pdf},
}
-
O. Amini,
J-C. Bermond,
F. Giroire,
F. Huc,
and S. Pérennes.
Design of Minimal Fault Tolerant Networks: Asymptotic Bounds.
In Huitièmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications (AlgoTel'06),
Trégastel, France,
pages 37--40,
May 2006.
[WWW
] [PDF
]
| Abstract: |
|
This paper deals with the design of on board networks in satellites (also called Traveling wave tube Amplifiers (TWTA)). These networks should connect signals arriving on some ports of the satellite to amplifiers, even in case of failures of some amplifiers. They are made of links and expensive switches each with 4 links. So, the aim is to design networks having as few switches as possible and satisfying the following property: \emph{there exist $p$ edge-disjoint paths from the $p$ signals arriving on $p + \lambda$ ports (inputs) to any set of $p$ amplifiers (outputs) chosen from the $p+k$ total number of outputs}. We call such networks \emph{valid $(p,\lambda,k)$-networks} and want to determine the minimum number of switches $\mathcal{N}(p, \lambda,k)$ of such networks. By symmetry we suppose $\lambda \leq k$. We give tight results for small values of $k$ and asymptotic results when $k = O(\log p)$ which are tight when $k=\Theta(\lambda)$ and when $\lambda=0$. |
@inproceedings{ABG+06,
author={O. Amini and J-C. Bermond and F. Giroire and F. Huc and S. P\'erennes},
title={Design of Minimal Fault Tolerant Networks: Asymptotic Bounds},
booktitle={Huiti\`emes Rencontres Francophones sur les Aspects Algorithmiques des T\'el\'ecommunications (AlgoTel'06)},
address={Tr\'egastel, France},
month={May},
year={2006},
pages={37--40},
sorte = "conf-nat",
URL={http://algotel2006.lip6.fr/},
PDF={http://www-sop.inria.fr/members/Jean-Claude.Bermond//PUBLIS/ABG+06.pdf},
abstract = {This paper deals with the design of on board networks in satellites (also called Traveling wave tube Amplifiers (TWTA)). These networks should connect signals arriving on some ports of the satellite to amplifiers, even in case of failures of some amplifiers. They are made of links and expensive switches each with 4 links. So, the aim is to design networks having as few switches as possible and satisfying the following property: \emph{there exist $p$ edge-disjoint paths from the $p$ signals arriving on $p + \lambda$ ports (inputs) to any set of $p$ amplifiers (outputs) chosen from the $p+k$ total number of outputs}. We call such networks \emph{valid $(p,\lambda,k)$-networks} and want to determine the minimum number of switches $\mathcal{N}(p, \lambda,k)$ of such networks. By symmetry we suppose $\lambda \leq k$. We give tight results for small values of $k$ and asymptotic results when $k = O(\log p)$ which are tight when $k=\Theta(\lambda)$ and when $\lambda=0$.},
}
-
M. Ancona,
W. Cazzola,
S. Drago,
and G. Quercini.
Visualizing and Managing Network Topologies via Rectangular Dualization.
In ISCC '06: Proceedings of the 11th IEEE Symposium on Computers and Communications,
Washington, DC, USA,
pages 1000-1005,
2006.
IEEE Computer Society.
[PDF
]
| Abstract: |
|
Rectangular dualization is an effective, hierarchically oriented visualization method for network topologies and can be used in many other problems having in common with networks the condition that objects and their interoccurring relations are represented by means of a planar graph. However, only 4-connected triangulated planar graphs admit a rectangular dual. In this paper we present a linear time algorithm to optimally construct a rectangular layout for a general class of graphs and we discuss a variety of application fields where this approach represents an helpful support for visualization tools. |
@inproceedings{ACD+06,
sorte = "conf-int",
author = {M. Ancona and W. Cazzola and S. Drago and G. Quercini},
title = {Visualizing and Managing Network Topologies via Rectangular Dualization},
booktitle = {ISCC '06: Proceedings of the 11th IEEE Symposium on Computers and Communications},
year = {2006},
pages = {1000-1005},
publisher = {IEEE Computer Society},
address = {Washington, DC, USA},
abstract = {Rectangular dualization is an effective, hierarchically oriented visualization method for network topologies and can be used in many other problems having in common with networks the condition that objects and their interoccurring relations are represented by means of a planar graph. However, only 4-connected triangulated planar graphs admit a rectangular dual. In this paper we present a linear time algorithm to optimally construct a rectangular layout for a general class of graphs and we discuss a variety of application fields where this approach represents an helpful support for visualization tools.},
pdf = {ftp://ftp-sop.inria.fr/mascotte/Publications/ACD+06.pdf},
}
-
R. Bayon,
N. Lygeros,
and J.-S. Sereni.
Orders with ten elements are circle orders.
In Book of abstracts of the nineteenth Panhellenic Conference/Summer School on nonlinear science and complexity,
Thessaloniki,
pages 1p,
July 2006.
[WWW
] [PDF
]
@InProceedings{BLS06b,
sorte = "conf-sa",
author = {R. Bayon and N. Lygeros and J.-S. Sereni},
title = {Orders with ten elements are circle orders},
booktitle = {Book of abstracts of the nineteenth Panhellenic Conference/Summer School on nonlinear science and complexity},
year = {2006},
pages = {1p},
address={Thessaloniki},
month={July},
URL={http://web.auth.gr/nonlinear/home_page_en.php},
PDF={http://www.math.upatras.gr/~crans/Book of Abstracts-4.pdf},
}
-
D. Benza,
M. Cosnard,
L. Liquori,
and M. Vesin.
Arigatoni: Overlaying Internet via Low Level Network Protocols.
In JVA: John Vincent Atanasoff International Symposium on Modern Computing,
pages 82--91,
2006.
IEEE.
[PDF
]
@inproceedings{BCLV06,
author = {D. Benza and M. Cosnard and L. Liquori and M. Vesin},
title = {Arigatoni: Overlaying Internet via Low Level Network Protocols},
booktitle = {JVA: John Vincent Atanasoff International Symposium on Modern Computing},
publisher = {IEEE},
year = {2006},
pages = {82--91},
sorte = "conf-int",
PDF = {http://www-sop.inria.fr/mascotte/Luigi.Liquori/PAPERS/jva-06.pdf}
}
-
J-C. Bermond,
R. Corrêa,
and M-L. Yu.
Gathering algorithms on paths under interference constraints.
In 6th Conference on Algorithms and Complexity,
volume 3998 of Lecture Notes in Computer Science,
Roma, Italy,
pages 115--126,
May 2006.
[WWW
] [PDF
]
@inproceedings{BCY06,
title={Gathering algorithms on paths under interference constraints},
author={J-C. Bermond and R. Corr\^ea and M-L. Yu},
year={2006},
booktitle={6th Conference on Algorithms and Complexity},
address={Roma, Italy},
series={Lecture Notes in Computer Science},
volume={3998},
pages={115--126},
month={May},
sorte = "conf-int",
URL={http://www.dsi.uniroma1.it/~ciac/},
PDF={http://www-sop.inria.fr/members/Jean-Claude.Bermond//PUBLIS/BCY06.pdf},
}
-
J-C. Bermond,
M. Cosnard,
D. Coudert,
and S. Pérennes.
Optimal Solution of the Maximum All Request Path Grooming Problem.
In Advanced International Conference on Telecommunications (AICT),
pages 6p,
2006.
IEEE.
[PDF
]
| Abstract: |
|
We give an optimal solution to the Maximum All Request Path Grooming (MARPG) problem motivated by a traffic grooming application. The MARPG problem consists in finding the maximum number of connections which can be established in a path of size $N$, where each arc has a capacity or bandwidth $C$ (grooming factor). We present a greedy algorithm to solve the problem and an explicit formula for the maximum number of requests that can be groomed. In particular, if $C = s(s 1)/2$ and $N > s(s-1)$, an optimal solution is obtained by taking all the requests of smallest length, that is of length 1 to $s$. However this is not true in general since anomalies can exist. We give a complete analysis and the exact number of such anomalies. |
@INPROCEEDINGS{BCCP06,
author = {J-C. Bermond and M. Cosnard and D. Coudert and S. P\'erennes},
title = {Optimal Solution of the Maximum All Request Path Grooming Problem},
booktitle = {Advanced International Conference on Telecommunications (AICT)},
year = {2006},
pages = {6p},
publisher = {IEEE},
sorte = "conf-int",
abstract = {We give an optimal solution to the Maximum All Request Path Grooming (MARPG) problem motivated by a traffic grooming application. The MARPG problem consists in finding the maximum number of connections which can be established in a path of size $N$, where each arc has a capacity or bandwidth $C$ (grooming factor). We present a greedy algorithm to solve the problem and an explicit formula for the maximum number of requests that can be groomed. In particular, if $C = s(s 1)/2$ and $N > s(s-1)$, an optimal solution is obtained by taking all the requests of smallest length, that is of length 1 to $s$. However this is not true in general since anomalies can exist. We give a complete analysis and the exact number of such anomalies.},
pdf = {ftp://ftp-sop.inria.fr/mascotte/personnel/David.Coudert/Publication/BCCP-AICT06.pdf}
}
-
J-C. Bermond,
D. Coudert,
X. Muñoz,
and I. Sau.
Traffic Grooming in Bidirectional WDM ring networks.
In IEEE-LEOS ICTON / COST 293 GRAAL,
volume 3,
pages 19-22,
June 2006.
[PDF
]
| Abstract: |
|
We study the minimization of ADMs (Add-Drop Multiplexers) in Optical WDM Networks with Bidirectional Ring topology considering symmetric shortest path routing and all-to-all unitary requests. We insist on the statement of the problem, which had not been clearly stated before in the bidirectional case. Optimal solutions had not been found up to date. In particular, we study the case $C = 2$ and $C = 3$ (giving either optimal constructions or near-optimal solutions) and the case $C = k(k 1)/2$ (giving optimal decompositions for specific congruence classes of $N$). We state a general Lower Bound for all the values of $C$ and $N$, and we improve this Lower Bound for $C=2$ and $C=3$ (when $N=4t 3)$. We also include some comments about the simulation of the problem using Linear Programming. |
@INPROCEEDINGS{BCMS06,
author = {J-C. Bermond and D. Coudert and X. Mu{\~n}oz and I. Sau},
title = {Traffic Grooming in Bidirectional {WDM} ring networks},
booktitle = {IEEE-LEOS ICTON / COST 293 GRAAL},
year = {2006},
volume = {3},
pages = {19-22},
month = jun,
abstract = {We study the minimization of ADMs (Add-Drop Multiplexers) in Optical WDM Networks with Bidirectional Ring topology considering symmetric shortest path routing and all-to-all unitary requests. We insist on the statement of the problem, which had not been clearly stated before in the bidirectional case. Optimal solutions had not been found up to date. In particular, we study the case $C = 2$ and $C = 3$ (giving either optimal constructions or near-optimal solutions) and the case $C = k(k 1)/2$ (giving optimal decompositions for specific congruence classes of $N$). We state a general Lower Bound for all the values of $C$ and $N$, and we improve this Lower Bound for $C=2$ and $C=3$ (when $N=4t 3)$. We also include some comments about the simulation of the problem using Linear Programming.},
sorte = "conf-int",
optbooktitle = {IEEE/COST 293 annual conference on GRAphs and ALgorithms in communication networks},
pdf = {ftp://ftp-sop.inria.fr/mascotte/personnel/David.Coudert/Publication/BCMS-ICTON-GRAAL06.pdf}
}
-
J-C. Bermond,
J. Galtier,
R. Klasing,
N. Morales,
and S. Pérennes.
Hardness and approximation of Gathering in static radio networks.
In FAWN06,
Pisa, Italy,
pages 75--79,
March 2006.
[WWW
] [PDF
]
@InProceedings{BGK+06a,
author = {J-C. Bermond and J. Galtier and R. Klasing and N. Morales and S. P\'erennes},
title = {Hardness and approximation of Gathering in static radio networks},
booktitle = { FAWN06 },
year = {2006},
Pages={75--79},
address = {Pisa, Italy},
month = {March},
sorte = "conf-int",
URL={http://ares.insa-lyon.fr/fawn2006/},
PDF={http://www-sop.inria.fr/members/Jean-Claude.Bermond//PUBLIS/BGK+06.pdf},
}
-
J-C. Bermond,
J. Galtier,
R. Klasing,
N. Morales,
and S. Pérennes.
Gathering in specific radio networks.
In Huitièmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications (AlgoTel'06),
Trégastel, France,
pages 85--88,
May 2006.
[WWW
] [PDF
]
@inproceedings{BGK+06b,
author={J-C. Bermond and J. Galtier and R. Klasing and N. Morales and S. P\'erennes},
title={Gathering in specific radio networks},
booktitle={Huiti\`emes Rencontres Francophones sur les Aspects Algorithmiques des T\'el\'ecommunications (AlgoTel'06)},
address={Tr\'egastel, France},
month={May},
year={2006},
pages={85--88},
sorte = "conf-nat",
URL={http://algotel2006.lip6.fr/},
PDF={http://www-sop.inria.fr/members/Jean-Claude.Bermond//PUBLIS/BGK+06b.pdf},
}
-
L. Blin,
P. Fraigniaud,
N. Nisse,
and S. Vial.
Distributed Chasing of Network Intruders.
In Proceeding of the 13th International Colloquium on Structural Information and Communication Complexity (SIROCCO),
volume 4056 of Lecture Notes in Computer Science,
Chester, UK,
pages 70-84,
July 2006.
Springer.
[WWW
] [PDF
]
| Abstract: |
|
This paper addresses the graph searching problem in a distributed setting. We describe a distributed protocol that enables searchers with logarithmic size memory to clear any network, in a fully decentralized manner. The search strategy for the network in which the searchers are launched is computed online by the searchers themselves \emph{without knowing the topology of the network in advance}. It performs in an asynchronous environment, i.e., it implements the necessary synchronization mechanism in a decentralized manner. In every network, our protocol performs a connected strategy using at most $k+1$ searchers, where $k$ is the minimum number of searchers required to clear the network in a monotone connected way, computed in the centralized and synchronous setting. |
@inproceedings{BFNV06b,
sorte = "conf-int",
author = {L. Blin and P. Fraigniaud and N. Nisse and S. Vial},
title = {Distributed Chasing of Network Intruders},
booktitle = {Proceeding of the 13th International Colloquium on Structural Information and Communication Complexity (SIROCCO)},
year = {2006},
month = jul,
pages = {70-84},
volume = {4056},
series = {Lecture Notes in Computer Science},
publisher = {Springer},
address = {Chester, UK},
abstract = {This paper addresses the graph searching problem in a distributed setting. We describe a distributed protocol that enables searchers with logarithmic size memory to clear any network, in a fully decentralized manner. The search strategy for the network in which the searchers are launched is computed online by the searchers themselves \emph{without knowing the topology of the network in advance}. It performs in an asynchronous environment, i.e., it implements the necessary synchronization mechanism in a decentralized manner. In every network, our protocol performs a connected strategy using at most $k+1$ searchers, where $k$ is the minimum number of searchers required to clear the network in a monotone connected way, computed in the centralized and synchronous setting.},
url = {http://www.informatik.uni-trier.de/~ley/db/conf/sirocco/sirocco2006.shtml},
pdf = {http://www-sop.inria.fr/members/Nicolas.Nisse/publications/sirocco06.pdf}
}
-
L. Blin,
P. Fraigniaud,
N. Nisse,
and S. Vial.
Encerclement réparti d'un fugitif dans un réseau par des agents mobiles..
In 8èmes Rencontres Francophones sur les Aspects Algorithmiques de Télécommunications (AlgoTel),
pages 89-92,
2006.
[WWW
]
| Abstract: |
|
\emph{L'encerclement} dans les graphes est l'un des outils les plus populaires pour analyser la recherche, par une \'equipe d'agents, d'un fugitif omniscient, arbitrairement rapide et invisible dans un r\'eseau. Les solutions existantes au probl\`eme de l'encerclement dans les graphes souffrent cependant d'un s\'erieux inconv\'enient : elles sont toutes centralis\'ees et supposent que les agents \'evoluent dans un environnement synchrone. En particulier : (1) la strat\'egie d'encerclement dans un r\'eseau est calcul\'ee partant d'une connaissance compl\`ete du r\'eseau, et (2) les mouvements des agents sont control\'es par un m\'ecanisme centralis\'e qui d\'ecide \`a chaque \'etape quel agent doit se d\'eplacer et quel mouvement il doit r\'ealiser. Cet article traite de l'encerclement dans les graphes r\'ealis\'e de mani\`ere r\'epartie. Nous pr\'esentons un protocole r\'eparti qui permet \`a des agents, dont la m\'emoire est de taille logarithmique en la taille du r\'eseau, de nettoyer le r\'eseau de facon d\'ecentralis\'ee. La mani\`ere dont les agents se d\'eplacent pour r\'ealiser la strat\'egie d'encerclement est calcul\'ee en temps r\'eel par les agents eux-m\^eme, {\emph sans qu'ils ne connaissent la topologie du r\'eseau \`a l'avance}. Tout cela est r\'ealis\'e dans un environnement asynchrone, c'est-\`a-dire que notre protocole impl\'emente le m\'ecanisme de synchronisation n\'ecessaire de mani\`ere d\'ecentralis\'ee. La performance de la strat\'egie d'encerclement est mesur\'ee par le nombre d'agents utilis\'es pour capturer l'intrus. Selon cette mesure, nous prouvons que notre protocole a un rapport de comp\'etitivit\'e de $3/2$ et que c'est le meilleur ratio atteignable par n'importe quel protocole r\'eparti. En fait, pour tout r\'eseau, notre protocole calcule une strat\'egie dont nous prouvons qu'elle utilise au plus $OPT+1$ agents, o\`u $OPT$ est le nombre minimum d'agents n\'ecessaire pour nettoyer un r\'eseau de facon centralis\'ee et synchrone. |
@InProceedings{BFNV06a,
sorte = "conf-nat",
author = {L. Blin and P. Fraigniaud and N. Nisse and S. Vial},
title = {Encerclement r\'eparti d'un fugitif dans un r\'eseau par des agents mobiles.},
booktitle = {8\`emes Rencontres Francophones sur les Aspects Algorithmiques de T\'el\'ecommunications (AlgoTel)},
year = {2006},
pages ={89-92},
url = {http://algotel2006.lip6.fr/},
pdf = {},
abstract = {\emph{L'encerclement} dans les graphes est l'un des outils les plus populaires pour analyser la recherche, par une \'equipe d'agents, d'un fugitif omniscient, arbitrairement rapide et invisible dans un r\'eseau. Les solutions existantes au probl\`eme de l'encerclement dans les graphes souffrent cependant d'un s\'erieux inconv\'enient : elles sont toutes centralis\'ees et supposent que les agents \'evoluent dans un environnement synchrone. En particulier : (1) la strat\'egie d'encerclement dans un r\'eseau est calcul\'ee partant d'une connaissance compl\`ete du r\'eseau, et (2) les mouvements des agents sont control\'es par un m\'ecanisme centralis\'e qui d\'ecide \`a chaque \'etape quel agent doit se d\'eplacer et quel mouvement il doit r\'ealiser. Cet article traite de l'encerclement dans les graphes r\'ealis\'e de mani\`ere r\'epartie. Nous pr\'esentons un protocole r\'eparti qui permet \`a des agents, dont la m\'emoire est de taille logarithmique en la taille du r\'eseau, de nettoyer le r\'eseau de facon d\'ecentralis\'ee. La mani\`ere dont les agents se d\'eplacent pour r\'ealiser la strat\'egie d'encerclement est calcul\'ee en temps r\'eel par les agents eux-m\^eme, {\emph sans qu'ils ne connaissent la topologie du r\'eseau \`a l'avance}. Tout cela est r\'ealis\'e dans un environnement asynchrone, c'est-\`a-dire que notre protocole impl\'emente le m\'ecanisme de synchronisation n\'ecessaire de mani\`ere d\'ecentralis\'ee. La performance de la strat\'egie d'encerclement est mesur\'ee par le nombre d'agents utilis\'es pour capturer l'intrus. Selon cette mesure, nous prouvons que notre protocole a un rapport de comp\'etitivit\'e de $3/2$ et que c'est le meilleur ratio atteignable par n'importe quel protocole r\'eparti. En fait, pour tout r\'eseau, notre protocole calcule une strat\'egie dont nous prouvons qu'elle utilise au plus $OPT+1$ agents, o\`u $OPT$ est le nombre minimum d'agents n\'ecessaire pour nettoyer un r\'eseau de facon centralis\'ee et synchrone.},
}
-
R. Chand,
M. Cosnard,
and L. Liquori.
Resource Discovery in the Arigatoni Overlay Network.
In Proceedings of the International Workshop on Innovative Internet Community Systems (I2CS),
pages 13p,
2006.
[PDF
]
@inproceedings{CCL06,
author = {R. Chand and M. Cosnard and L. Liquori},
title = {Resource Discovery in the {A}rigatoni Overlay Network},
booktitle = {Proceedings of the International Workshop on Innovative Internet Community Systems (I2CS)},
OPTseries={Lecture Notes in Informatics},
OPTPUBLISHER = {},
pages = {13p},
year = {2006},
sorte = "conf-int",
PDF = {http://www-sop.inria.fr/mascotte/Luigi.Liquori/PAPERS/i2cs-06.pdf}
}
-
R. Cilibrasi,
Z. Lotker,
A. Navarra,
S. Pérennes,
and P. Vitanyi.
About the Lifespan of Peer to Peer Networks.
In Proceedings of the 10th International Conference On Principles Of Distributed Systems (OPODIS),
volume 4305 of Lecture Notes in Computer Science,
Bordeaux,
pages 290--304,
December 2006.
Springer-Verlag.
[WWW
] [PDF
]
@InProceedings{CLN+06,
sorte = "conf-int",
author = {R. Cilibrasi and Z. Lotker and A. Navarra and S. P\'erennes and P. Vitanyi},
title = {About the {L}ifespan of {P}eer to {P}eer {N}etworks},
booktitle = {Proceedings of the 10th International Conference On Principles Of Distributed Systems (OPODIS)},
OPTcrossref = {},
OPTkey = {},
pages = {290--304},
year = {2006},
OPTeditor = {},
volume = {4305},
OPTnumber = {},
series = {Lecture Notes in Computer Science},
OPTaddress = {},
OPTmonth = {},
OPTorganization = {},
publisher = {Springer-Verlag},
month = {December},
address={Bordeaux},
URL={http://www.opodis.net/},
PDF={ftp://ftp-sop.inria.fr/mascotte/Publications/CLN+06.pdf},
}
-
H. Cirstea,
K. Claude,
L. Liquori,
and B. Wack.
Polymorphic Type Inference for the Rewriting Calculus.
In JFLA: Journées Francophones des Langages Applicatifs,
pages 57--69,
2006.
INRIA.
@INPROCEEDINGS{CLKW06,
sorte = "conf-nat",
AUTHOR = {H. Cirstea and K. Claude and L. Liquori and B. Wack},
TITLE = {Polymorphic Type Inference for the Rewriting Calculus},
YEAR = {2006},
BOOKTITLE = {JFLA: Journ\'ees Francophones des Langages Applicatifs},
PUBLISHER = {INRIA},
pages = {57--69},
}
-
D. Coudert,
S. Pérennes,
H. Rivano,
and M-E. Voge.
Shared Risk Resource Groups and Survivability in Multilayer Networks.
In IEEE-LEOS ICTON / COST 293 GRAAL,
volume 3,
pages 235-238,
June 2006.
Note: Invited Paper.
[PDF
]
| Abstract: |
|
We study the minimization of ADMs (Add-Drop Multiplexers) in Optical WDM Networks with Bidirectional Ring topology considering symmetric shortest path routing and all-to-all unitary requests. We insist on the statement of the problem, which had not been clearly stated before in the bidirectional case. Optimal solutions had not been found up to date. In particular, we study the case C = 2 and C = 3 (giving either optimal constructions or near-optimal solutions) and the case C = k(k 1)/2 (giving optimal decompositions for specific congruence classes of N). We state a general Lower Bound for all the values of C and N, and we improve this Lower Bound for C=2 and C=3 (when N=4t 3). We also include some comments about the simulation of the problem using Linear Programming. |
@INPROCEEDINGS{CPRV06,
author = {D. Coudert and S. P\'erennes and H. Rivano and M-E. Voge},
title = {Shared Risk Resource Groups and Survivability in Multilayer Networks},
booktitle = {IEEE-LEOS ICTON / COST 293 GRAAL},
year = {2006},
volume = {3},
pages = {235-238},
month = jun,
note = {Invited Paper},
sorte = "inv-conf",
abstract = {We study the minimization of ADMs (Add-Drop Multiplexers) in Optical WDM Networks with Bidirectional Ring topology considering symmetric shortest path routing and all-to-all unitary requests. We insist on the statement of the problem, which had not been clearly stated before in the bidirectional case. Optimal solutions had not been found up to date. In particular, we study the case C = 2 and C = 3 (giving either optimal constructions or near-optimal solutions) and the case C = k(k 1)/2 (giving optimal decompositions for specific congruence classes of N). We state a general Lower Bound for all the values of C and N, and we improve this Lower Bound for C=2 and C=3 (when N=4t 3). We also include some comments about the simulation of the problem using Linear Programming.},
optbooktitle = {IEEE/COST 293 annual conference on GRAphs and ALgorithms in communication networks},
pdf = {ftp://ftp-sop.inria.fr/mascotte/personnel/David.Coudert/Publication/CPRV-ICTON-GRAAL06.pdf}
}
-
O. Dalle.
OSA: an Open Component-based Architecture for Discrete-Event Simulation.
In 20th European Conference on Modeling and Simulation (ECMS),
Bonn, Germany,
pages 253--259,
May 2006.
[PDF
]
@InProceedings{Dal06b,
author = {O. Dalle},
title = {{OSA}: an {O}pen {C}omponent-based {A}rchitecture for {D}iscrete-{E}vent Simulation},
booktitle = {20th European Conference on Modeling and Simulation (ECMS)},
OPTcrossref = {},
OPTkey = {},
pages = {253--259},
year = {2006},
OPTeditor = {},
OPTvolume = {},
OPTnumber = {},
OPTseries = {},
address = {Bonn, Germany},
month = {May},
OPTorganization = {},
OPTpublisher = {},
OPTnote = {},
sorte = "conf-int",
PDF = {ftp://ftp-sop.inria.fr/mascotte/Publications/Dal06b.pdf},
OPTannote = {}
}
-
A. Ferreira,
A. Goldman,
and J. Monteiro.
Performance Evaluation of Dynamic Networks using an Evolving Graph Combinatorial Model.
In Proceedings of the 2nd IEEE International Conference on Wireless and Mobile Computing, Networking and Communications (WiMob 2006),
Montreal, CA,
pages 173--180,
June 2006.
Note: Best Student Paper Award.
[WWW
]
@inproceedings{FGM06,
author={A. Ferreira and A. Goldman and J. Monteiro},
title={Performance Evaluation of Dynamic Networks using an Evolving Graph Combinatorial Model},
booktitle={Proceedings of the 2nd {IEEE} International Conference on Wireless and Mobile Computing, Networking and Communications {(WiMob 2006)}},
URL={http://www.congresbcu.com/wimob2006/},
pages={173--180},
month = {June},
year = {2006},
address = {Montreal, CA},
note = {Best Student Paper Award},
sorte = "conf-int"
}
-
F. V. Fomin,
P. Fraigniaud,
and N. Nisse.
Strategies d'encerclement non deterministes.
In 8èmes Rencontres Francophones sur les Aspects Algorithmiques de Télécommunications (AlgoTel),
pages 81-84,
2006.
[WWW
]
| Abstract: |
|
Nous d\'efinissons l'encerclement non-d\'eterministe dans les graphes. Nous montrons comment ce nouvel outil peut \^etre utilis\'e pour la conception d'algorithmes et pour l'analyse combinatoire de la largeur lin\'eaire (pathwidth) comme de la largeur arborescente (treewidth) des graphes. Nous prouvons l'\'equivalence entre cette approche sous forme de ``jeu'' (graph searching) et la d\'ecomposition arborescente $q$-branch\'ee d'un graphe. Cette d\'ecomposition peut \^etre interpr\'et\'ee comme une version param\'etr\'ee des d\'ecompositions arborescente et lin\'eaire qui sont deux cas extr\^emes de la d\'ecomposition arborescente $q$-branch\'ee. L'\'equivalence entre l'encerclement non-d\'eterministe et la d\'ecomposition arborescente $q$-branch\'ee nous permet de proposer un algorithme exact (en temps exponentiel) pour calculer la largeur arborescente $q$-branch\'ee pour tout $q \geq 0$. Cet algorithme est donc valide \`a la fois pour la largeur lin\'eaire et po ur la largeur arborescente. Notre algorithme est aussi rapide que le meilleur algorithme connu pour la largeur lin\'eaire. |
@InProceedings{FFN06,
sorte = "conf-nat",
author = {F. V. Fomin and P. Fraigniaud and N. Nisse},
title = {Strategies d'encerclement non deterministes},
booktitle = {8\`emes Rencontres Francophones sur les Aspects Algorithmiques de T\'el\'ecommunications (AlgoTel)},
year = {2006},
pages = {81-84},
url = {http://algotel2006.lip6.fr/},
pdf = {},
abstract = {Nous d\'efinissons l'encerclement non-d\'eterministe dans les graphes. Nous montrons comment ce nouvel outil peut \^etre utilis\'e pour la conception d'algorithmes et pour l'analyse combinatoire de la largeur lin\'eaire (pathwidth) comme de la largeur arborescente (treewidth) des graphes. Nous prouvons l'\'equivalence entre cette approche sous forme de ``jeu'' (graph searching) et la d\'ecomposition arborescente $q$-branch\'ee d'un graphe. Cette d\'ecomposition peut \^etre interpr\'et\'ee comme une version param\'etr\'ee des d\'ecompositions arborescente et lin\'eaire qui sont deux cas extr\^emes de la d\'ecomposition arborescente $q$-branch\'ee. L'\'equivalence entre l'encerclement non-d\'eterministe et la d\'ecomposition arborescente $q$-branch\'ee nous permet de proposer un algorithme exact (en temps exponentiel) pour calculer la largeur arborescente $q$-branch\'ee pour tout $q \geq 0$. Cet algorithme est donc valide \`a la fois pour la largeur lin\'eaire et po ur la largeur arborescente. Notre algorithme est aussi rapide que le meilleur algorithme connu pour la largeur lin\'eaire.},
}
-
P. Fraigniaud and N. Nisse.
Connected Treewidth and Connected Graph Searching.
In Proceeding of the 7th Latin American Symposium on Theoretical Informatics (LATIN),
pages 479-490,
2006.
[WWW
] [PDF
]
| Abstract: |
|
We give a constructive proof of the equality between \emph{treewidth} and \emph{connected treewidth}. More precisely, we describe an $O(nk^3)$-time algorithm that, given any $n$-node width-$k$ tree-decomposition of a connected graph $G$, returns a connected tree-decomposition of $G$ of width $\leq k$. The equality between treewidth and connected treewidth finds applications in \emph{graph searching} problems. First, using equality between treewidth and connected treewidth, we prove that the \emph{connected} search number $\cs(G)$ of a connected graph $G$ is at most $\log{n}+1$ times larger than its search number. Second, using our constructive proof of equality between treewidth and connected treewidth, we design an \\$O(\log n\sqrt{\log OPT})$-approximation algorithm for connected search, running in time $O(t(n)+nk^3\log^{3/2}k+m\log n)$ for $n$-node $m$-edge connected graphs of treewidth at most $k$, where $t(n)$ is the time-complexity of the fastest algorith m for approximating the treewidth, up to a factor $O(\sqrt{\log OPT})$. |
@inproceedings{FrNi06b,
sorte = "conf-int",
author = {P. Fraigniaud and N. Nisse},
title = {Connected Treewidth and Connected Graph Searching},
booktitle = {Proceeding of the 7th Latin American Symposium on Theoretical Informatics (LATIN)},
year = {2006},
pages = {479-490},
abstract = {We give a constructive proof of the equality between \emph{treewidth} and \emph{connected treewidth}. More precisely, we describe an $O(nk^3)$-time algorithm that, given any $n$-node width-$k$ tree-decomposition of a connected graph $G$, returns a connected tree-decomposition of $G$ of width $\leq k$. The equality between treewidth and connected treewidth finds applications in \emph{graph searching} problems. First, using equality between treewidth and connected treewidth, we prove that the \emph{connected} search number $\cs(G)$ of a connected graph $G$ is at most $\log{n}+1$ times larger than its search number. Second, using our constructive proof of equality between treewidth and connected treewidth, we design an \\$O(\log n\sqrt{\log OPT})$-approximation algorithm for connected search, running in time $O(t(n)+nk^3\log^{3/2}k+m\log n)$ for $n$-node $m$-edge connected graphs of treewidth at most $k$, where $t(n)$ is the time-complexity of the fastest algorith m for approximating the treewidth, up to a factor $O(\sqrt{\log OPT})$. },
url = {http://www.informatik.uni-trier.de/~ley/db/conf/latin/latin2006.shtml},
pdf = {http://www-sop.inria.fr/members/Nicolas.Nisse/publications/Latin06.ps}
}
-
P. Fraigniaud and N. Nisse.
Monotony Properties of Connected Visible Graph Searching.
In Proceedings of 32nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG),
volume 5911 of Lecture Notes in Computer Science,
Montpellier, France,
pages 229-240,
June 2006.
Springer.
| Abstract: |
|
{Search games are attractive for their correspondence with classical width parameters. For instance, the \emph{invisible} search number (a.k.a. \emph{node} search number) of a graph is equal to its pathwidth plus~1, and the \emph{visible} search number of a graph is equal to its treewidth plus~1. The \emph{connected} variants of these games ask for search strategies that are connected, i.e., at every step of the strategy, the searched part of the graph induces a connected subgraph. We focus on \emph{monotone} search strategies, i.e., strategies for which every node is searched exactly once. The monotone connected visible search number of an $n$-node graph is at most $O(\log n)$ times its visible search number. First, we prove that this logarithmic bound is tight. Precisely, we prove that there is an infinite family of graphs for which the ratio monotone connected visible search number over visible search number is $\Omega(\log n)$. Second, we prove that, as opposed to the non-connected variant of visible graph searching, ``recontamination helps" for connected visible search. Precisely, we prove that, for any $k \geq 4$, there exists a graph with connected visible search number at most $k$, and monotone connected visible search number $>k$.}, url = {http://www.informatik.uni-trier.de/~ley/db/conf/wg/wg2006.shtml}, pdf = {http://www-sop.inria.fr/members/Nicolas.Nisse/publications/WG06_nisse.ps} |
@inproceedings{FrNi06a,
sorte = "conf-int",
author = {P. Fraigniaud and N. Nisse},
title = {Monotony Properties of Connected Visible Graph Searching},
booktitle = {Proceedings of 32nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG)},
year = {2006},
month = jun,
pages = {229-240},
volume = {5911},
series = {Lecture Notes in Computer Science},
publisher = {Springer},
address = {Montpellier, France},
abstract = {Search games are attractive for their correspondence with classical width parameters. For instance, the \emph{invisible} search number (a.k.a. \emph{node} search number) of a graph is equal to its pathwidth plus~1, and the \emph{visible} search number of a graph is equal to its treewidth plus~1. The \emph{connected} variants of these games ask for search strategies that are connected, i.e., at every step of the strategy, the searched part of the graph induces a connected subgraph. We focus on \emph{monotone} search strategies, i.e., strategies for which every node is searched exactly once. The monotone connected visible search number of an $n$-node graph is at most $O(\log n)$ times its visible search number. First, we prove that this logarithmic bound is tight. Precisely, we prove that there is an infinite family of graphs for which the ratio monotone connected visible search number over visible search number is $\Omega(\log n)$. Second, we prove that, as opposed to the non-connected variant of visible graph searching, ``recontamination helps" for connected visible search. Precisely, we prove that, for any $k \geq 4$, there exists a graph with connected visible search number at most $k$, and monotone connected visible search number $>k$.}, url = {http://www.informatik.uni-trier.de/~ley/db/conf/wg/wg2006.shtml}, pdf = {http://www-sop.inria.fr/members/Nicolas.Nisse/publications/WG06_nisse.ps}
}
-
J. Galtier.
Adaptive power and transmission rate control in cellular CDMA networks.
In IEEE GLOBECOM,
pages 6p,
2006.
[PDF
]
@InProceedings{Gal06b,
author = {J. Galtier},
title = {Adaptive power and transmission rate control in cellular {CDMA} networks},
booktitle = {IEEE GLOBECOM},
pages = {6p},
year = {2006},
sorte = "conf-int",
pdf = {ftp://ftp-sop.inria.fr/mascotte/Publications/Gal06b.pdf},
}
-
J. Galtier.
Analysis of the slotted non-persistent CSMA protocol with poissonian packet size using a semi-Markov graph representation.
In 8th International Conference on Transparent Optical Networks,
volume 3,
pages 258--262,
June 2006.
IEEE.
[PDF
]
@InProceedings{Gal06a,
author = {J. Galtier},
title = {Analysis of the slotted non-persistent {CSMA} protocol with poissonian packet size using a semi-Markov graph representation},
booktitle = {8th International Conference on Transparent Optical Networks},
pages = {258--262},
year = {2006},
volume = {3},
month = {June},
organization = {IEEE},
sorte = "conf-int",
pdf = {ftp://ftp-sop.inria.fr/mascotte/Publications/Gal06a.pdf},
}
-
F. Giroire.
Directions to use Probabilistic Algorithms for Cardinality for DNA Analysis.
In Journées Ouvertes Biologie Informatique Mathématiques (JOBIM 2006),
pages 3-5,
July 2006.
[PDF
]
| Abstract: |
|
Probabilistic algorithms for cardinality allow to estimate the number of distinct words of very large multisets. Best of them are very fast (only few tens of CPU operations per element) and use constant memory (standard error of $c \sqrt M$ attained using $M$ units of memory) to be compared with the linear memory used by exact algorithms. Hence they allow to do multiple experiments in few minutes with few KiloBytes on files of several GigaBytes that would be unfeasible with exact counting algorithms. Such algorithms are used here to analyze base correlation in human genome. |
@inproceedings{Gir06a,
author = {F. Giroire},
title = {Directions to use Probabilistic Algorithms for Cardinality for {DNA} Analysis},
booktitle = {Journ\'ees Ouvertes Biologie Informatique Math\'ematiques (JOBIM 2006)},
year = {2006},
month = {July},
pages = {3-5},
pdf = {http://www-sop.inria.fr/members/Frederic.Giroire/publis/Gir06.pdf},
abstract = {Probabilistic algorithms for cardinality allow to estimate the number of distinct words of very large multisets. Best of them are very fast (only few tens of CPU operations per element) and use constant memory (standard error of $c \sqrt M$ attained using $M$ units of memory) to be compared with the linear memory used by exact algorithms. Hence they allow to do multiple experiments in few minutes with few KiloBytes on files of several GigaBytes that would be unfeasible with exact counting algorithms. Such algorithms are used here to analyze base correlation in human genome.},
}
-
L. Hogie,
Pascal Bouvry,
and Frédéric Guinand.
An Overview of MANETs Simulation.
In L. Brim and I. Linden, editors,
Electronic Notes in Theoretical Computer Science, in the proceedings of MTCoord'05,
volume 150 of LNCS,
Namur, Belgium,
pages 81--101,
March 2006.
Elsevier.
[WWW
]
| Abstract: |
|
Mobile Ad hoc NETworks (MANETs) are dynamic networks populated by mobile stations. Stations in MANETs are usually laptops, PDAs or mobile phones. These devices feature Bluetooth and/or IEEE 802.11 (WiFi) network interfaces and communicate in a decentralized manner. Mobility is a key feature of MANETs. Because of their high cost and their lack of flexibility of such networks, experimentation is mostly achievable through simulation. Numerous tools exist for MANETs simulation, including ns-2 and GloMoSim which are the two most popular ones. This paper provides a State of the Art of MANETs simulators and associated simulation techniques. First it gives an overview of the domain. Then it provides a map of the main characteristics that MANETs simulation tools should feature and the current support of these. Finally, a description for each simulator is provided, including an explanation of what make them appealing solutions. |
@INPROCEEDINGS{HBG05,
author = {L. Hogie and Pascal Bouvry and Fr{\'e}d{\'e}ric Guinand},
title = {An Overview of MANETs Simulation},
booktitle = {Electronic Notes in Theoretical Computer Science, in the proceedings of MTCoord'05},
year = {2006},
editor = {L. Brim and I. Linden},
volume = {150},
series = {LNCS},
pages = {81--101},
address = {Namur, Belgium},
month = {March},
publisher = {Elsevier},
abstract = {Mobile Ad hoc NETworks (MANETs) are dynamic networks populated by mobile stations. Stations in MANETs are usually laptops, PDAs or mobile phones. These devices feature Bluetooth and/or IEEE 802.11 (WiFi) network interfaces and communicate in a decentralized manner. Mobility is a key feature of MANETs. Because of their high cost and their lack of flexibility of such networks, experimentation is mostly achievable through simulation. Numerous tools exist for MANETs simulation, including ns-2 and GloMoSim which are the two most popular ones. This paper provides a State of the Art of MANETs simulators and associated simulation techniques. First it gives an overview of the domain. Then it provides a map of the main characteristics that MANETs simulation tools should feature and the current support of these. Finally, a description for each simulator is provided, including an explanation of what make them appealing solutions.},
doi = {10.1016/j.entcs.2005.12.025},
url = {http://www.sciencedirect.com/science?_ob=MImg&_imagekey=B75H1-4JCCCYV-7-1&_cdi=13109&_user=6068170&_pii=S1571066106001010&_orig=search&_coverDate=030.00000009-16231083800624715025648228832155020226166892719138018421525037632987473280314397391192269858494702975413828793994344961730315854330232890054744206295222504730102436050490447205944018758853219057263022459675248963747430121648560444313413255982990181978237473570041841837066007183829415589688357099523473932288.0000002006&_sk=998499998&view=c&wchp=dGLzVlb-zSkzk&md5=e28496e51e1f2587eb45bf5557c533fd&ie=/sdarticle.pdf},
OPTx-editorial-board={yes},
OPTx-proceedings={no},
OPTx-international-audience={yes},
}
-
L. Hogie,
P. Bouvry,
F. Guinand,
G. Danoy,
and E. Alba.
A Bandwidth-Efficient Broadcasting Protocol for Mobile Multi-hop Ad hoc Networks.
In ICN/ICONS/MCL '06: Proceedings of the International Conference on Networking, International Conference on Systems and International Conference on Mobile Communications and Learning Technologies,
pages 71-71,
October 2006.
IEEE Computer Society.
[WWW
]
| Abstract: |
|
This paper presents a new broadcasting protocol called Delayed Flooding with Cumulative Neighborhood (DFCN) designed for wireless ad hoc networks. DFCN enables bandwidth-efficient broadcasting in wide area network composed of large number of mobile devices. The protocol was validated trough simulation which proved its efficiency and cost-effectiveness. Comparison with other well known protocols has shown that the proposed protocol outperforms them in such terms as a number of emissions and redundant receptions. |
@INPROCEEDINGS{HBG+b,
OPTauthor = {L. Hogie and Pascal Bouvry and Fr{\'e}d{\'e}ric Guinand and Gr{\'e}goire Danoy and Enrique Alba},
author = {L. Hogie and P. Bouvry and F. Guinand and G. Danoy and E. Alba},
title = {A Bandwidth-Efficient Broadcasting Protocol for Mobile Multi-hop Ad hoc Networks},
booktitle = {ICN/ICONS/MCL '06: Proceedings of the International Conference on Networking, International Conference on Systems and International Conference on Mobile Communications and Learning Technologies},
year = {2006},
pages = {71-71},
month = {October},
publisher = {IEEE Computer Society},
abstract = {This paper presents a new broadcasting protocol called Delayed Flooding with Cumulative Neighborhood (DFCN) designed for wireless ad hoc networks. DFCN enables bandwidth-efficient broadcasting in wide area network composed of large number of mobile devices. The protocol was validated trough simulation which proved its efficiency and cost-effectiveness. Comparison with other well known protocols has shown that the proposed protocol outperforms them in such terms as a number of emissions and redundant receptions.},
doi = {10.1109/ICNICONSMCL.2006.1},
timestamp = {2006.09.19},
url = {http://pascal.bouvry.org/ftp/icn2006.pdf},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
sorte = "conf-int",
}
-
L. Hogie,
P. Bouvry,
F. Guinand,
G. Danoy,
and E. Alba.
Simulating Realistic Mobility Models for Large Heterogeneous MANETs.
In Demo proceeding of the 9th ACM/IEEE International Symposium on Modeling, Analysis and Simulation of Wireless and Mobile Systems (MSWIM'06),
pages 1p,
October 2006.
IEEE.
[WWW
]
| Abstract: |
|
Mobile ad hoc networks (MANETs) are composed of communicat- ing mobile devices capable of spontaneously interconnecting without any pre-existing infrastructure. The wide spread of mobile devices(i.e. phones, PDAs, laptops) enables the deployment of metropolitan ad hoc networks, referred to as MobileMANs. Until recently, MobileMAN simu- lation suffered from a lack of appropriate tools. Therefore a new class of simulators dedicated to MobileMANs is appearing. This paper presents Mad hoc, a MANETs simulator which belongs to this class. In addi- tion to providing particular models for the simulation of numerous nodes evolving in a metropolitan environment, Mad hoc comes with appropri- ate tools for the development and the monitoring of ad hoc applications. Mad hocÃs applications are presented. |
@INPROCEEDINGS{HBG+06a,
OPTauthor = {L. Hogie and Pascal Bouvry and Fr{\'e}d{\'e}ric Guinand and Gr{\'e}goire Danoy and Enrique Alba},
author = {L. Hogie and P. Bouvry and F. Guinand and G. Danoy and E. Alba},
title = {Simulating Realistic Mobility Models for Large Heterogeneous {MANET}s},
booktitle = {Demo proceeding of the 9th ACM/IEEE International Symposium on Modeling, Analysis and Simulation of Wireless and Mobile Systems (MSWIM'06)},
year = {2006},
pages = {1p},
month = {October},
publisher = {IEEE},
abstract = {Mobile ad hoc networks (MANETs) are composed of communicat- ing mobile devices capable of spontaneously interconnecting without any pre-existing infrastructure. The wide spread of mobile devices(i.e. phones, PDAs, laptops) enables the deployment of metropolitan ad hoc networks, referred to as MobileMANs. Until recently, MobileMAN simu- lation suffered from a lack of appropriate tools. Therefore a new class of simulators dedicated to MobileMANs is appearing. This paper presents Mad hoc, a MANETs simulator which belongs to this class. In addi- tion to providing particular models for the simulation of numerous nodes evolving in a metropolitan environment, Mad hoc comes with appropri- ate tools for the development and the monitoring of ad hoc applications. Mad hocÃs applications are presented.},
url = {http://www.google.fr/url?sa=t&source=web&ct=res&cd=1&ved=0CBoQFjAA&url=http0X1.2AC02P-885-16231083800624715025648228832155020226166892719138018421525037632987473280314397391192269858494702975413828793994344961730315854330232890054744206295222504730102436050490447205944018758853219057263022459675248963747430121648560444313413255982990181978237473570041841837066007183829415589688357099523473932288.0000000.000000www-valoria.univ-ubs.fr0.000000SARAH0.000000pdf0.000000Hogie_mswim06.pdf&ei=MRjoS-GFN4-C_QbZ9MW7BA&usg=AFQjCNG_0DVrdUMl_h00MOvH2fgUX6osDQ},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
sorte = "conf-int",
}
-
L. Liquori,
F. Honsell,
and R. Redamalla.
A Language for Verification and Manipulation of Web Documents.
In Proceedings of the International Workshop on Automated Specification and Verification of Web Sites (WWV 2005),
volume 157 of Electronic Notes in Theoretical Computer Science,
pages 67--78,
2006.
Elsevier.
@InProceedings{LHR06,
sorte = "conf-int",
author = {L. Liquori and F. Honsell and R. Redamalla},
title = {A Language for Verification and Manipulation of Web Documents},
booktitle = {Proceedings of the International Workshop on Automated Specification and Verification of Web Sites (WWV 2005)},
OPTcrossref = {},
OPTkey = {},
pages = {67--78},
year = {2006},
OPTeditor = {},
volume = {157},
number = {2},
series = {Electronic Notes in Theoretical Computer Science},
OPTaddress = {},
OPTmonth = {},
OPTorganization = {},
publisher = {Elsevier},
OPTnote = {},
OPTannote = {},
doi = "DOI: j.entcs.2005.12.046",
}
-
L. Liquori.
iRho: the Software: [System Description].
In Proceedings of the First International Workshop on Developments in Computational Models (DCM 2005),
volume 135 of Electronic Notes in Theoretical Computer Science,
pages 85--94,
2006.
Elsevier.
[PDF
]
@InProceedings{Liq06,
sorte = "conf-int",
author = {L. Liquori},
title = {i{R}ho: the Software: [System Description]},
booktitle = {Proceedings of the First International Workshop on Developments in Computational Models (DCM 2005) },
OPTcrossref = {},
OPTkey = {},
pages = {85--94},
year = {2006},
OPTeditor = {},
volume = {135},
number = {3},
series = {Electronic Notes in Theoretical Computer Science},
OPTaddress = {},
OPTmonth = {},
OPTorganization = {},
publisher = {Elsevier},
OPTnote = {},
OPTannote = {},
PDF = {http://www-sop.inria.fr/mascotte/Luigi.Liquori/PAPERS/dcm-06.pdf},
issn = "1571-0661",
doi = "DOI: 10.1016/j.entcs.2005.09.023",
}
-
F. Luna,
A. J. Nebro,
B. Dorronsoro,
E. Alba,
P. Bouvry,
and L. Hogie.
Optimal Broadcasting in Metropolitan MANETs Using Multiobjective Scatter Search.
In Applications of Evolutionary Computing,
volume 3907 of Lecture Notes in Computer Science,
pages 255-266,
March 2006.
Springer.
[WWW
]
| Abstract: |
|
Mobile Ad-hoc Networks (MANETs) are composed of a set of communicating devices which are able to spontaneously interconnect without any pre-existing infrastructure. In such scenario, broadcasting becomes an operation of capital importance for the own existence and operation of the network. Optimizing a broadcasting strategy in MANETs is a multiobjective problem accounting for three goals: reaching as many stations as possible, minimizing the network utilization, and reducing the makespan. In this paper, we face this multiobjective problem with a state-of-the-art multiobjective scatter search algorithm called AbSS (Archive-based Scatter Search) that computes a Pareto front of solutions to empower a human designer with the ability of choosing the preferred configuration for the network. Results are compared against those obtained with the previous proposal used for solving the problem, a cellular multiobjective genetic algorithm (cMOGA). We conclude that AbSS outperforms cMOGA with respect to three different metrics. |
@INPROCEEDINGS{LND+06,
OPTauthor = {Francisco Luna and Antonio J. Nebro and Bernab{\'e} Dorronsoro and Enrique Alba and Pascal Bouvry and L. Hogie},
author = {F. Luna and A. J. Nebro and B. Dorronsoro and E. Alba and P. Bouvry and L. Hogie},
title = {Optimal Broadcasting in Metropolitan {MANET}s Using Multiobjective Scatter Search},
booktitle = {Applications of Evolutionary Computing},
year = {2006},
volume = {3907},
series = {Lecture Notes in Computer Science},
publisher = {Springer},
pages = {255-266},
month = mar,
sorte = "conf-int",
abstract = {Mobile Ad-hoc Networks (MANETs) are composed of a set of communicating devices which are able to spontaneously interconnect without any pre-existing infrastructure. In such scenario, broadcasting becomes an operation of capital importance for the own existence and operation of the network. Optimizing a broadcasting strategy in MANETs is a multiobjective problem accounting for three goals: reaching as many stations as possible, minimizing the network utilization, and reducing the makespan. In this paper, we face this multiobjective problem with a state-of-the-art multiobjective scatter search algorithm called AbSS (Archive-based Scatter Search) that computes a Pareto front of solutions to empower a human designer with the ability of choosing the preferred configuration for the network. Results are compared against those obtained with the previous proposal used for solving the problem, a cellular multiobjective genetic algorithm (cMOGA). We conclude that AbSS outperforms cMOGA with respect to three different metrics.},
bibsource = {DBLP, http://dblp.uni-trier.de},
doi = {10.1007/11732242},
url = {http://www.springerlink.com/content/qk6747wq32478r42/fulltext.pdf},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
}
-
J. Moulierac,
A. Guitton,
and M. Molnár.
On the number of MPLS LSP using Multicast Tree Aggregation.
In IEEE Globecom,
pages 5p,
November 2006.
[PDF
]
| Abstract: |
|
Multicast tree aggregation is an efficient proposition that can solve the multicast forwarding state scalability problem. Existing works on tree aggregation have focused on developing and simulating protocols that build trees dynamically. However, the underlying problem of the impact of the tree construction algorithm on the performance of the protocols remains untouched. In this paper, we propose a study on the number of trees that need to be configured in a domain depending on the tree construction algorithm. We ran extensive simulations on several real domains and with different tree construction algorithms. Our results show that for a given set of multicast groups, even when this set includes all the possible groups, the number of trees that need to be configured is small. This allows a network administrator to configure off-line all these trees in order to maintain a stable set of trees and to have knowledge of the routes used by the multicast packets. Knowing the set of all the possible trees is also useful to determine the best subset to configure and to give an upper bound of the number of different trees. |
@inproceedings{MGM06b,
sorte = "conf-int",
author = {J. Moulierac and A. Guitton and M. Moln\'ar},
title = {{On the number of MPLS LSP using Multicast Tree Aggregation}},
booktitle = {IEEE Globecom},
year = {2006},
pages = {5p},
month = {November},
PDF={ftp://ftp-sop.inria.fr/mascotte/personnel/Joanna.Moulierac/pdf/moulierac06number.pdf},
ABSTRACT={Multicast tree aggregation is an efficient proposition that can solve the multicast forwarding state scalability problem. Existing works on tree aggregation have focused on developing and simulating protocols that build trees dynamically. However, the underlying problem of the impact of the tree construction algorithm on the performance of the protocols remains untouched. In this paper, we propose a study on the number of trees that need to be configured in a domain depending on the tree construction algorithm. We ran extensive simulations on several real domains and with different tree construction algorithms. Our results show that for a given set of multicast groups, even when this set includes all the possible groups, the number of trees that need to be configured is small. This allows a network administrator to configure off-line all these trees in order to maintain a stable set of trees and to have knowledge of the routes used by the multicast packets. Knowing the set of all the possible trees is also useful to determine the best subset to configure and to give an upper bound of the number of different trees.}
}
-
J. Moulierac,
A. Guitton,
and M. Molnár.
Multicast Tree Aggregation in Large Domains.
In IFIP Networking,
number 3976,
pages 691--702,
2006.
[PDF
]
| Abstract: |
|
Tree aggregation is an ecient proposition that can solve the problem of multicast forwarding state scalability. The main idea of tree aggregation is to force several groups to share the same delivery tree: in this way, the number of multicast forwarding states per router is reduced. Unfortunately, when achieving tree aggregation in large do- mains, few groups share the same tree and the aggregation ratio is small. In this paper, we propose a new algorithm called TALD (Tree Aggrega- tion in Large Domains) that achieves tree aggregation in domains with a large number of nodes. The principle of TALD is to divide the domain into several sub-domains and to achieve the aggregation in each of the sub-domain separately. In this way, there is possible aggregation in each of the sub-domain and the number of forwarding states is signicantly reduced. We show the performance of our algorithm by simulations on a Rocketfuel network of 200 routers. |
@inproceedings{MGM06c,
sorte = "conf-int",
author = {J. Moulierac and A. Guitton and M. Moln\'ar},
title = {{Multicast Tree Aggregation in Large Domains}},
booktitle = {IFIP Networking},
number = {3976},
pages= {691--702},
year = {2006},
PDF={ftp://ftp-sop.inria.fr/mascotte/personnel/Joanna.Moulierac/pdf/moulierac06tree.pdf},
ABSTRACT={Tree aggregation is an ecient proposition that can solve the problem of multicast forwarding state scalability. The main idea of tree aggregation is to force several groups to share the same delivery tree: in this way, the number of multicast forwarding states per router is reduced. Unfortunately, when achieving tree aggregation in large do- mains, few groups share the same tree and the aggregation ratio is small. In this paper, we propose a new algorithm called TALD (Tree Aggrega- tion in Large Domains) that achieves tree aggregation in domains with a large number of nodes. The principle of TALD is to divide the domain into several sub-domains and to achieve the aggregation in each of the sub-domain separately. In this way, there is possible aggregation in each of the sub-domain and the number of forwarding states is signicantly reduced. We show the performance of our algorithm by simulations on a Rocketfuel network of 200 routers.}
}
-
J. Moulierac and M. Molnàr.
Active Monitoring of Link Delays in Case of Asymmetric Routes.
In IEEE International Conference on Networking (ICN),
pages 6p,
April 2006.
[PDF
]
| Abstract: |
|
Network monitoring receives signicant interest recently. Indeed, knowledge of link availability and link characteristics is of signicant importance in order to provide efcient routing. In this paper, we consider active network monitoring of link delays in a Service Provider or Enterprise IP network using round trip delays. Our proposition guarantees that all links are monitored contrary to previous propositions. Indeed, previous propositions assume symmetric routing in networks when placing the monitoring stations. With this assumption, round trips may be different when routes are asymmetric and link delays are not signi cant. We say that links are not monitored in this case. Previous propositions do not monitor 5.76\0f links in average and 10\ 144878418n worst cases during our simulations while we monitor always 100\0f links. Moreover, in our proposition, the amount of trafc is reduced and the measures are more precise since the distance from a monitoring station (beacon) to the edges is limited by a given bound. Finally, we show during the simulations that the set of beacons is rather stable in case of link failures. |
@inproceedings{MM06,
sorte = "conf-int",
author = {J. Moulierac and M. Moln\`ar},
title = {Active Monitoring of Link Delays in Case of Asymmetric Routes},
booktitle = {IEEE International Conference on Networking (ICN)},
year = {2006},
pages = {6p},
month = {April},
PDF = {ftp://ftp-sop.inria.fr/mascotte/personnel/Joanna.Moulierac/pdf/moulierac06active.pdf},
ABSTRACT={Network monitoring receives signicant interest recently. Indeed, knowledge of link availability and link characteristics is of signicant importance in order to provide efcient routing. In this paper, we consider active network monitoring of link delays in a Service Provider or Enterprise IP network using round trip delays. Our proposition guarantees that all links are monitored contrary to previous propositions. Indeed, previous propositions assume symmetric routing in networks when placing the monitoring stations. With this assumption, round trips may be different when routes are asymmetric and link delays are not signi cant. We say that links are not monitored in this case. Previous propositions do not monitor 5.76\0f links in average and 10\ 144878418n worst cases during our simulations while we monitor always 100\0f links. Moreover, in our proposition, the amount of trafc is reduced and the measures are more precise since the distance from a monitoring station (beacon) to the edges is limited by a given bound. Finally, we show during the simulations that the set of beacons is rather stable in case of link failures.}
}
-
J. Moulierac.
On the number of multicast aggregated trees in a domain.
In 2nd Student Workshop of IEEE Infocom,
pages 2p,
April 2006.
[PDF
]
| Abstract: |
|
Multicast tree aggregation is an efficient proposition that can solve the multicast forwarding state scalability problem. Existing works on tree aggregation have focused on developing and simulating protocols that build trees dynamically. However, the underlying problem of the impact of the tree construction algorithm on the performance of the protocols remains untouched. In this paper, we propose a study on the number of trees that need to be configured in a domain depending on the tree construction algorithm. We ran extensive simulations on several real domains and with different tree construction algorithms. Our results show that for a given set of multicast groups, even when this set includes all the possible groups, the number of trees that need to be configured is small. This allows a network administrator to configure off-line all these trees in order to maintain a stable set of trees and to have knowledge of the routes used by the multicast packets. Knowing the set of all the possible trees is also useful to determine the best subset to configure and to give an upper bound of the number of different trees. |
@inproceedings{Mou06,
sorte = "conf-int",
author = {J. Moulierac},
title = {On the number of multicast aggregated trees in a domain},
booktitle = {2nd Student Workshop of {IEEE} {I}nfocom},
pages = {2p},
year = {2006},
month = {April},
PDF = {ftp://ftp-sop.inria.fr/mascotte/personnel/Joanna.Moulierac/pdf/moulierac06number.pdf},
ABSTRACT={Multicast tree aggregation is an efficient proposition that can solve the multicast forwarding state scalability problem. Existing works on tree aggregation have focused on developing and simulating protocols that build trees dynamically. However, the underlying problem of the impact of the tree construction algorithm on the performance of the protocols remains untouched. In this paper, we propose a study on the number of trees that need to be configured in a domain depending on the tree construction algorithm. We ran extensive simulations on several real domains and with different tree construction algorithms. Our results show that for a given set of multicast groups, even when this set includes all the possible groups, the number of trees that need to be configured is small. This allows a network administrator to configure off-line all these trees in order to maintain a stable set of trees and to have knowledge of the routes used by the multicast packets. Knowing the set of all the possible trees is also useful to determine the best subset to configure and to give an upper bound of the number of different trees.}
}
-
N. Nepomuceno,
P. Rogério Pinheiro,
and A. L. V. Coelho.
Metaheurìstica e Programação Linear Inteira: Um Algoritmo Hìbrido para o Problema de Carregamento de Contêineres.
In XIII Congreso Latino-Iberoamericano de Investigación Operativa (CLAIO),
Montevideo, Uruguay,
pages 6p,
2006.
[PDF
]
@inproceedings{NPC06a,
sorte = "conf-int",
OPTauthor = {Napole{\~a}o Nepomuceno and Pl{\'a}cido Rog{\'e}rio Pinheiro and Andr{\'e} L. V. Coelho},
author = {Nepomuceno, N. and Rog{\'e}rio Pinheiro, P. and Coelho, A. L. V.},
title = {Metaheur{\'i}stica e Programa\c{c}\~ao Linear Inteira: Um Algoritmo H{\'i}brido para o Problema de Carregamento de Cont\^eineres},
booktitle = {XIII Congreso Latino-Iberoamericano de Investigaci\'on Operativa (CLAIO) },
address= {Montevideo, Uruguay},
pages = {6p},
year = {2006},
pdf = {ftp://ftp-sop.inria.fr/mascotte/Publications/NPC06.pdf},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
x-pays = {BR}
}
-
N. Nepomuceno,
P. Rogério Pinheiro,
and A. L. V. Coelho.
Aplicação de uma Metodologia Hìbrida ao Problema de Carregamento de Contêineres.
In XXXVIII Simpósio Brasileiro de Pesquisa Operacional (SBPO),
Goiania, Brazil,
pages 1596-1603,
2006.
[PDF
]
@inproceedings{NPC06b,
sorte = "conf-nat",
OPTauthor = {Napole{\~a}o Nepomuceno and Pl{\'a}cido Rog{\'e}rio Pinheiro and Andr{\'e} L. V. Coelho},
author = {Nepomuceno, N. and Rog{\'e}rio Pinheiro, P. and Coelho, A. L. V. },
title = {Aplica\c{c}\~ao de uma Metodologia H{\'i}brida ao Problema de Carregamento de Cont\^eineres},
booktitle = {XXXVIII Simp\'osio Brasileiro de Pesquisa Operacional (SBPO)},
address= {Goiania, Brazil},
year = {2006},
pages = {1596-1603},
pdf = {ftp://ftp-sop.inria.fr/mascotte/Publications/NPC06b.pdf},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={no},
x-pays = {BR}
}
-
H. Rivano,
F. Theoleyre,
and F. Valois.
Capacity Evaluation Framework and Validation of Self-Organized Routing Schemes.
In Workshop on Wireless Ad-hoc and Sensor Networks (IWWAN 2006),
volume 3,
pages 779--785,
28-28 Sept. 2006.
IEEE.
[WWW
] [PDF
]
| Abstract: |
|
Assuming a given network topology and a routing protocol, this work is focused on the capacity evaluation of routing protocols based on either a self-organization scheme or a flat approach. To reach this goal, we propose to use linear-programming formulation to model radio resource sharing as linear constraints. Four models are detailed to evaluate the capacity of any routing scheme in wireless multihops networks. First, two models of fairness are proposed: either each node has a fair access to the channel, or the fairness is among the radio links. Besides, a pessimistic and an optimistic scenarios of spatial re-utilization of the medium are proposed, yielding a lower bound and an upper bound on the network capacity for each fairness case. Finally, using this model, we provide a comparative analysis of some flat and self-organized routing protocols |
@INPROCEEDINGS{RTV06a,
sorte = "conf-int",
author = {Rivano, H. and Theoleyre, F. and Valois, F.},
title = {Capacity Evaluation Framework and Validation of Self-Organized Routing Schemes},
booktitle = {Workshop on Wireless Ad-hoc and Sensor Networks (IWWAN 2006)},
publisher = {IEEE},
year = {2006},
volume = {3},
pages = {779--785},
month = {28-28 Sept.},
abstract = {Assuming a given network topology and a routing protocol, this work is focused on the capacity evaluation of routing protocols based on either a self-organization scheme or a flat approach. To reach this goal, we propose to use linear-programming formulation to model radio resource sharing as linear constraints. Four models are detailed to evaluate the capacity of any routing scheme in wireless multihops networks. First, two models of fairness are proposed: either each node has a fair access to the channel, or the fairness is among the radio links. Besides, a pessimistic and an optimistic scenarios of spatial re-utilization of the medium are proposed, yielding a lower bound and an upper bound on the network capacity for each fairness case. Finally, using this model, we provide a comparative analysis of some flat and self-organized routing protocols},
pdf = {ftp://ftp-sop.inria.fr/mascotte/Herve.Rivano/Biblio/rtv06.pdf},
url = {http://www.ctr.kcl.ac.uk/IWWAN2006/}
}
-
M.-E. Voge.
How to transform a multilayer network into a colored graph.
In IEEE-LEOS ICTON/COST 293 GRAAL,
volume 3,
pages 116--119,
June 2006.
@InProceedings{Vog06b,
sorte = "conf-int",
author = {M.-E. Voge},
title = {How to transform a multilayer network into a colored graph},
booktitle = {IEEE-LEOS ICTON/COST 293 GRAAL},
OPTbooktitle = {IEEE/COST 293 annual conference on GRAphs and ALgorithms in communication networks},
pages = {116--119},
volume = {3},
year = {2006},
month = {June},
}
-
M.-E. Voge.
Graphes Colorés - Arbre Couvrant Coloré.
In Huitièmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications (AlgoTel'06),
Trégastel,
pages 41--44,
May 2006.
[WWW
]
@inproceedings{Vog06a,
sorte = "conf-nat",
author={M.-E. Voge},
title={Graphes Color\'es - Arbre Couvrant Color\'e},
booktitle={Huiti\`emes Rencontres Francophones sur les Aspects Algorithmiques des T\'el\'ecommunications (AlgoTel'06)},
address={Tr\'egastel},
month={May},
year={2006},
pages={41--44},
URL={http://algotel2006.lip6.fr/},
}
-
O. Amini,
F. Giroire,
F. Huc,
and S. Pérennes.
Minimal selectors and fault tolerant networks.
Research report,
INRIA Research Report HAL-00082015,
July 2006.
[WWW
] [PDF
] [POSTSCRIPT
]
| Abstract: |
|
Un r\'eseau $\plk$ est un graphe non orient\'e avec $p + \lambda$ entr\'ees, $p + k$ sorties et des noeuds internes de degr\'e $4$. Un r\'eseau $\plk$ est valide si pour n'importe quel choix de $p$ entr\'ees et de $p$ sorties il existe $p$ chemins ar\^etes disjoints reliant les entr\'ees aux sorties. Dans le cas particulier $\lambda = 0$, un r\'eseau $\plk$ est un \emph{s\'electeur}. Notre objectif est de d\'eterminer $N\plk$ : le nombre minimum de noeuds d'un r\'eseau $\plk$ valide. Pour cela, on utilise une condition suffisante de validit\'e qui nous permet d'obtenir les bornes inf\'erieures pour $N\plk$. D'autre part on propose des constructions de r\'eseaux valides utlisant des \emph{expandeurs}, ce qui donne les bornes supp\'erieures. Le probl\`me d\'epend tr\`es fortement des ordres de $\lambda$ et $k$, par exemple lorsque $\lambda $ et $k$ sont petits par rapport \`a $p$, certains patterns sont interdits. Pour les valeurs plus grandes de $\lambda$ et $k$, on peut construire un r\'eseau $\plk$ valide \`a partir d'un graphe ayant de bonne propri\'et\'e d'expension concernant les petits ensembles de sommets. Cela nous emm\`ene \`a introduire un nouveau param\`etre : la \emph{robustness}. On obtient dans de nombreux cas des bornes assymptotiques exactes. |
@TechReport{AGHP06,
author = {O. Amini and F. Giroire and F. Huc and S. P\'erennes},
title = {Minimal selectors and fault tolerant networks},
institution = {INRIA Research Report HAL-00082015},
year = {2006},
month = {July},
type={Research report},
sorte = "Rapports",
url = {http://hal.inria.fr/inria-00082015},
POSTSCRIPT={http://hal.inria.fr/docs/00/08/20/15/PS/RRAGHP06.ps},
PDF={http://hal.inria.fr/docs/00/08/20/15/PDF/RRAGHP06.pdf},
abstract = {Un r\'eseau $\plk$ est un graphe non orient\'e avec $p + \lambda$ entr\'ees, $p + k$ sorties et des noeuds internes de degr\'e $4$. Un r\'eseau $\plk$ est valide si pour n'importe quel choix de $p$ entr\'ees et de $p$ sorties il existe $p$ chemins ar\^etes disjoints reliant les entr\'ees aux sorties. Dans le cas particulier $\lambda = 0$, un r\'eseau $\plk$ est un \emph{s\'electeur}. Notre objectif est de d\'eterminer $N\plk$ : le nombre minimum de noeuds d'un r\'eseau $\plk$ valide. Pour cela, on utilise une condition suffisante de validit\'e qui nous permet d'obtenir les bornes inf\'erieures pour $N\plk$. D'autre part on propose des constructions de r\'eseaux valides utlisant des \emph{expandeurs}, ce qui donne les bornes supp\'erieures. Le probl\`me d\'epend tr\`es fortement des ordres de $\lambda$ et $k$, par exemple lorsque $\lambda $ et $k$ sont petits par rapport \`a $p$, certains patterns sont interdits. Pour les valeurs plus grandes de $\lambda$ et $k$, on peut construire un r\'eseau $\plk$ valide \`a partir d'un graphe ayant de bonne propri\'et\'e d'expension concernant les petits ensembles de sommets. Cela nous emm\`ene \`a introduire un nouveau param\`etre : la \emph{robustness}. On obtient dans de nombreux cas des bornes assymptotiques exactes.},
}
-
O. Amini,
F. Huc,
and S. Pérennes.
On the pathwidth of planar graphs.
Research report,
INRIA Research Report HAL-00082035,
July 2006.
[WWW
] [PDF
] [POSTSCRIPT
]
| Abstract: |
|
Fomin and Thilikos in \cite{FoTh06} conjectured that there is a constant $c$ such that, for every $2$-connected planar graph $G$, $\text{pw}(G^*) \leq 2\text{pw}(G)+c$ (the same question was asked simutaneously by Coudert, Huc and Sereni in \cite{CHS06}). By the results of Boedlander and Fomin~\cite{BoFo02} this holds for every outerplanar graph and actually is tight by Coudert, Huc and Sereni~\cite{CHS06}. In \cite{FoTh06}, Fomin and Thilikos proved that there is a constant $c$ such that the pathwidth of every 3-connected graph $G$ satisfies: $\text{pw}(G^*) \leq 6\text{pw}(G)+c$. In this paper we improve this result by showing that the dual a 3-connected planar graph has pathwidth at most $3$ times the pathwidth of the primal plus two. We prove also that the question can be answered positively for $4$-connected planar graphs. |
@TechReport{AHP06,
author = {O. Amini and F. Huc and S. P\'erennes},
title = {On the pathwidth of planar graphs},
institution = {INRIA Research Report HAL-00082035 },
year = {2006},
month = {July},
type={Research report},
sorte = "Rapports",
url={http://hal.inria.fr/inria-00082035},
POSTSCRIPT={http://hal.inria.fr/docs/00/08/20/35/PS/RRAHP06.ps},
PDF={http://hal.inria.fr/docs/00/08/20/35/PDF/RRAHP06.pdf},
abstract = {Fomin and Thilikos in \cite{FoTh06} conjectured that there is a constant $c$ such that, for every $2$-connected planar graph $G$, $\text{pw}(G^*) \leq 2\text{pw}(G)+c$ (the same question was asked simutaneously by Coudert, Huc and Sereni in \cite{CHS06}). By the results of Boedlander and Fomin~\cite{BoFo02} this holds for every outerplanar graph and actually is tight by Coudert, Huc and Sereni~\cite{CHS06}. In \cite{FoTh06}, Fomin and Thilikos proved that there is a constant $c$ such that the pathwidth of every 3-connected graph $G$ satisfies: $\text{pw}(G^*) \leq 6\text{pw}(G)+c$. In this paper we improve this result by showing that the dual a 3-connected planar graph has pathwidth at most $3$ times the pathwidth of the primal plus two. We prove also that the question can be answered positively for $4$-connected planar graphs.},
}
-
J-C. Bermond,
D. Coudert,
H. Rivano,
and M. Syska.
Critical resource sharing, State of the art Survey.
Technical report Deliverable 2.2.1,
IST FET AEOLUS, Integrated Project IST-015964,
2006.
[PDF
]
@TechReport{BCRS06,
author = {J-C. Bermond and D. Coudert and H. Rivano and M. Syska},
title = {Critical resource sharing, State of the art Survey},
institution = {IST FET AEOLUS, Integrated Project IST-015964},
year = {2006},
number = {Deliverable 2.2.1},
sorte = "Rapports",
pdf = {http://aeolus.ceid.upatras.gr/sub-projects/deliverables/D221.pdf},
}
-
J-C. Bermond,
J. Galtier,
R. Klasing,
N. Morales,
and S. Pérennes.
Hardness and approximation of gathering in static radio networks.
Research Report 5936,
INRIA,
06 2006.
[WWW
] [PDF
]
| Abstract: |
|
In this paper, we address the problem of gathering information in a specific node (or \emph{sink}) of a radio network, where interference constraints are present. We take into account the fact that, when a node transmits, it produces interference in an area bigger than the area in which its message can actually be received. The network is modeled by a graph; a node is able to transmit one unit of information to the set of vertices at distance at most $\dt$ in the graph, but when doing so it generates interference that does not allow nodes at distance up to $\di$ ($\di \ge \dt$) to listen to other transmissions. Time is synchronous and divided into time-steps in each of which a round (set of non-interfering radio transmissions) is performed. We give general lower bounds on the number of rounds required to gather into a sink of a general graph, and present an algorithm working on any graph, with an approximation factor of 4. We also show that the problem of finding an optimal strategy for gathering is \textsc{NP-hard}, for any values of $\di$ and $\dt$. If $\di>\dt$, we show that the problem remains hard when restricted to the uniform case where each vertex in the network has exactly one piece of information to communicate to the sink. |
@TechReport{BGK+06d,
author = {J-C. Bermond and J. Galtier and R. Klasing and N. Morales and S. P\'erennes},
title = {Hardness and approximation of gathering in static radio networks},
year = {2006},
month = {06},
institution = {INRIA},
number = {5936},
type = {Research Report},
sorte = "Rapports",
url= {http://hal.inria.fr/inria-00081032},
pdf = {http://hal.inria.fr/action/open_file.php?url=http://hal.inria.fr/docs/00/08/14/26/PDF/RR-5936.pdf&docid=81426},
abstract = {In this paper, we address the problem of gathering information in a specific node (or \emph{sink}) of a radio network, where interference constraints are present. We take into account the fact that, when a node transmits, it produces interference in an area bigger than the area in which its message can actually be received. The network is modeled by a graph; a node is able to transmit one unit of information to the set of vertices at distance at most $\dt$ in the graph, but when doing so it generates interference that does not allow nodes at distance up to $\di$ ($\di \ge \dt$) to listen to other transmissions. Time is synchronous and divided into time-steps in each of which a round (set of non-interfering radio transmissions) is performed. We give general lower bounds on the number of rounds required to gather into a sink of a general graph, and present an algorithm working on any graph, with an approximation factor of 4. We also show that the problem of finding an optimal strategy for gathering is \textsc{NP-hard}, for any values of $\di$ and $\dt$. If $\di>\dt$, we show that the problem remains hard when restricted to the uniform case where each vertex in the network has exactly one piece of information to communicate to the sink.},
}
-
J-C. Bermond,
V. Papadopoulou,
and E. Pitoura.
Subproject2: Resource Management Report on the activities of the first year.
Technical report Deliverable 2.O.1,
IST FET AEOLUS, Integrated Project IST-015964,
2006.
[PDF
]
@TechReport{BPP06,
author = {J-C. Bermond and V. Papadopoulou and E. Pitoura},
title = {Subproject2: Resource Management Report on the activities of the first year},
institution = {IST FET AEOLUS, Integrated Project IST-015964},
year = {2006},
number = {Deliverable 2.O.1},
sorte = "Rapports",
pdf = {http://aeolus.ceid.upatras.gr/sub-projects/deliverables/D201.pdf},
}
-
D. Coudert,
P. Datta,
S. Pérennes,
H. Rivano,
and M-E. Voge.
Complexity and approximability issues of Shared Risk Resource Group.
Technical report,
INRIA Research Report 5859 and I3S Research Report I3S/RR-2006-08-FR,
2006.
[WWW
] [PDF
] [POSTSCRIPT
]
| Abstract: |
|
This article investigates complexity and approximability properties of combinatorial optimization problems yielded by the notion of Shared Risk Resource Group (SRRG). SRRG has been introduced in order to capture network survivability issues where a failure may break a whole set of resources, and has been formalized as colored graphs, where a set of resources is represented by a set of edges with same color. We consider here the analogous of classical problems such as determining paths or cuts with the minimum numbers of colors or color disjoint paths. These optimization problems are much more difficult than their counterparts in classical graph theory. In particular standard relationship such as the Max Flow - Min Cut equality do not hold any longer. In this article we identify cases where these problems are polynomial, for example when the edges of a given color form a connected subgraph, and otherwise give hardness and non approximability results for these problems. |
@TECHREPORT{CDP+06,
author = {D. Coudert and P. Datta and S. P\'erennes and H. Rivano and M-E. Voge},
title = {Complexity and approximability issues of Shared Risk Resource Group},
institution = {INRIA Research Report 5859 and I3S Research Report I3S/RR-2006-08-FR},
year = {2006},
sorte = "Rapports",
abstract = {This article investigates complexity and approximability properties of combinatorial optimization problems yielded by the notion of Shared Risk Resource Group (SRRG). SRRG has been introduced in order to capture network survivability issues where a failure may break a whole set of resources, and has been formalized as colored graphs, where a set of resources is represented by a set of edges with same color. We consider here the analogous of classical problems such as determining paths or cuts with the minimum numbers of colors or color disjoint paths. These optimization problems are much more difficult than their counterparts in classical graph theory. In particular standard relationship such as the Max Flow - Min Cut equality do not hold any longer. In this article we identify cases where these problems are polynomial, for example when the edges of a given color form a connected subgraph, and otherwise give hardness and non approximability results for these problems.},
pdf = {ftp://ftp.inria.fr/INRIA/publication/publi-pdf/RR/RR-5859.pdf},
postscript = {ftp://ftp.inria.fr/INRIA/publication/publi-ps-gz/RR/RR-5859.ps.gz},
url = {http://hal.inria.fr/inria-00070167}
}
-
D. Coudert,
F. Huc,
and J.S. Sereni.
Pathwidth of outerplanar graphs.
Technical report,
INRIA Research Report 5804 and I3S Research Report I3S/RR-2006-02-FR,
January 2006.
[WWW
] [PDF
] [POSTSCRIPT
]
| Abstract: |
|
We are interested in the relation between the pathwidth of a biconnected outerplanar graph and the pathwidth of its (geometric) dual. Bodlaender and Fomin, after having proved that the pathwidth of every biconnected outerplanar graph is always at most twice the pathwidth of its (geometric) dual plus two, conjectured that there exists a constant c such that the pathwidth of every biconnected outerplanar graph is at most c plus the pathwidth of its dual. They also conjectured that this was actually true with c being one for every biconnected planar graph. Fomin proved that the second conjecture is true for all planar triangulations. First, we construct for each p>=1 a biconnected outerplanar graph of pathwidth 2p 1 whose (geometric) dual has pathwidth p 1, thereby disproving both conjectures. Next, we also disprove two other conjectures (one of Bodlaender and Fomin, implied by one of Fomin). Finally we prove, in an algorithmic way, that the pathwidth of every biconnected outerplanar graph is at most twice the pathwidth of its (geometric) dual minus one. A tight interval for the studied relation is therefore obtained, and we show that all cases in the interval happen. |
@TECHREPORT{CHS06,
author = {D. Coudert and F. Huc and J.S. Sereni},
title = {Pathwidth of outerplanar graphs},
institution = {INRIA Research Report 5804 and I3S Research Report I3S/RR-2006-02-FR},
year = {2006},
month = {January},
sorte = "Rapports",
abstract = {We are interested in the relation between the pathwidth of a biconnected outerplanar graph and the pathwidth of its (geometric) dual. Bodlaender and Fomin, after having proved that the pathwidth of every biconnected outerplanar graph is always at most twice the pathwidth of its (geometric) dual plus two, conjectured that there exists a constant c such that the pathwidth of every biconnected outerplanar graph is at most c plus the pathwidth of its dual. They also conjectured that this was actually true with c being one for every biconnected planar graph. Fomin proved that the second conjecture is true for all planar triangulations. First, we construct for each p>=1 a biconnected outerplanar graph of pathwidth 2p 1 whose (geometric) dual has pathwidth p 1, thereby disproving both conjectures. Next, we also disprove two other conjectures (one of Bodlaender and Fomin, implied by one of Fomin). Finally we prove, in an algorithmic way, that the pathwidth of every biconnected outerplanar graph is at most twice the pathwidth of its (geometric) dual minus one. A tight interval for the studied relation is therefore obtained, and we show that all cases in the interval happen.},
optnote = {Submitted to Journal of Graph Theory},
pdf = {http://www.i3s.unice.fr/~mh/RR/2006/RR-06.02-D.COUDERT.pdf},
postscript = {ftp://ftp.inria.fr/INRIA/publication/publi-ps-gz/RR/RR-5804.ps.gz},
url = {http://www.inria.fr/rrrt/rr-5804.shtml}
}
-
O. Dalle.
OSA: an Open Component-based Architecture for Discrete-Event Simulation.
Technical report RR-5762, version 2,
INRIA,
February 2006.
[WWW
] [PDF
]
| Abstract: |
|
This report describes work in progress to initiate the collaborative development of a new software platform for discrete-event simulation studies, the Open Simulation Architecture (OSA). OSA is primarily designed to be a federating platform for the simulation community: it is designed to favour the integration of new or existing contributions at every level of its architecture. This report describes the way OSA provides an open platform intended to support simulationists in a wide set of their simulation activities, and how it favours the reuse and sharing of system models by means of a flexible component model (Fractal). Indeed, OSA supports component-based modeling, which has many well-known good properties. Out of these properties is the ability to dispatch the modeling effort amongst several experts each having their own area of system expertise. Clearly, the less experts have to care about areas of expertise of others, the more efficient they are in modeling sub-systems in their own area. Furthermore, the process of studying complex systems using discrete-event computer simulations involves several areas of non-system expertise, such as discrete-event techniques or experiment planning. In OSA, all these tasks are clearly separated by identifying different kinds of (virtual) users: experimenters, developpers, model architects, and so on. OSA shall eventually supports each of these users by integrating dedicated tools for each of their specific tasks. |
@TechReport{Dal06a,
author = {O. Dalle},
title = {{OSA}: an {O}pen {C}omponent-based {A}rchitecture for {D}iscrete-{E}vent Simulation},
institution = {INRIA},
year = {2006},
OPTkey = {},
OPTtype = {},
number = {RR-5762, version 2},
OPTaddress = {},
month = {February},
OPTnote = {},
PDF = {ftp://ftp-sop.inria.fr/mascotte/Publications/Dal06a.pdf},
OPTannote = {},
sorte = "Rapports",
url = {http://hal.inria.fr/inria-00070258/fr/},
abstract = {This report describes work in progress to initiate the collaborative development of a new software platform for discrete-event simulation studies, the Open Simulation Architecture (OSA). OSA is primarily designed to be a federating platform for the simulation community: it is designed to favour the integration of new or existing contributions at every level of its architecture. This report describes the way OSA provides an open platform intended to support simulationists in a wide set of their simulation activities, and how it favours the reuse and sharing of system models by means of a flexible component model (Fractal). Indeed, OSA supports component-based modeling, which has many well-known good properties. Out of these properties is the ability to dispatch the modeling effort amongst several experts each having their own area of system expertise. Clearly, the less experts have to care about areas of expertise of others, the more efficient they are in modeling sub-systems in their own area. Furthermore, the process of studying complex systems using discrete-event computer simulations involves several areas of non-system expertise, such as discrete-event techniques or experiment planning. In OSA, all these tasks are clearly separated by identifying different kinds of (virtual) users: experimenters, developpers, model architects, and so on. OSA shall eventually supports each of these users by integrating dedicated tools for each of their specific tasks.},
}
-
O. Delmas,
F. Havet,
M. Montassier,
and S. Pérennes.
Design of fault tolerant on-board networks.
Research report,
INRIA Research Report 5866,
March 2006.
[WWW
] [PDF
] [POSTSCRIPT
]
| Abstract: |
|
An $(n,k,r)$-network is a triple $N=(G,in,out)$ where $G=(V,E)$ is a graph and $in,out$ are integral functions defined on $V$ called input and output functions, such that for any $v \inV$, $in(v)+out(v)+ deg(v)\leq2r$ with $deg(v)$ the degree of $v$ in the graph $G$. The total number of inputs is $in(V)=\sum_v\inVin(v)$, and the total number of outputs is $out(V)=\sum_v\inVout(v)+k$. An $(n,k,r)$-network is valid, if for any faulty output function $out'$ (that is such that $out'(v) \leqout(v)$ for any $v \inV$, and $out'(V) = n$), there are $n$ edge-disjoint paths in $G$ such that each vertex $v\inV$ is the initial vertex of $in(v)$ paths and the terminal vertex of $out'(v)$ paths. We investigate the design problem of determining the minimum number of vertices in a valid $(n,k,r)$-network and of constructing minimum $(n,k,r)$-networks, or at least valid $(n,k,r)$-networks with a number of vertices close to the optimal value. We first show $\frac3n+k2r-2+ \frac3r^2k \leq\calN(n,k,r)\leq\left\lceil\frack+22r-2\right\rceil\fracn2$. We prove a better upper bound when $r\geqk/2$: $\calN(n,k,r) \leq\fracr-2+k/2r^2-2r+k/2 n + O(1)$. Finally, we give the exact value of $\calN(n,k,r)$ when $k\leq6$ and exhibit the corresponding networks. |
@TechReport{DHM+06,
author = {O. Delmas and F. Havet and M. Montassier and S. P\'erennes},
title = {Design of fault tolerant on-board networks},
month = {March},
year = {2006},
type = {Research report},
sorte = "Rapports",
institution = {INRIA Research Report 5866},
POSTSCRIPT = {ftp://ftp.inria.fr/INRIA/publication/publi-ps-gz/RR/RR-5866.ps.gz},
pdf = {ftp://ftp.inria.fr/INRIA/publication/publi-pdf/RR/RR-5866.pdf},
URL = {http://hal.inria.fr/inria-00070160/fr/},
abstract = {An $(n,k,r)$-network is a triple $N=(G,in,out)$ where $G=(V,E)$ is a graph and $in,out$ are integral functions defined on $V$ called input and output functions, such that for any $v \inV$, $in(v)+out(v)+ deg(v)\leq2r$ with $deg(v)$ the degree of $v$ in the graph $G$. The total number of inputs is $in(V)=\sum_v\inVin(v)$, and the total number of outputs is $out(V)=\sum_v\inVout(v)+k$. An $(n,k,r)$-network is valid, if for any faulty output function $out'$ (that is such that $out'(v) \leqout(v)$ for any $v \inV$, and $out'(V) = n$), there are $n$ edge-disjoint paths in $G$ such that each vertex $v\inV$ is the initial vertex of $in(v)$ paths and the terminal vertex of $out'(v)$ paths. We investigate the design problem of determining the minimum number of vertices in a valid $(n,k,r)$-network and of constructing minimum $(n,k,r)$-networks, or at least valid $(n,k,r)$-networks with a number of vertices close to the optimal value. We first show $\frac3n+k2r-2+ \frac3r^2k \leq\calN(n,k,r)\leq\left\lceil\frack+22r-2\right\rceil\fracn2$. We prove a better upper bound when $r\geqk/2$: $\calN(n,k,r) \leq\fracr-2+k/2r^2-2r+k/2 n + O(1)$. Finally, we give the exact value of $\calN(n,k,r)$ when $k\leq6$ and exhibit the corresponding networks.},
}
-
F. Havet,
R. J. Kang,
T. Müller,
and J.-S. Sereni.
Circular Choosability.
Research report,
INRIA Research Report 5957 and I3S Research Report I3S/RR-2006-21-FR,
July 2006.
Note: Submitted to Journal of Graph Theory.
[WWW
] [PDF
] [POSTSCRIPT
]
| Abstract: |
|
In this paper, we study the notion of circular choosability recently introduced by Mohar and Zhu. First, we provide a negative answer to a question of Zhu about circular cliques. We next prove that, for every graph G, cch(G) = O( ch(G) + ln |V(G)| ). We investigate a generalisation of circular choosability, circular f-choosability, when f is a function of the degrees. We also consider the circular choice number of planar graphs. Mohar asked for the value of tau := sup{ cch(G) : G is planar }, and we prove that 6 <= tau <= 8, thereby providing a negative answer to another question of Mohar. Finally, we study the circular choice number of planar and outerplanar graphs with prescribed girth, and graphs with bounded density. |
@TechReport{HKMS06,
author = {F. Havet and R. J. Kang and T. M\"uller and J.-S. Sereni},
title = {Circular Choosability},
institution = {INRIA Research Report 5957 and I3S Research Report I3S/RR-2006-21-FR},
year = {2006},
month = {July},
note = {Submitted to Journal of Graph Theory},
type={Research report},
sorte = "Rapports",
url= {http://hal.inria.fr/inria-00086981},
POSTSCRIPT={http://hal.inria.fr/docs/00/08/83/74/PS/RR-5957.ps},
PDF={http://www.i3s.unice.fr/4.523703E-267mh/RR/2006/RR-06.21-F.HAVET.pdf},
abstract = {In this paper, we study the notion of circular choosability recently introduced by Mohar and Zhu. First, we provide a negative answer to a question of Zhu about circular cliques. We next prove that, for every graph G, cch(G) = O( ch(G) + ln |V(G)| ). We investigate a generalisation of circular choosability, circular f-choosability, when f is a function of the degrees. We also consider the circular choice number of planar graphs. Mohar asked for the value of tau := sup{ cch(G) : G is planar }, and we prove that 6 <= tau <= 8, thereby providing a negative answer to another question of Mohar. Finally, we study the circular choice number of planar and outerplanar graphs with prescribed girth, and graphs with bounded density.},
}
-
F. Havet,
J.-S. Sereni,
and R. Skrekovski.
3-facial colouring of plane graphs.
Research report,
INRIA Research Report 5943 and I3S Research Report I3S/RR-2006-20-FR,
July 2006.
Note: Submitted to SIAM Journal on Discrete Mathematics.
[WWW
] [PDF
] [POSTSCRIPT
]
| Abstract: |
|
A plane graph is l-facially k-colourable if its vertices can be coloured with k colours such that any two distinct vertices on a facial segment of length at most l are coloured differently. We prove that every plane graph is 3-facially 11-colourable. As a consequence, we derive that every 2-connected plane graph with maximum face-size at most 7 is cyclically 11-colourable. These two bounds are for one off from those that are proposed by the (3l+1)-Conjecture and the Cyclic Conjecture. |
@TechReport{HSS06,
author = {F. Havet and J.-S. Sereni and R. {\v{S}}krekovski},
title = {3-facial colouring of plane graphs},
institution = {INRIA Research Report 5943 and I3S Research Report I3S/RR-2006-20-FR},
year = {2006},
month = {July},
note = {Submitted to SIAM Journal on Discrete Mathematics},
type={Research report},
sorte = "Rapports",
url={http://hal.inria.fr/inria-00083533},
POSTSCRIPT={http://hal.inria.fr/docs/00/08/44/30/PS/squelette-rr.ps},
PDF = {http://www.i3s.unice.fr/~mh/RR/2006/RR-06.20-J.-S.SERENI.pdf},
abstract = {A plane graph is l-facially k-colourable if its vertices can be coloured with k colours such that any two distinct vertices on a facial segment of length at most l are coloured differently. We prove that every plane graph is 3-facially 11-colourable. As a consequence, we derive that every 2-connected plane graph with maximum face-size at most 7 is cyclically 11-colourable. These two bounds are for one off from those that are proposed by the (3l+1)-Conjecture and the Cyclic Conjecture.},
}
-
F. Havet.
Choosability of the square of planar subcubic graphs with large girth.
Research report,
INRIA Research Report 5800 and I3S Research Report I3S/RR-2006-01-FR,
January 2006.
Note: Submitted to Discrete Mathematics.
[WWW
] [PDF
] [POSTSCRIPT
]
| Abstract: |
|
We first show that the choose number of the square of a subcubic graph with maximum average degree less than 18/7 is at most 6. As a corollary, we get that the choose number of the square of a planar graph with girth at least 9 is at most 6. We then show that the choose number of the square of a subcubic planar graph with girth at least 13 is at most 5. |
@TechReport{Hav06b,
author = {F. Havet},
title = {Choosability of the square of planar subcubic graphs with large girth},
month = {January},
year = {2006},
type = {Research report},
sorte = "Rapports",
institution = {INRIA Research Report 5800 and I3S Research Report I3S/RR-2006-01-FR},
POSTSCRIPT = {ftp://ftp.inria.fr/INRIA/publication/publi-ps-gz/RR/RR-5800.ps.gz},
pdf = {ftp://ftp.inria.fr/INRIA/publication/publi-pdf/RR/RR-5800.pdf},
URL = {http://hal.inria.fr/inria-00070223/fr/},
note = {Submitted to Discrete Mathematics},
abstract = {We first show that the choose number of the square of a subcubic graph with maximum average degree less than 18/7 is at most 6. As a corollary, we get that the choose number of the square of a planar graph with girth at least 9 is at most 6. We then show that the choose number of the square of a subcubic planar graph with girth at least 13 is at most 5.},
}
-
F. Havet,
S. Thomassé,
and A. Yeo.
Hoàng-Reed conjecture holds for tournaments.
Research report,
INRIA Research Report 5976,
September 2006.
Note: Submitted Discrete Mathematics.
[WWW
] [PDF
]
| Abstract: |
|
Hoà ng-Reed conjecture asserts that every digraph $D$ has a collection $\cal C$ of circuits $C_1,\dots,C_{\delta ^+}$, where $\delta ^+$ is the minimum outdegree of $D$, such that the circuits of $\cal C$ have a forest-like structure. Formally, $|V(C_i)\cap (V(C_1)\cup \dots \cup V(C_{i-1}))|\leq 1$, for all $i=2,\dots ,\delta^+$. We verify this conjecture for the class of tournaments. |
@TechReport{HTY06,
author = {F. Havet and S. Thomass\'e and A. Yeo},
title = {Ho{\`a}ng-Reed conjecture holds for tournaments},
institution = {INRIA Research Report 5976},
year = {2006},
month = {September},
note = {Submitted Discrete Mathematics},
type={Research report},
url= {http://hal.inria.fr/inria-00091366},
sorte = "Rapports",
PDF={http://hal.inria.fr/docs/00/09/50/31/PDF/RR-5976.pdf},
abstract = {Hoà ng-Reed conjecture asserts that every digraph $D$ has a collection $\cal C$ of circuits $C_1,\dots,C_{\delta ^+}$, where $\delta ^+$ is the minimum outdegree of $D$, such that the circuits of $\cal C$ have a forest-like structure. Formally, $|V(C_i)\cap (V(C_1)\cup \dots \cup V(C_{i-1}))|\leq 1$, for all $i=2,\dots ,\delta^+$. We verify this conjecture for the class of tournaments.},
}
-
M. Lenisa,
F. Honsell,
and L. Liquori.
A Framework for Defining Logical Frameworks.
Research Report,
RR INRIA and University of Udine,
2006.
[WWW
]
@TECHREPORT{LHL06,
sorte = "Rapports",
AUTHOR = {M. Lenisa and F. Honsell and L. Liquori},
TITLE = {A Framework for Defining Logical Frameworks},
INSTITUTION = {RR INRIA and University of Udine},
type={Research Report},
YEAR = {2006},
URL = {http://hal.inria.fr/inria-00088809},
}
-
G. Méheut,
S. Pérennes,
and H. Rivano.
Evaluation stochastique et simulation des réseaux radio.
Research report 5989,
INRIA,
September 2006.
[WWW
]
| Abstract: |
|
La capacité d'un réseau ad hoc sans fil passe mal à l'échelle lorsque le nombre $N$ de noeuds du réseau augmente. Si chaque noeud choisit un interlocuteur parmi les autres noeuds, le débit avec lequel les noeuds peuvent communiquer doit tendre vers $0$ au moins en $\mathcal{O}\left(1/\sqrt{N}\right)$ lorsque $N$ tend vers l'infini. Le problème fondamental des réseaux ad hoc sans fil est de trouver un compromis entre connectivité et parallélisme: il est nécessaire d'utiliser une puissance d'émission suffisante pour éviter d'avoir des noeuds isolés mais il faut aussi limiter cette puissance pour limiter les interférences et ainisi obtenir du parallélisme dans l'accès au médium. L'objectif principal de cette étude est de proposer des protocoles de routage qui permettent d'atteindre la borne asymptotique pour la capacité et de dépasser le résultat déjà connu de $\mathcal{O}\left(1/\sqrt{N\ln(N)}\right)$ dans le cadre des réseaux aléatoires sur le carré unité $[0,1]\times[0,1]$ avec un trafic également aléatoire. Une première approche à l'aide d'un routage local utilisant une puissance d'émission variable permet de se rapprocher de cette borne sans toutefois l'atteindre en raison d'une mauvaise répartition du trafic due à l'aspect aléatoire du réseau. Une seconde approche fondée sur la théorie de la percolation aboutit à l'existence avec une forte probabilité d'un nombre suffisant de chemins disjoints formés de {\og petits sauts \fg} et traversant le réseau. Ces chemins permettent d'acheminer l'ensemble du trafic avec suffisamment de parallélisme pour atteindre asymptotiquement un débit en $\Theta\left(\frac{1}{\sqrt{N}}\right)$ pour chaque noeud. On s'appuie en outre sur des simulations afin de valider empiriquement les résultats de l'analyse théorique. |
@TECHREPORT{MPR06,
sorte = "Rapports",
author = {G. M\'eheut and S. P\'erennes and H. Rivano},
title = {Evaluation stochastique et simulation des r\'eseaux radio},
institution = {INRIA},
year = {2006},
type = {Research report},
number = {5989},
month = {September},
abstract = {La capacité d'un réseau ad hoc sans fil passe mal à l'échelle lorsque le nombre $N$ de noeuds du réseau augmente. Si chaque noeud choisit un interlocuteur parmi les autres noeuds, le débit avec lequel les noeuds peuvent communiquer doit tendre vers $0$ au moins en $\mathcal{O}\left(1/\sqrt{N}\right)$ lorsque $N$ tend vers l'infini. Le problème fondamental des réseaux ad hoc sans fil est de trouver un compromis entre connectivité et parallélisme: il est nécessaire d'utiliser une puissance d'émission suffisante pour éviter d'avoir des noeuds isolés mais il faut aussi limiter cette puissance pour limiter les interférences et ainisi obtenir du parallélisme dans l'accès au médium. L'objectif principal de cette étude est de proposer des protocoles de routage qui permettent d'atteindre la borne asymptotique pour la capacité et de dépasser le résultat déjà connu de $\mathcal{O}\left(1/\sqrt{N\ln(N)}\right)$ dans le cadre des réseaux aléatoires sur le carré unité $[0,1]\times[0,1]$ avec un trafic également aléatoire. Une première approche à l'aide d'un routage local utilisant une puissance d'émission variable permet de se rapprocher de cette borne sans toutefois l'atteindre en raison d'une mauvaise répartition du trafic due à l'aspect aléatoire du réseau. Une seconde approche fondée sur la théorie de la percolation aboutit à l'existence avec une forte probabilité d'un nombre suffisant de chemins disjoints formés de {\og petits sauts \fg} et traversant le réseau. Ces chemins permettent d'acheminer l'ensemble du trafic avec suffisamment de parallélisme pour atteindre asymptotiquement un débit en $\Theta\left(\frac{1}{\sqrt{N}}\right)$ pour chaque noeud. On s'appuie en outre sur des simulations afin de valider empiriquement les résultats de l'analyse théorique.},
url = {http://hal.inria.fr/inria-00102039}
}
-
H. Rivano,
F. Théoleyre,
and F. Valois.
About the Capacity of Flat and Self-Organized Ad Hoc and Hybrid Networks.
Research Report,
INRIA Research Report 5977,
2006.
[WWW
]
| Abstract: |
|
Ad hoc networking specific challenges foster a strong research effort on efficient protocols design. Routing protocols based on a self-organized structure have been studied principally for the robustness and the scalability they provide. On the other hand, self-organization schemes may decrease the network capacity since they concentrate the traffic on privileged links. This paper presents four models for evaluating the capacity of a routing schemes on 802.11 like networks. Our approach consists in modeling the radio resource sharing principles of 802.11 like MAC protocols as a set of linear constraints. We have implemented 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 scenarii of spatial re-utilization of the medium, yielding a lower bound and an upper bound on the network capacity for each fairness case. Our models are independent of the routing protocols and provide therefore a relevant framework for their comparison. We apply our models to a comparative analysis of the well-known shortest path base flat routing protocol OLSR against two main self-organized structure approaches, VSR, and Wu \& Li's protocols. This study concludes on the relevance of self-organized approaches from the network capacity point of view. |
@TECHREPORT{RTV06b,
sorte = "Rapports",
author = {H. Rivano and F. Th\'eoleyre and F. Valois},
title = {About the Capacity of Flat and Self-Organized Ad Hoc and Hybrid Networks},
institution = {INRIA Research Report 5977},
year = {2006},
type = {Research Report},
abstract = {Ad hoc networking specific challenges foster a strong research effort on efficient protocols design. Routing protocols based on a self-organized structure have been studied principally for the robustness and the scalability they provide. On the other hand, self-organization schemes may decrease the network capacity since they concentrate the traffic on privileged links. This paper presents four models for evaluating the capacity of a routing schemes on 802.11 like networks. Our approach consists in modeling the radio resource sharing principles of 802.11 like MAC protocols as a set of linear constraints. We have implemented 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 scenarii of spatial re-utilization of the medium, yielding a lower bound and an upper bound on the network capacity for each fairness case. Our models are independent of the routing protocols and provide therefore a relevant framework for their comparison. We apply our models to a comparative analysis of the well-known shortest path base flat routing protocol OLSR against two main self-organized structure approaches, VSR, and Wu \& Li's protocols. This study concludes on the relevance of self-organized approaches from the network capacity point of view.},
url = {http://hal.inria.fr/inria-00095216}
}
