-
V. Bilò,
I. Caragiannis,
A. Fanelli,
M. Flammini,
C. Kaklamanis,
G. Monaco,
and L. Moscardelli.
Graphs and Algorithms in Communication Networks: Studies in Broadband, Optical, Wireless, and Ad Hoc Networks,
volume XXVII of EATCS Texts in Theoretical Computer Science,
chapter Game-Theoretic Approaches to Optimization Problems in Communication Networks,
pages 241-264.
Springer,
A. Koster and X. Muñoz edition,
November 2009.
[WWW
] [PDF
]
| Abstract: |
|
In this chapter we consider fundamental communication problems arising in networks with non-cooperative users. The uncoordinated usersâ behavior, addressing communication primitives in an individualistic and selfish manner, poses several intriguing questions ranging from the definition of reasonable and practical models, to the quantification of the efficiency loss due to the lack of users' cooperation. We present several results lately achievied in this research area and propose interesting future research directions. |
@InBook{BCF+09,
sorte = "livres-chap",
author = {V. Bil{\`o} and I. Caragiannis and A. Fanelli and M. Flammini and C. Kaklamanis and G. Monaco and L. Moscardelli},
ALTeditor = {},
title = {Graphs and Algorithms in Communication Networks: Studies in Broadband, Optical, Wireless, and Ad Hoc Networks},
chapter = {Game-Theoretic Approaches to Optimization Problems in Communication Networks},
publisher = {Springer},
year = {2009},
x-pays = {IT,GR},
OPTkey = {},
volume = {XXVII},
OPTnumber = {},
series = {EATCS Texts in Theoretical Computer Science},
OPTtype = {},
OPTaddress = {},
edition = {{A. Koster and X. Mu{\~n}oz}},
month = nov,
pages = {241-264},
OPTnote = {to appear},
OPTannote = {},
ISBN = {978-3-642-02249-4},
url = {http://www.springer.com/computer/foundations/book/978-3-642-02249-4},
abstract = {In this chapter we consider fundamental communication problems arising in networks with non-cooperative users. The uncoordinated usersâ behavior, addressing communication primitives in an individualistic and selfish manner, poses several intriguing questions ranging from the definition of reasonable and practical models, to the quantification of the efficiency loss due to the lack of users' cooperation. We present several results lately achievied in this research area and propose interesting future research directions. },
pdf = {http://www.gianpieromonaco.com/293chap-selfish.pdf},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
}
-
I. Sau and J. Zerovnik.
Graphs and Algorithms in Communication Networks: Studies in Broadband, Optical, Wireless, and Ad Hoc Networks,
volume XXVII of EATCS Texts in Theoretical Computer Science,
chapter Permutation Routing and $(\ell,k)$-Routing on Plane Grids,
pages 265-279.
Springer,
A. Koster and X. Muñoz edition,
November 2009.
[WWW
] [PDF
]
| Abstract: |
|
The packet routing problem plays an essential role in communication networks. It involves how to transfer data from some origins to some destinations within a reasonable amount of time. In the $(\ell,k)$-routing problem, each node can send at most $\ell$ packets and receive at most $k$ packets. Permutation routing is the particular case $\ell=k=1$. In the $r$-centralrouting problem, all nodes at distance at most $r$ from a fixed node $v$ want to send a packet to $v$.Here we survey the results on permutation routing, the $r$-central routing and the general $(\ell,k)$-routing problems on plane grids, that is square grids, triangular grids and hexagonal grids. We assume the \emph{store-and-forward} $\Delta$-port model, and we consider both full and half-duplex networks. |
@InBook{SaZe09,
sorte = "livres-chap",
author = {I. Sau and J. Zerovnik},
ALTeditor = {},
title = {Graphs and Algorithms in Communication Networks: Studies in Broadband, Optical, Wireless, and Ad Hoc Networks},
chapter = {Permutation Routing and $(\ell,k)$-Routing on Plane Grids},
publisher = {Springer},
year = {2009},
OPTkey = {},
volume = {XXVII},
OPTnumber = {},
series = {EATCS Texts in Theoretical Computer Science},
OPTtype = {},
OPTaddress = {},
edition = {{A. Koster and X. Mu{\~n}oz}},
month = nov,
pages = {265-279},
OPTnote = {to appear},
OPTannote = {},
ISBN = {978-3-642-02249-4},
url = {http://www.springer.com/computer/foundations/book/978-3-642-02249-4},
abstract = {The packet routing problem plays an essential role in communication networks. It involves how to transfer data from some origins to some destinations within a reasonable amount of time. In the $(\ell,k)$-routing problem, each node can send at most $\ell$ packets and receive at most $k$ packets. Permutation routing is the particular case $\ell=k=1$. In the $r$-centralrouting problem, all nodes at distance at most $r$ from a fixed node $v$ want to send a packet to $v$.Here we survey the results on permutation routing, the $r$-central routing and the general $(\ell,k)$-routing problems on plane grids, that is square grids, triangular grids and hexagonal grids. We assume the \emph{store-and-forward} $\Delta$-port model, and we consider both full and half-duplex networks.},
pdf = {ftp://ftp-sop.inria.fr/mascotte/Publications/SaZe09.pdf},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
x-pays = {SI},
}
-
L. Addario-Berry,
N. Broutin,
and B. Reed.
Critical random graphs and the structure of a minimum spanning tree.
Random Structures and Algorithms,
35:323--347,
2009.
[WWW
] [PDF
]
| Abstract: |
|
We consider the complete graph on n vertices whose edges are weighted by independent and identically distributed edge weights and build the associated minimum weight spanning tree. We show that if the random weights are all distinct, then the expected diameter of such a tree is Î(n1-3). This settles a question of Frieze and Mc-Diarmid (Random Struct Algorithm 10 (1997), 5â42). The proofs are based on a precise analysis of the behavior of random graphs around the critical point. © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2009 |
@ARTICLE{ABR09,
sorte = "rev-int",
AUTHOR={L. Addario-Berry and N. Broutin and B. Reed},
TITLE={Critical random graphs and the structure of a minimum spanning tree},
JOURNAL = {Random Structures and Algorithms},
VOLUME = {35},
NUMBER = {},
YEAR = {2009},
PAGES = {323--347},
x-pays ={CA},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
abstract = {We consider the complete graph on n vertices whose edges are weighted by independent and identically distributed edge weights and build the associated minimum weight spanning tree. We show that if the random weights are all distinct, then the expected diameter of such a tree is Î(n1-3). This settles a question of Frieze and Mc-Diarmid (Random Struct Algorithm 10 (1997), 5â42). The proofs are based on a precise analysis of the behavior of random graphs around the critical point. © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2009},
pdf = {algo.inria.fr/broutin/pub/AdBrRe2009a.pdf},
url ={http://portal.acm.org/citation.cfm?id=1598965}
}
-
L. Addario-Berry and B. Reed.
Minima in branching random walks.
Annals of Probability,
37:1044--1079,
2009.
[WWW
] [PDF
]
| Abstract: |
|
Given a branching random walk, let $M_n$ be the minimum position of any member of the $n$th generation. We calculate $\mathbf{E}M_n$ to within O(1) and prove exponential tail bounds for $\mathbf{P}\{|M_n-\mathbf{E}M_n|>x\}$, under quite general conditions on the branching random walk. In particular, together with work by Bramson [Z. Wahrsch. Verw. Gebiete 45 (1978) 89--108], our results fully characterize the possible behavior of $\mathbf {E}M_n$ when the branching random walk has bounded branching and step size. |
@ARTICLE{AdRe09,
sorte = "rev-int",
AUTHOR={L. Addario-Berry and B. Reed},
TITLE={Minima in branching random walks},
JOURNAL = {Annals of Probability},
VOLUME = {37},
NUMBER = {},
YEAR = {2009},
PAGES = {1044--1079},
x-pays ={CA},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
abstract = {Given a branching random walk, let $M_n$ be the minimum position of any member of the $n$th generation. We calculate $\mathbf{E}M_n$ to within O(1) and prove exponential tail bounds for $\mathbf{P}\{|M_n-\mathbf{E}M_n|>x\}$, under quite general conditions on the branching random walk. In particular, together with work by Bramson [Z. Wahrsch. Verw. Gebiete 45 (1978) 89--108], our results fully characterize the possible behavior of $\mathbf {E}M_n$ when the branching random walk has bounded branching and step size.},
pdf = {http://arxiv.org/pdf/0712.2582v3},
url ={http://arxiv.org/abs/0712.2582}
}
-
O. Amini,
F. Huc,
and S. Pérennes.
On the pathwidth of planar graphs.
SIAM Journal of Discrete Mathematics,
23(3):1311-1316,
August 2009.
[WWW
] [PDF
]
| Abstract: |
|
In this paper, we present a result concerning the relation between the path-with of a planar graph and the path-width of its dual. More precisely, we prove that for a 3-connected planar graph $G$, $pw(G) \leq 3pw(G^*)+2$. For $4$-connected planar graphs, and more generally for Hamiltonian planar graphs, we prove a stronger bound $\pw(G^*) \leq 2 \ \pw(G)+c$. The best previously known bound was obtained by Fomin and Thilikos who proved that $\pw(G^*) \leq 6 \ \pw(G)+cte$. The proof is based on an algorithm which, given a fixed spanning tree of $G$, transforms any given decomposition of $G$ into one of $G^*$. The ratio of the corresponding parameters is bounded by the maximum degree of the spanning tree. |
@article{AHP09,
sorte = "rev-int",
author= { O. Amini and F. Huc and S. P\'erennes },
title= { On the pathwidth of planar graphs },
journal= { SIAM Journal of Discrete Mathematics },
volume = {23},
number = {3},
pages = {1311-1316},
year = {2009},
month = aug,
pdf= { ftp://ftp-sop.inria.fr/mascotte/Publications/AHP07.pdf },
url = {http://dx.doi.org/10.1137/060670146},
abstract= { In this paper, we present a result concerning the relation between the path-with of a planar graph and the path-width of its dual. More precisely, we prove that for a 3-connected planar graph $G$, $pw(G) \leq 3pw(G^*)+2$. For $4$-connected planar graphs, and more generally for Hamiltonian planar graphs, we prove a stronger bound $\pw(G^*) \leq 2 \ \pw(G)+c$. The best previously known bound was obtained by Fomin and Thilikos who proved that $\pw(G^*) \leq 6 \ \pw(G)+cte$. The proof is based on an algorithm which, given a fixed spanning tree of $G$, transforms any given decomposition of $G$ into one of $G^*$. The ratio of the corresponding parameters is bounded by the maximum degree of the spanning tree. },
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
}
-
O. Amini,
F. Mazoit,
N. Nisse,
and S. Thomassé.
Submodular partition functions.
Discrete Mathematics,
309(20):6000-6008,
2009.
[WWW
] [PDF
]
| Abstract: |
|
Adapting the method introduced in Graph Minors X, we propose a new proof of the duality between the bramble-number of a graph and its tree-width. Our approach is based on a new definition of submodularity on partition functions which naturally extends the usual one on set functions. The proof does not rely on Menger's theorem, and thus greatly generalises the original one. It thus provides a dual for matroid tree-width. One can also derive all known dual notions of other classical width-parameters from it. |
@article{AMN+09,
sorte = "rev-int",
author = {O. Amini and F. Mazoit and N. Nisse and S. Thomass\'e},
title = {Submodular partition functions},
journal = {Discrete Mathematics},
volume = {309},
number = {20},
pages = {6000-6008},
year = {2009},
abstract = {Adapting the method introduced in Graph Minors X, we propose a new proof of the duality between the bramble-number of a graph and its tree-width. Our approach is based on a new definition of submodularity on partition functions which naturally extends the usual one on set functions. The proof does not rely on Menger's theorem, and thus greatly generalises the original one. It thus provides a dual for matroid tree-width. One can also derive all known dual notions of other classical width-parameters from it.},
url = {http://www-sop.inria.fr/members/Nicolas.Nisse/publications/},
pdf = {http://www-sop.inria.fr/members/Nicolas.Nisse/publications/},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
}
-
O. Amini,
S. Pérennes,
and I. Sau.
Hardness and Approximation of Traffic Grooming.
Theoretical Computer Science,
410(38-40):3751-3760,
2009.
[PDF
]
| Abstract: |
|
Traffic grooming is a central problem in optical networks. It refers to packing low rate signals into higher speed streams, in order to improve bandwidth utilization and reduce network cost. In WDM networks, the most accepted criterion is to minimize the number of electronic terminations, namely the number of SONET Add-Drop Multiplexers (ADMs). In this article we focus on ring and path topologies. On the one hand, we provide an inapproximability result for Traffic Grooming for fixed values of the grooming factor g, answering authorrmatively the conjecture of Chow and Lin (Networks, 44:194-202, 2004 ). More precisely, we prove that Ring Traffic Grooming for fixed $g\leq 1$ and Path Traffic Grooming for fixed $g \leq 2$ are Apx-complete. That is, they do not accept a PTAS unless P = NP. Both results rely on the fact that finding the maximum number of edge-disjoint triangles in a tripartite graph (and more generally cycles of length $2g + 1$ in a $(2g + 1)$-partite graph of girth $2g + 1$) is Apx-complete. On the other hand, we provide a polynomial-time approximation algorithm for Ring and Path Traffic Grooming, based on a greedy cover algorithm, with an approximation ratio independent of $g$. Namely, the approximation guarantee is ${\mathcal O} (n^{1/3}\log^2(n))$ for any $g\leq 1$, $n$ being the size of the network. This is useful in practical applications, since in backbone networks the grooming factor is usually greater than the network size. Finally, we improve this approximation ratio under some extra assumptions about the request graph. |
@ARTICLE{APS09,
sorte = "rev-int",
AUTHOR = {O. Amini and S. P\'erennes and I. Sau},
TITLE = {{Hardness and Approximation of Traffic Grooming}},
JOURNAL = {Theoretical Computer Science},
YEAR = {2009},
volume = {410},
number = {38-40},
pages = {3751-3760},
pdf = {ftp://ftp-sop.inria.fr/mascotte/Publications/APS09.pdf},
abstract = {Traffic grooming is a central problem in optical networks. It refers to packing low rate signals into higher speed streams, in order to improve bandwidth utilization and reduce network cost. In WDM networks, the most accepted criterion is to minimize the number of electronic terminations, namely the number of SONET Add-Drop Multiplexers (ADMs). In this article we focus on ring and path topologies. On the one hand, we provide an inapproximability result for Traffic Grooming for fixed values of the grooming factor g, answering authorrmatively the conjecture of Chow and Lin (Networks, 44:194-202, 2004 ). More precisely, we prove that Ring Traffic Grooming for fixed $g\leq 1$ and Path Traffic Grooming for fixed $g \leq 2$ are Apx-complete. That is, they do not accept a PTAS unless P = NP. Both results rely on the fact that finding the maximum number of edge-disjoint triangles in a tripartite graph (and more generally cycles of length $2g + 1$ in a $(2g + 1)$-partite graph of girth $2g + 1$) is Apx-complete. On the other hand, we provide a polynomial-time approximation algorithm for Ring and Path Traffic Grooming, based on a greedy cover algorithm, with an approximation ratio independent of $g$. Namely, the approximation guarantee is ${\mathcal O} (n^{1/3}\log^2(n))$ for any $g\leq 1$, $n$ being the size of the network. This is useful in practical applications, since in backbone networks the grooming factor is usually greater than the network size. Finally, we improve this approximation ratio under some extra assumptions about the request graph.},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
}
-
J-C. Bermond,
R. Correa,
and M-L. Yu.
Optimal Gathering Protocols on Paths under Interference Constraints.
Discrete Mathematics,
309(18):5574-5587,
September 2009.
Note: A preliminary version has been presented at CIAC06.
[WWW
] [PDF
]
| Abstract: |
|
We study the problem of gathering information from the nodes of a multi-hop radio network into a predefined destination node under reachability and interference constraints. In such a network, a node is able to send messages to other nodes within reception distance, but doing so it might create interference with other communications. Thus, a message can only be properly received if the receiver is reachable from the sender and there is no interference from another message being transmitted simultaneously. The network is modeled as a graph, where the vertices represent the nodes of the network and the edges, the possible communications. The interference constraint is modeled by a fixed integer d?1, which implies that nodes within distance d in the graph from one sender cannot receive messages from another node. In this paper, we suppose that each node has one unit-length message to transmit and, furthermore, we suppose that it takes one unit of time (slot) to transmit a unit-length message and during such a slot we can have only calls which do not interfere (called compatible calls). A set of compatible calls is referred to as a round. We give protocols and lower bounds on the minimum number of rounds for the gathering problem when the network is a path and the destination node is either at one end or at the center of the path. These protocols are shown to be optimal for any d in the first case, and for 1?d?4, in the second case. |
@Article{BCY09,
author = {J-C. Bermond and R. Correa and M-L. Yu},
title = {Optimal Gathering Protocols on Paths under Interference Constraints},
journal = {Discrete Mathematics},
year= {2009},
OPTkey = {},
volume = {309},
number = {18},
pages = {5574-5587},
month = sep,
URL={http://dx.doi.org/10.1016/j.disc.2008.04.037},
note = {A preliminary version has been presented at CIAC06},
PDF={http://www-sop.inria.fr/members/Jean-Claude.Bermond/PUBLIS/BCY08.pdf},
abstract = {We study the problem of gathering information from the nodes of a multi-hop radio network into a predefined destination node under reachability and interference constraints. In such a network, a node is able to send messages to other nodes within reception distance, but doing so it might create interference with other communications. Thus, a message can only be properly received if the receiver is reachable from the sender and there is no interference from another message being transmitted simultaneously. The network is modeled as a graph, where the vertices represent the nodes of the network and the edges, the possible communications. The interference constraint is modeled by a fixed integer d?1, which implies that nodes within distance d in the graph from one sender cannot receive messages from another node. In this paper, we suppose that each node has one unit-length message to transmit and, furthermore, we suppose that it takes one unit of time (slot) to transmit a unit-length message and during such a slot we can have only calls which do not interfere (called compatible calls). A set of compatible calls is referred to as a round. We give protocols and lower bounds on the minimum number of rounds for the gathering problem when the network is a path and the destination node is either at one end or at the center of the path. These protocols are shown to be optimal for any d in the first case, and for 1?d?4, in the second case.},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
x-pays={BR, CA},
sorte = "rev-int",
}
-
E. Birmelé,
J. A. Bondy,
and B. Reed.
Tree-width of graphs without a 3 by 3 grid minor.
Discrete Applied Mathematics,
157:2577--2598,
2009.
[WWW
] [PDF
]
| Abstract: |
|
We show that graphs with no minor isomorphic to the 3x3 grid have tree-width at most 7. |
@ARTICLE{BBR09,
sorte = "rev-int",
AUTHOR={E. Birmel\'e and J. A. Bondy and B. Reed},
TITLE={Tree-width of graphs without a 3 by 3 grid minor},
JOURNAL = {Discrete Applied Mathematics},
VOLUME = {157},
NUMBER = {},
YEAR = {2009},
PAGES = {2577--2598},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
abstract = {We show that graphs with no minor isomorphic to the 3x3 grid have tree-width at most 7.},
pdf = {http://stat.genopole.cnrs.fr/Members/ebirmele/page-web/publications-1/BBRGrid.pdf},
url ={http://portal.acm.org/citation.cfm?id=1553060}
}
-
R. Correa,
F. Havet,
and J-S. Sereni.
About a Brooks-type theorem for improper colouring.
Australasian Journal of Combinatorics,
43:219--230,
2009.
[PDF
]
| Abstract: |
|
A graph is $k$-improperly \l-colourable if its vertices can be partitioned into \l parts such that each part induces a subgraph of maximum degree at most $k$. A result of Lov\'asz states that for any graph $G$, such a partition exists if $\l\ge\left\lceil\frac{\Delta(G)+1}{k+1}\right\rceil$. When $k=0$, this bound can be reduced by Brooks' Theorem, unless $G$ is complete or an odd cycle. We study the following question, which can be seen as a generalisation of the celebrated Brooks' Theorem to improper colouring: does there exist a polynomial-time algorithm that decides whether a graph $G$ of maximum degree $\Delta$ has $k$-improper chromatic number at most $\lceil \frac{\Delta + 1}{k + 1} \rceil - 1$? We show that the answer is no, unless $\mathcal P = \mathcal NP$, when $\Delta = \ell(k + 1)$, $k \geq 1$ and $\ell + \sqrt{\ell} \leq 2k + 3$. We also show that, if $G$ is planar, $k=1$ or $k=2$, $\Delta = 2k + 2$, and $\ell = 2$, then the answer is still no, unless $\mathcal P = \mathcal NP$. These results answer some questions of Cowen et al. [Journal of Graph Theory 24(3):205-219, 1997]. |
@article{CHS09,
sorte = "rev-int",
author = {R. Correa and F. Havet and J-S. Sereni},
title = {About a {B}rooks-type theorem for improper colouring},
JOURNAL = {Australasian Journal of Combinatorics},
VOLUME = {43},
YEAR = {2009},
PAGES = {219--230},
abstract={A graph is $k$-improperly \l-colourable if its vertices can be partitioned into \l parts such that each part induces a subgraph of maximum degree at most $k$. A result of Lov\'asz states that for any graph $G$, such a partition exists if $\l\ge\left\lceil\frac{\Delta(G)+1}{k+1}\right\rceil$. When $k=0$, this bound can be reduced by Brooks' Theorem, unless $G$ is complete or an odd cycle. We study the following question, which can be seen as a generalisation of the celebrated Brooks' Theorem to improper colouring: does there exist a polynomial-time algorithm that decides whether a graph $G$ of maximum degree $\Delta$ has $k$-improper chromatic number at most $\lceil \frac{\Delta + 1}{k + 1} \rceil - 1$? We show that the answer is no, unless $\mathcal P = \mathcal NP$, when $\Delta = \ell(k + 1)$, $k \geq 1$ and $\ell + \sqrt{\ell} \leq 2k + 3$. We also show that, if $G$ is planar, $k=1$ or $k=2$, $\Delta = 2k + 2$, and $\ell = 2$, then the answer is still no, unless $\mathcal P = \mathcal NP$. These results answer some questions of Cowen et al. [Journal of Graph Theory 24(3):205-219, 1997].},
pdf = {ftp://ftp-sop.inria.fr/mascotte/Publications/CHS09.pdf},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
x-pays = {BR},
}
-
F. V. Fomin,
P. Fraigniaud,
and N. Nisse.
Nondeterministic Graph Searching: From Pathwidth to Treewidth.
Algorithmica,
53(3):358-373,
2009.
[WWW
] [PDF
]
| Abstract: |
|
We introduce nondeterministic graph searching with a controlled amount of nondeterminism and show how this new tool can be used in algorithm design and combinatorial analysis applying to both pathwidth and treewidth. We prove equivalence between this game-theoretic approach and graph decompositions called q -branched tree decompositions, which can be interpreted as a parameterized version of tree decompositions. Path decomposition and (standard) tree decomposition are two extreme cases of q-branched tree decompositions. The equivalence between nondeterministic graph searching and q-branched tree decomposition enables us to design an exact (exponential time) algorithm computing q-branched treewidth for all q, which is thus valid for both treewidth and pathwidth. This algorithm performs as fast as the best known exact algorithm for pathwidth. Conversely, this equivalence also enables us to design a lower bound on the amount of nondeterminism required to search a graph with the minimum number of searchers. |
@article{FFN09,
sorte = "rev-int",
author = {F. V. Fomin and P. Fraigniaud and N. Nisse},
title = {Nondeterministic Graph Searching: From Pathwidth to Treewidth},
journal = {Algorithmica},
volume = {53},
number = {3},
pages = {358-373},
year = {2009},
x-pays = {NO},
abstract = {We introduce nondeterministic graph searching with a controlled amount of nondeterminism and show how this new tool can be used in algorithm design and combinatorial analysis applying to both pathwidth and treewidth. We prove equivalence between this game-theoretic approach and graph decompositions called q -branched tree decompositions, which can be interpreted as a parameterized version of tree decompositions. Path decomposition and (standard) tree decomposition are two extreme cases of q-branched tree decompositions. The equivalence between nondeterministic graph searching and q-branched tree decomposition enables us to design an exact (exponential time) algorithm computing q-branched treewidth for all q, which is thus valid for both treewidth and pathwidth. This algorithm performs as fast as the best known exact algorithm for pathwidth. Conversely, this equivalence also enables us to design a lower bound on the amount of nondeterminism required to search a graph with the minimum number of searchers.},
url = {http://www.springerlink.com/content/42g5tp1588w89186/},
pdf={http://www.springerlink.com/content/42g5tp1588w89186/fulltext.pdf},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
}
-
J. Galtier.
Real-time resource allocation for LEO satellite constellations.
Wireless Networks,
15(6):791-803,
August 2009.
[WWW
]
| Abstract: |
|
The paper addresses the need of controling the access of terminals with guaranteed ressources on the high dynamic systems offered by LEO satellite constellations. A call-access-control scheme that guarantees the reservation of permanent resources of satellite constellations in $O(\sqrt{n}\log(n))$ time, where n is the number of user present in the system, is described. A tradeoff between computational time of call-access-control and optimization of the use of the spectrum is identified. Some experimental results are presented. |
@Article{Gal09,
author={J. Galtier},
title={Real-time resource allocation for {LEO} satellite constellations},
journal={Wireless Networks},
volume = {15},
number = {6},
pages = {791-803},
year = {2009},
month = aug,
publisher = {Springer},
url = {http://dx.doi.org/10.1007/s11276-007-0075-0},
abstract = {The paper addresses the need of controling the access of terminals with guaranteed ressources on the high dynamic systems offered by LEO satellite constellations. A call-access-control scheme that guarantees the reservation of permanent resources of satellite constellations in $O(\sqrt{n}\log(n))$ time, where n is the number of user present in the system, is described. A tradeoff between computational time of call-access-control and optimization of the use of the spectrum is identified. Some experimental results are presented. },
sorte = "rev-int",
}
-
J. Geelen,
B. Gerards,
B. Reed,
P. Seymour,
and A. Vetta.
On the odd-minor variant of Hadwiger's conjecture.
Journal of Combinatorial Theory Ser. B,
99:20--29,
2009.
[WWW
] [PDF
]
| Abstract: |
|
A Kl-expansion consists of l vertex-disjoint trees, every two of which are joined by an edge. We call such an expansion odd if its vertices can be two-coloured so that the edges of the trees are bichromatic but the edges between trees are monochromatic. We show that, for every l, if a graph contains no odd Kl-expansion then its chromatic number is View the MathML source. In doing so, we obtain a characterization of graphs which contain no odd Kl-expansion which is of independent interest. We also prove that given a graph and a subset S of its vertex set, either there are k vertex-disjoint odd paths with endpoints in S, or there is a set X of at most 2kâ2 vertices such that every odd path with both ends in S contains a vertex in X. Finally, we discuss the algorithmic implications of these results. |
@ARTICLE{GGR+09,
sorte = "rev-int",
AUTHOR={J. Geelen and B. Gerards and B. Reed and P. Seymour and A. Vetta},
TITLE={On the odd-minor variant of Hadwiger's conjecture},
JOURNAL = {Journal of Combinatorial Theory Ser. B},
VOLUME = {99},
NUMBER = {},
YEAR = {2009},
PAGES = {20--29},
x-pays = {CA,NL,US},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
abstract = {A Kl-expansion consists of l vertex-disjoint trees, every two of which are joined by an edge. We call such an expansion odd if its vertices can be two-coloured so that the edges of the trees are bichromatic but the edges between trees are monochromatic. We show that, for every l, if a graph contains no odd Kl-expansion then its chromatic number is View the MathML source. In doing so, we obtain a characterization of graphs which contain no odd Kl-expansion which is of independent interest. We also prove that given a graph and a subset S of its vertex set, either there are k vertex-disjoint odd paths with endpoints in S, or there is a set X of at most 2kâ2 vertices such that every odd path with both ends in S contains a vertex in X. Finally, we discuss the algorithmic implications of these results.},
pdf = {http://www.math.princeton.edu/~pds/papers/oddhadwiger/paper.ps},
url ={http://portal.acm.org/citation.cfm?id=1465824}
}
-
F. Giroire.
Order statistics and estimating cardinalities of massive data sets.
Discrete Applied Mathematics,
157(2):406-427,
2009.
[WWW
] [PDF
]
| Abstract: |
|
A new class of algorithms to estimate the cardinality of very large multisets using constant memory and doing only one pass on the data is introduced here. It is based on order statistics rather than on bit patterns in binary representations of numbers. Three families of estimators are analyzed. They attain a standard error of using M units of storage, which places them in the same class as the best known algorithms so far. The algorithms have a very simple internal loop, which gives them an advantage in terms of processing speed. For instance, a memory of only 12 kB and only few seconds are sufficient to process a multiset with several million elements and to build an estimate with accuracy of order 2 percent. The algorithms are validated both by mathematical analysis and by experimentations on real internet traffic. |
@article{Gir09,
author = {F. Giroire},
title = {Order statistics and estimating cardinalities of massive data sets},
year = {2009},
volume = {157},
number = {2},
pages = {406-427},
journal = {Discrete Applied Mathematics},
url = {http://dx.doi.org/10.1016/j.dam.2008.06.020},
pdf = {http://www-sop.inria.fr/members/Frederic.Giroire/publis/Gir08.pdf},
abstract = {A new class of algorithms to estimate the cardinality of very large multisets using constant memory and doing only one pass on the data is introduced here. It is based on order statistics rather than on bit patterns in binary representations of numbers. Three families of estimators are analyzed. They attain a standard error of using M units of storage, which places them in the same class as the best known algorithms so far. The algorithms have a very simple internal loop, which gives them an advantage in terms of processing speed. For instance, a memory of only 12 kB and only few seconds are sufficient to process a multiset with several million elements and to build an estimate with accuracy of order 2 percent. The algorithms are validated both by mathematical analysis and by experimentations on real internet traffic.},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
sorte = "rev-int",
}
-
F. Havet,
R. Kang,
T. Müller,
and J.-S. Sereni.
Circular choosability.
Journal of Graph Theory,
61(4):241--334,
2009.
[PDF
]
| Abstract: |
|
We study circular choosability, a notion recently introduced by Mohar and by Zhu. First, we provide a negative answer to a question of Zhu about circular cliques. We next prove that $\cch(G) = O\left( \ch(G) + \ln |V(G)| \right)$ for every graph $G$. We investigate a generalisation of circular choosability, the circular $f$-choosability, where $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\text{ is planar}}$, and we prove that $6\le\tau\le8$, thereby providing a negative answer to another question of Mohar. We also study the circular choice number of planar and outerplanar graphs with prescribed girth, and graphs with bounded density. |
@ARTICLE{HKM+09,
sorte = "rev-int",
AUTHOR={F. Havet and R. Kang and T. M\"uller and J.-S. Sereni},
TITLE={Circular choosability},
JOURNAL = {Journal of Graph Theory},
VOLUME = {61},
NUMBER = {4},
YEAR = {2009},
PAGES = {241--334},
abstract={We study circular choosability, a notion recently introduced by Mohar and by Zhu. First, we provide a negative answer to a question of Zhu about circular cliques. We next prove that $\cch(G) = O\left( \ch(G) + \ln |V(G)| \right)$ for every graph $G$. We investigate a generalisation of circular choosability, the circular $f$-choosability, where $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\text{ is planar}}$, and we prove that $6\le\tau\le8$, thereby providing a negative answer to another question of Mohar. We also study the circular choice number of planar and outerplanar graphs with prescribed girth, and graphs with bounded density.},
pdf = {ftp://ftp-sop.inria.fr/mascotte/Publications/HKM+09.pdf},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
x-pays = {CA, CZ}
}
-
F. Havet,
R. Kang,
and J.-S. Sereni.
Improper Colouring of Unit Disk Graphs.
Networks,
54(3):150--164,
2009.
| Abstract: |
|
Motivated by a satellite communications problem, we consider a generalised colouring problem on unit disk graphs. A colouring is \emph{$k$-improper} if no more than $k$ neighbours of every vertex have the same colour as that assigned to the vertex. The \emph{$k$-improper chromatic number $\chi^k(G)$} is the least number of colours needed in a $k$-improper colouring of a graph $G$. The main subject of this work is analysing the complexity of computing $\chi^k$ for the class of unit disk graphs and some related classes, e.g.~hexagonal graphs and interval graphs. We show NP-completeness in many restricted cases and also provide both positive and negative approximability results. Due to the challenging nature of this topic, many seemingly simple questions remain: for example, it remains open to determine the complexity of computing $\chi^k$ for unit interval graphs. |
@Article{HKS09,
sorte = "rev-int",
AUTHOR={F. Havet and R. Kang and J.-S. Sereni},
TITLE={Improper Colouring of Unit Disk Graphs},
JOURNAL = {Networks},
VOLUME = {54},
NUMBER = {3},
YEAR = {2009},
PAGES = {150--164},
abstract={Motivated by a satellite communications problem, we consider a generalised colouring problem on unit disk graphs. A colouring is \emph{$k$-improper} if no more than $k$ neighbours of every vertex have the same colour as that assigned to the vertex. The \emph{$k$-improper chromatic number $\chi^k(G)$} is the least number of colours needed in a $k$-improper colouring of a graph $G$. The main subject of this work is analysing the complexity of computing $\chi^k$ for the class of unit disk graphs and some related classes, e.g.~hexagonal graphs and interval graphs. We show NP-completeness in many restricted cases and also provide both positive and negative approximability results. Due to the challenging nature of this topic, many seemingly simple questions remain: for example, it remains open to determine the complexity of computing $\chi^k$ for unit interval graphs.}
}
-
F. Havet and S. Thomassé.
Complexity of $(p,1)$-total labelling.
Dicrete Applied Mathematics,
157:2859--2870,
2009.
[PDF
]
| Abstract: |
|
A {\it $(p,1)$-total labelling} of a graph $G=(V,E)$ is a total coloring $L$ from $V\cup E$ into ${0,\dots ,l}$ such that $|L(v)-L(e)|\geq p$ whenever an edge $e$ is incident to a vertex $v$. The minimum $l$ for which $G$ admits a $(p,1)$-total labelling is denoted by $\lambda_p(G)$. The case $p=1$ corresponds to the usual notion of total colouring, which is NP-hard to compute even for cubic bipartite graphs~\cite{MDSA94}. In this paper we assume $p\geq 2$. It is easy to show that $\lambda_p(G)\geq \Delta +p-1$, where $\Delta$ is the maximum degree of $G$. Moreover, when $G$ is bipartite, $\Delta +p$ is an upper bound for $\lambda_p(G)$, leaving only two possible values. In this paper, we completely settle the computational complexity of deciding whether $\lambda_p(G)$ is equal to $\Delta +p-1$ or to $\Delta +p$ when $G$ is bipartite. This is trivial when $\Delta \leq p$, polynomial when $\Delta =3$ and $p=2$, and NP-complete in the remaining cases. |
@ARTICLE{HaTh09,
sorte = "rev-int",
AUTHOR={F. Havet and S. Thomass\'e},
TITLE={Complexity of $(p,1)$-total labelling},
JOURNAL = {Dicrete Applied Mathematics},
VOLUME = {157},
NUMBER = {},
YEAR = {2009},
PAGES = {2859--2870},
abstract={ A {\it $(p,1)$-total labelling} of a graph $G=(V,E)$ is a total coloring $L$ from $V\cup E$ into ${0,\dots ,l}$ such that $|L(v)-L(e)|\geq p$ whenever an edge $e$ is incident to a vertex $v$. The minimum $l$ for which $G$ admits a $(p,1)$-total labelling is denoted by $\lambda_p(G)$. The case $p=1$ corresponds to the usual notion of total colouring, which is NP-hard to compute even for cubic bipartite graphs~\cite{MDSA94}. In this paper we assume $p\geq 2$. It is easy to show that $\lambda_p(G)\geq \Delta +p-1$, where $\Delta$ is the maximum degree of $G$. Moreover, when $G$ is bipartite, $\Delta +p$ is an upper bound for $\lambda_p(G)$, leaving only two possible values. In this paper, we completely settle the computational complexity of deciding whether $\lambda_p(G)$ is equal to $\Delta +p-1$ or to $\Delta +p$ when $G$ is bipartite. This is trivial when $\Delta \leq p$, polynomial when $\Delta =3$ and $p=2$, and NP-complete in the remaining cases.},
pdf = {ftp://ftp-sop.inria.fr/mascotte/Publications/HaTh09.pdf},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
}
-
F. Havet.
Choosability of the square of planar subcubic graphs with large girth.
Discrete Mathematics,
309:3553--3563,
2009.
[PDF
]
| Abstract: |
|
We show that the choice 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 choice number of the square of a subcubic planar graph with girth at least $9$ is at most $6$. We then show that the choice number of the square of a subcubic planar graph with girth at least $13$ is at most $5$. |
@ARTICLE{Hav09,
sorte = "rev-int",
AUTHOR={F. Havet},
TITLE={Choosability of the square of planar subcubic graphs with large girth},
JOURNAL = {Discrete Mathematics},
VOLUME = {309},
NUMBER = {},
YEAR = {2009},
PAGES = {3553--3563},
abstract={ We show that the choice 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 choice number of the square of a subcubic planar graph with girth at least $9$ is at most $6$. We then show that the choice number of the square of a subcubic planar graph with girth at least $13$ is at most $5$.},
pdf = {ftp://ftp-sop.inria.fr/mascotte/Publications/Hav07.pdf},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
}
-
F. Huc,
I. Sau,
and J. Zerovnik.
$(\ell,k)$-Routing on Plane Grids.
Journal of Interconnection Networks,
10(1-2):27-57,
2009.
[PDF
]
| Abstract: |
|
The packet routing problem plays an essential role in communication networks. It involves how to transfer data from some origins to some destinations within a reasonable amount of time. In the $(\ell,k)$-routing problem, each node can send at most $\ell$ packets and receive at most $k$ packets. Permutation routing is the particular case $\ell=k=1$. In the $r$-central routing problem, all nodes at distance at most $r$ from a fixed node $v$ want to send a packet to $v$. In this article we study the permutation routing, the $r$-central routing and the general $(\ell,k)$-routing problems on plane grids, that is square grids, triangular grids and hexagonal grids. We use the \emph{store-and-forward} $\Delta$-port model, and we consider both full and half-duplex networks. The main contributions are the following: \begin{itemize} \item[1.] Tight permutation routing algorithms on full-duplex hexagonal grids, and half duplex triangular and hexagonal grids. \item[2.] Tight $r$-central routing algorithms on triangular and hexagonal grids. \item[3.] Tight $(k,k)$-routing algorithms on square, triangular and hexagonal grids. \item[4.] Good approximation algorithms (in terms of running time) for $(\ell,k)$-routing on square, triangular and hexagonal grids, together with new lower bounds on the running time of any algorithm using shortest path routing. \end{itemize} \noindent All these algorithms are completely distributed, i.e. can be implemented independently at each node. Finally, we also formulate the $(\ell,k)$-routing problem as a \textsc{Weighted Edge Coloring} problem on bipartite graphs. |
@ARTICLE{HSZ09,
sorte = "rev-int",
AUTHOR = {F. Huc and I. Sau and J. \v{Z}erovnik},
TITLE = {{$(\ell,k)$-Routing on Plane Grids}},
JOURNAL = {Journal of Interconnection Networks},
volume = {10},
number = {1-2},
pages = {27-57},
year = {2009},
abstract = {The packet routing problem plays an essential role in communication networks. It involves how to transfer data from some origins to some destinations within a reasonable amount of time. In the $(\ell,k)$-routing problem, each node can send at most $\ell$ packets and receive at most $k$ packets. Permutation routing is the particular case $\ell=k=1$. In the $r$-central routing problem, all nodes at distance at most $r$ from a fixed node $v$ want to send a packet to $v$. In this article we study the permutation routing, the $r$-central routing and the general $(\ell,k)$-routing problems on plane grids, that is square grids, triangular grids and hexagonal grids. We use the \emph{store-and-forward} $\Delta$-port model, and we consider both full and half-duplex networks. The main contributions are the following: \begin{itemize} \item[1.] Tight permutation routing algorithms on full-duplex hexagonal grids, and half duplex triangular and hexagonal grids. \item[2.] Tight $r$-central routing algorithms on triangular and hexagonal grids. \item[3.] Tight $(k,k)$-routing algorithms on square, triangular and hexagonal grids. \item[4.] Good approximation algorithms (in terms of running time) for $(\ell,k)$-routing on square, triangular and hexagonal grids, together with new lower bounds on the running time of any algorithm using shortest path routing. \end{itemize} \noindent All these algorithms are completely distributed, i.e. can be implemented independently at each node. Finally, we also formulate the $(\ell,k)$-routing problem as a \textsc{Weighted Edge Coloring} problem on bipartite graphs.},
pdf = {ftp://ftp-sop.inria.fr/mascotte/Publications/HSZ09.pdf},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
}
-
D. Ilcinkas,
N. Nisse,
and D. Soguet.
The Cost of Monotonicity in Distributed Graph Searching.
Distributed Computing,
22(2):117-127,
2009.
[WWW
] [PDF
]
| Abstract: |
|
Blin et al. (TCS 2008) proposed a dis- tributed protocol enabling the smallest possible num- ber of searchers to clear any unknown graph in a de- centralized manner. However, the strategy that is actu- ally performed lacks of an important property, namely the monotonicity. This paper deals with the smallest number of searchers that are necessary and sufficient to monotonously clear any unknown graph in a decen- tralized manner. The clearing of the graph is required to be connected, i.e., the clear part of the graph must remain permanently connected, and monotone, i.e., the clear part of the graph only grows. We prove that a dis- tributed protocol clearing any unknown n-node graph in a monotone connected way, in a decentralized set- ting, can achieve but cannot beat competitive ratio of Theta(log n /n), compared with the centralized minimum number of searchers. Moreover, our lower bound holds even in a synchronous setting, while our constructive upper bound holds even in an asynchronous setting. |
@article{INS09,
sorte = "rev-int",
author = {D. Ilcinkas and N. Nisse and D. Soguet},
title = {The Cost of Monotonicity in Distributed Graph Searching},
journal = {Distributed Computing},
volume = {22},
number = {2},
year = {2009},
pages = {117-127},
abstract = {Blin et al. (TCS 2008) proposed a dis- tributed protocol enabling the smallest possible num- ber of searchers to clear any unknown graph in a de- centralized manner. However, the strategy that is actu- ally performed lacks of an important property, namely the monotonicity. This paper deals with the smallest number of searchers that are necessary and sufficient to monotonously clear any unknown graph in a decen- tralized manner. The clearing of the graph is required to be connected, i.e., the clear part of the graph must remain permanently connected, and monotone, i.e., the clear part of the graph only grows. We prove that a dis- tributed protocol clearing any unknown n-node graph in a monotone connected way, in a decentralized set- ting, can achieve but cannot beat competitive ratio of Theta(log n /n), compared with the centralized minimum number of searchers. Moreover, our lower bound holds even in a synchronous setting, while our constructive upper bound holds even in an asynchronous setting.},
url = {http://www.springerlink.com/content/l8371258177lv2j0/},
pdf = {http://www-sop.inria.fr/members/Nicolas.Nisse/publications/IlcinkasNisseSoguet.pdf},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
}
-
A. Jarry and S. Pérennes.
Disjoint Path in symmetric Graphs.
Discrete Applied Mathematics,
157(1):90-97,
2009.
@article{JP09,
sorte = "rev-int",
author={A. Jarry and S. P\'erennes},
title={Disjoint Path in symmetric Graphs},
journal={Discrete Applied Mathematics},
volume={157},
number = {1},
pages={90-97},
year={2009},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
}
-
K. Kawarabayashi,
O. Lee,
and B. Reed.
Removable cycles in non-bipartite graphs.
Journal of Combinatorial Theory Ser. B,
99:30--38,
2009.
[WWW
]
| Abstract: |
|
In this paper we prove the following result. Suppose that s and t are vertices of a 3-connected graph G such that G-s-t is not bipartite and there is no cutset X of size three in G for which some component U of G-X is disjoint from {s,t}. Then either (1) G contains an induced path P from s to t such that G-V(P) is not bipartite or (2) G can be embedded in the plane so that every odd face contains one of s or t. Furthermore, if (1) holds then we can insist that G-V(P) is connected, while if G is 5-connected then (1) must hold and P can be chosen so that G-V(P) is 2-connected. |
@ARTICLE{KLR09,
sorte = "rev-int",
AUTHOR={K. Kawarabayashi and O. Lee and B. Reed},
TITLE={Removable cycles in non-bipartite graphs},
JOURNAL = {Journal of Combinatorial Theory Ser. B},
VOLUME = {99},
NUMBER = {},
YEAR = {2009},
PAGES = {30--38},
x-pays = {JP,BR},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
abstract = {In this paper we prove the following result. Suppose that s and t are vertices of a 3-connected graph G such that G-s-t is not bipartite and there is no cutset X of size three in G for which some component U of G-X is disjoint from {s,t}. Then either (1) G contains an induced path P from s to t such that G-V(P) is not bipartite or (2) G can be embedded in the plane so that every odd face contains one of s or t. Furthermore, if (1) holds then we can insist that G-V(P) is connected, while if G is 5-connected then (1) must hold and P can be chosen so that G-V(P) is 2-connected.},
pdf = {},
url ={http://portal.acm.org/citation.cfm?id=1465820}
}
-
K. Kawarabayashi and B. Reed.
Highly parity linked graphs.
Combinatorica,
29:215--225,
2009.
[WWW
]
| Abstract: |
|
A graph G is k-linked if G has at least 2k vertices, and for any 2k vertices x 1,x 2, â¦, x k ,y 1,y 2, â¦, y k , G contains k pairwise disjoint paths P 1, â¦, P k such that P i joins x i and y i for i = 1,2, â¦, k. We say that G is parity-k-linked if G is k-linked and, in addition, the paths P 1, â¦, P k can be chosen such that the parities of their length are prescribed. Thomassen [22] was the first to prove the existence of a function f(k) such that every f(k)-connected graph is parity-k-linked if the deletion of any 4k-3 vertices leaves a nonbipartite graph. In this paper, we will show that the above statement is still valid for 50k-connected graphs. This is the first result that connectivity which is a linear function of k guarantees the ErdÅs-Pósa type result for parity-k-linked graphs. |
@ARTICLE{KaRe09,
sorte = "rev-int",
AUTHOR={K. Kawarabayashi and B. Reed},
TITLE={Highly parity linked graphs},
JOURNAL = {Combinatorica},
VOLUME = {29},
NUMBER = {},
YEAR = {2009},
PAGES = {215--225},
x-pays = {JP},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
abstract = {A graph G is k-linked if G has at least 2k vertices, and for any 2k vertices x 1,x 2, â¦, x k ,y 1,y 2, â¦, y k , G contains k pairwise disjoint paths P 1, â¦, P k such that P i joins x i and y i for i = 1,2, â¦, k. We say that G is parity-k-linked if G is k-linked and, in addition, the paths P 1, â¦, P k can be chosen such that the parities of their length are prescribed. Thomassen [22] was the first to prove the existence of a function f(k) such that every f(k)-connected graph is parity-k-linked if the deletion of any 4k-3 vertices leaves a nonbipartite graph. In this paper, we will show that the above statement is still valid for 50k-connected graphs. This is the first result that connectivity which is a linear function of k guarantees the ErdÅs-Pósa type result for parity-k-linked graphs.},
pdf = {},
url ={http://portal.acm.org/citation.cfm?id=1569773}
}
-
R. Klasing,
Z. Lotker,
A. Navarra,
and S. Pérennes.
From Balls and Bins to Points and Vertices.
Algorithmic Operations Research (AlgOR),
4(2):133-143,
2009.
| Abstract: |
|
Given a graph $G = (V, E)$ with $|V| = n$, we consider the following problem. Place $m = n$ points on the vertices of G independently and uniformly at random. Once the points are placed, relocate them using a bijection from the points to the vertices that minimizes the maximum distance between the random place of the points and their target vertices. We look for an upper bound on this maximum relocation distance that holds with high probability (over the initial placements of the points). For general graphs and in the case $m \leq n$, we prove the $\#P$-hardness of the problem and that the maximum relocation distance is ${\cal O}(\sqrt{n})$ with high probability. We present a Fully Polynomial Randomized Approximation Scheme when the input graph admits a polynomial-size family of witness cuts while for trees we provide a 2-approximation algorithm. Many applications concern the variation in which $m = (1 â q)n for some 0 < q < 1$. We provide several bounds for the maximum relocation distance according to different graph topologies. |
@article{KLN+09,
sorte = "rev-int",
author = {R. Klasing and Z. Lotker and A. Navarra and S. P\'erennes},
title = {From Balls and Bins to Points and Vertices},
journal = {Algorithmic Operations Research (AlgOR)},
volume = {4},
number = {2},
pages = {133-143},
year = {2009},
abstract = {Given a graph $G = (V, E)$ with $|V| = n$, we consider the following problem. Place $m = n$ points on the vertices of G independently and uniformly at random. Once the points are placed, relocate them using a bijection from the points to the vertices that minimizes the maximum distance between the random place of the points and their target vertices. We look for an upper bound on this maximum relocation distance that holds with high probability (over the initial placements of the points). For general graphs and in the case $m \leq n$, we prove the $\#P$-hardness of the problem and that the maximum relocation distance is ${\cal O}(\sqrt{n})$ with high probability. We present a Fully Polynomial Randomized Approximation Scheme when the input graph admits a polynomial-size family of witness cuts while for trees we provide a 2-approximation algorithm. Many applications concern the variation in which $m = (1 â q)n for some 0 < q < 1$. We provide several bounds for the maximum relocation distance according to different graph topologies.},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
}
-
B. Lévêque,
F. Maffray,
B. Reed,
and N. Trotignon.
Coloring Artemis graphs.
Theoretical Computer Science,
410:2234--2240,
2009.
[WWW
] [PDF
]
| Abstract: |
|
We consider the class of graphs that contain no odd hole, no antihole, and no ''prism'' (a graph consisting of two disjoint triangles with three disjoint paths between them). We give an algorithm that can optimally color the vertices of these graphs in time O(n^2m). |
@ARTICLE{LMRT09,
sorte = "rev-int",
AUTHOR={B. L\'ev\^eque and F. Maffray and B. Reed and N. Trotignon},
TITLE={Coloring Artemis graphs},
JOURNAL = {Theoretical Computer Science},
VOLUME = {410},
NUMBER = {},
YEAR = {2009},
PAGES = {2234--2240},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
abstract = {We consider the class of graphs that contain no odd hole, no antihole, and no ''prism'' (a graph consisting of two disjoint triangles with three disjoint paths between them). We give an algorithm that can optimally color the vertices of these graphs in time O(n^2m).},
pdf = {www.lirmm.fr/~leveque/Publications/ColArtemis-TCS.pdf},
url ={http://portal.acm.org/citation.cfm?id=1530984}
}
-
G. B. Mertzios,
I. Sau,
and S. Zaks.
A New Intersection Model and Improved Algorithms for Tolerance Graphs.
SIAM Journal on Discrete Mathematics,
23:1800-1813,
2009.
[WWW
] [PDF
]
| Abstract: |
|
Tolerance graphs model interval relations in such a way that intervals can tolerate a certain degree of overlap without being in conflict. This class of graphs, which generalizes in a natural way both interval and permutation graphs, has attracted many research efforts since their introduction in [10], as it finds many important applications in constraint-based temporal reasoning, resource allocation, and scheduling problems, among others. In this article we propose the first non-trivial intersection model for general tolerance graphs, given by three-dimensional parallelepipeds, which extends the widely known intersection model of parallelograms in the plane that characterizes the class of bounded tolerance graphs. Apart from being important on its own, this new representation also enables us to improve the time complexity of three problems on tolerance graphs. Namely, we present optimal $O(n log n)$ algorithms for computing a minimum coloring and a maximum clique, and an $O(n^2)$ algorithm for computing a maximum weight independent set in a tolerance graph with $n$ vertices, thus improving the best known running times $O(n^2)$ and $O(n^3)$ for these problems, respectively |
@article{MSZ09b,
sorte = "rev-int",
AUTHOR = {G. B. Mertzios and I. Sau and S. Zaks},
TITLE = {{A New Intersection Model and Improved Algorithms for Tolerance Graphs}},
JOURNAL = {SIAM Journal on Discrete Mathematics},
year = {2009},
volume = {23},
issue = {4},
pages = {1800-1813},
pdf = {ftp://ftp-sop.inria.fr/mascotte/Publications/MSZ09b.pdf},
url = {http://dx.doi.org/10.1137/09075994X},
abstract = {Tolerance graphs model interval relations in such a way that intervals can tolerate a certain degree of overlap without being in conflict. This class of graphs, which generalizes in a natural way both interval and permutation graphs, has attracted many research efforts since their introduction in [10], as it finds many important applications in constraint-based temporal reasoning, resource allocation, and scheduling problems, among others. In this article we propose the first non-trivial intersection model for general tolerance graphs, given by three-dimensional parallelepipeds, which extends the widely known intersection model of parallelograms in the plane that characterizes the class of bounded tolerance graphs. Apart from being important on its own, this new representation also enables us to improve the time complexity of three problems on tolerance graphs. Namely, we present optimal $O(n log n)$ algorithms for computing a minimum coloring and a maximum clique, and an $O(n^2)$ algorithm for computing a maximum weight independent set in a tolerance graph with $n$ vertices, thus improving the best known running times $O(n^2)$ and $O(n^3)$ for these problems, respectively},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
x-pays = {ES,IS,DE},
}
-
N. Nisse and D. Soguet.
Graph Searching with Advice.
Theoretical Computer Science,
410(14):1307-1318,
2009.
[WWW
] [PDF
]
| Abstract: |
|
Fraigniaud et al. [L. Blin, P. Fraigniaud, N. Nisse, S. Vial, Distributing chasing of network intruders, in: 13th Colloquium on Structural Information and Communication Complexity, SIROCCO, in: LNCS, vol. 4056, Springer-Verlag, 2006, pp. 70--84] introduced a new measure of difficulty for a distributed task in a network. The smallest number of bits of advice of a distributed problem is the smallest number of bits of information that has to be available to nodes in order to accomplish the task efficiently. Our paper deals with the number of bits of advice required to perform efficiently the graph searching problem in a distributed setting. In this variant of the problem, all searchers are initially placed at a particular node of the network. The aim of the team of searchers is to clear a contaminated graph in a monotone connected way, i.e., the cleared part of the graph is permanently connected, and never decreases while the search strategy is executed. Moreover, the clearing of the graph must be performed using the optimal number of searchers, i.e. the minimum number of searchers sufficient to clear the graph in a monotone connected way in a centralized setting. We show that the minimum number of bits of advice permitting the monotone connected and optimal clearing of a network in a distributed setting is $\Theta(nlogn)$, where n is the number of nodes of the network. More precisely, we first provide a labelling of the vertices of any graph G, using a total of O(nlogn) bits, and a protocol using this labelling that enables the optimal number of searchers to clear G in a monotone connected distributed way. Then, we show that this number of bits of advice is optimal: any distributed protocol requires $\Omega(nlogn)$ bits of advice to clear a network in a monotone connected way, using an optimal number of searchers. |
@article{NiSo09,
sorte = "rev-int",
author = {N. Nisse and D. Soguet},
title = {Graph Searching with Advice},
journal = {Theoretical Computer Science},
year = {2009},
volume = {410},
number = {14},
pages = {1307-1318},
abstract = {Fraigniaud et al. [L. Blin, P. Fraigniaud, N. Nisse, S. Vial, Distributing chasing of network intruders, in: 13th Colloquium on Structural Information and Communication Complexity, SIROCCO, in: LNCS, vol. 4056, Springer-Verlag, 2006, pp. 70--84] introduced a new measure of difficulty for a distributed task in a network. The smallest number of bits of advice of a distributed problem is the smallest number of bits of information that has to be available to nodes in order to accomplish the task efficiently. Our paper deals with the number of bits of advice required to perform efficiently the graph searching problem in a distributed setting. In this variant of the problem, all searchers are initially placed at a particular node of the network. The aim of the team of searchers is to clear a contaminated graph in a monotone connected way, i.e., the cleared part of the graph is permanently connected, and never decreases while the search strategy is executed. Moreover, the clearing of the graph must be performed using the optimal number of searchers, i.e. the minimum number of searchers sufficient to clear the graph in a monotone connected way in a centralized setting. We show that the minimum number of bits of advice permitting the monotone connected and optimal clearing of a network in a distributed setting is $\Theta(nlogn)$, where n is the number of nodes of the network. More precisely, we first provide a labelling of the vertices of any graph G, using a total of O(nlogn) bits, and a protocol using this labelling that enables the optimal number of searchers to clear G in a monotone connected distributed way. Then, we show that this number of bits of advice is optimal: any distributed protocol requires $\Omega(nlogn)$ bits of advice to clear a network in a monotone connected way, using an optimal number of searchers.},
url = {http://www.springerlink.com/content/10t1l145m1182477/},
pdf={http://www.springerlink.com/content/10t1l145m1182477/fulltext.pdf},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
}
-
N. Nisse.
Connected graph searching in chordal graphs.
Discrete Applied Mathematics,
157(12):2603-2610,
2009.
[WWW
] [PDF
]
| Abstract: |
|
Graph searching was introduced by Parson [T. Parson, Pursuit-evasion in a graph, in: Theory and Applications of Graphs, in: Lecture Notes in Mathematics, Springer-Verlag, 1976, pp. 426--441]: given a contaminated graph G (e.g., a network containing a hostile intruder), the search number s(G) of the graph G is the minimum number of searchers needed to clear the graph (or to capture the intruder). A search strategy is connected if, at every step of the strategy, the set of cleared edges induces a connected subgraph. The connected search number cs(G) of a graph G is the minimum k such that there exists a connected search strategy for the graph G using at most k searchers. This paper is concerned with the ratio between the connected search number and the search number. We prove that, for any chordal graph G of treewidth tw(G), cs(G)/s(G)=O(tw(G)). More precisely, we propose a polynomial-time algorithm that, given any chordal graph G, computes a connected search strategy for G using at most (tw(G)+2)(2s(G)-1) searchers. Our main tool is the notion of connected tree-decomposition. We show that, for any connected graph G of chordality k, there exists a connected search strategy using at most (tw(G)^{k/2}+2)(2s(T)-1) searchers where T is an optimal tree-decomposition of G. |
@article{Nis09,
sorte = "rev-int",
author = {N. Nisse},
title = {Connected graph searching in chordal graphs},
journal = {Discrete Applied Mathematics},
volume = {157},
number = {12},
pages = {2603-2610},
year = {2009},
abstract = {Graph searching was introduced by Parson [T. Parson, Pursuit-evasion in a graph, in: Theory and Applications of Graphs, in: Lecture Notes in Mathematics, Springer-Verlag, 1976, pp. 426--441]: given a contaminated graph G (e.g., a network containing a hostile intruder), the search number s(G) of the graph G is the minimum number of searchers needed to clear the graph (or to capture the intruder). A search strategy is connected if, at every step of the strategy, the set of cleared edges induces a connected subgraph. The connected search number cs(G) of a graph G is the minimum k such that there exists a connected search strategy for the graph G using at most k searchers. This paper is concerned with the ratio between the connected search number and the search number. We prove that, for any chordal graph G of treewidth tw(G), cs(G)/s(G)=O(tw(G)). More precisely, we propose a polynomial-time algorithm that, given any chordal graph G, computes a connected search strategy for G using at most (tw(G)+2)(2s(G)-1) searchers. Our main tool is the notion of connected tree-decomposition. We show that, for any connected graph G of chordality k, there exists a connected search strategy using at most (tw(G)^{k/2}+2)(2s(T)-1) searchers where T is an optimal tree-decomposition of G.},
url = {http://portal.acm.org/citation.cfm?id=1553062},
pdf = {http://www.sciencedirect.com/science?_ob=MImg&_imagekey=B6TYW-4TC2RT8-1-5&_cdi=5629&_user=10&_orig=search&_coverDate=090.00000003-16231083800624715025648228832155020226166892719138018421525037632987473280314397391192269858494702975413828793994344961730315854330232890054744206295222504730102436050490447205944018758853219057263022459675248963747430121648560444313413255982990181978237473570041841837066007183829415589688357099523473932288.0000002008&_sk=999999999&view=c&wchp=dGLbVtb-zSkzV&md5=7b91cf0e2d0c8e82bebf037c73af4ad1&ie=/sdarticle.pdf},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
}
-
E. Altman,
P. Nain,
and J-C. Bermond.
Distributed Storage Management of Evolving Files in Delay Tolerant Ad Hoc Networks.
In INFOCOM 2009,
Rio De Janeiro, Brazil,
pages 1431 - 1439,
April 2009.
[WWW
] [PDF
]
| Abstract: |
|
This work focuses on a class of distributed storage systems whose content may evolve over time. Each component or node of the storage system is mobile and the set of all nodes forms a delay tolerant (ad hoc) network (DTN). The goal of the paper is to study efficient ways for distributing evolving files within DTNs and for managing dynamically their content. We specify to dynamic files where not only the latest version is useful but also previous ones; we restrict however to files where a file has no use if another more recent version is available. There are $N+1$ mobile nodes including a {\em single} source which at some points in time makes available a new version of a {\em single} file $F$. We consider both the cases when (a) nodes do not cooperate and (b) nodes cooperate. In case (a) only the source may transmit a copy of the latest version of $F$ to a node that it meets, while in case (b) any node may transmit a copy of $F$ to a node that it meets. A file management policy is a set of rules specifying when a node may send a copy of $F$ to a node that it meets. The objective is to find file management policies which maximize some system utility functions under a constraint on the resource consumption. Both myopic ({\em static}) and state-dependent ({\em dynamic}) policies are considered, where the state of a node is the age of the copy of $F$ it carries. Scenario (a) is studied under the assumption that the source updates $F$ at discrete times $t=0,1,\ldots$. During a slot $[t,t+1)$ the source meets any node with a fixed probability. We find the optimal static (resp. dynamic) policy which maximizes a general utility function under a constraint on the number of transmissions within a slot. In particular, we show the existence of a threshold dynamic policy. In scenario (b) $F$ is updated at random points in time, with the consequence that between two meetings with the source a node does not know the age evolution of the version of $F$ it holds. Under Markovian assumptions regarding nodes mobility and update frequency of $F$, we study the stability of the system (aging of the nodes) and derive an (approximate) optimal static policy. We then revisit scenario (a) when the source does not know parameter $N$ (node population) and $q$ (node meeting probability) and derive a stochastic approximation algorithm which we show to converge to the optimal static policy found in the complete information setting. Numerical results illustrate the respective performance of optimal static and dynamic policies as well as the benefit of node cooperation. |
@inproceedings{ANB09,
author = {E. Altman and P. Nain and J-C. Bermond},
title = {Distributed Storage Management of Evolving Files in Delay Tolerant Ad Hoc Networks},
booktitle= {INFOCOM 2009},
year= {2009},
month = apr,
pages = {1431 - 1439},
address = {Rio De Janeiro, Brazil },
OPTnote = {},
OPTannote = {},
url = {http://dx.doi.org/10.1109/INFCOM.2009.5062059},
PDF={http://www-sop.inria.fr/members/Jean-Claude.Bermond//PUBLIS/ABN08.pdf},
abstract = {This work focuses on a class of distributed storage systems whose content may evolve over time. Each component or node of the storage system is mobile and the set of all nodes forms a delay tolerant (ad hoc) network (DTN). The goal of the paper is to study efficient ways for distributing evolving files within DTNs and for managing dynamically their content. We specify to dynamic files where not only the latest version is useful but also previous ones; we restrict however to files where a file has no use if another more recent version is available. There are $N+1$ mobile nodes including a {\em single} source which at some points in time makes available a new version of a {\em single} file $F$. We consider both the cases when (a) nodes do not cooperate and (b) nodes cooperate. In case (a) only the source may transmit a copy of the latest version of $F$ to a node that it meets, while in case (b) any node may transmit a copy of $F$ to a node that it meets. A file management policy is a set of rules specifying when a node may send a copy of $F$ to a node that it meets. The objective is to find file management policies which maximize some system utility functions under a constraint on the resource consumption. Both myopic ({\em static}) and state-dependent ({\em dynamic}) policies are considered, where the state of a node is the age of the copy of $F$ it carries. Scenario (a) is studied under the assumption that the source updates $F$ at discrete times $t=0,1,\ldots$. During a slot $[t,t+1)$ the source meets any node with a fixed probability. We find the optimal static (resp. dynamic) policy which maximizes a general utility function under a constraint on the number of transmissions within a slot. In particular, we show the existence of a threshold dynamic policy. In scenario (b) $F$ is updated at random points in time, with the consequence that between two meetings with the source a node does not know the age evolution of the version of $F$ it holds. Under Markovian assumptions regarding nodes mobility and update frequency of $F$, we study the stability of the system (aging of the nodes) and derive an (approximate) optimal static policy. We then revisit scenario (a) when the source does not know parameter $N$ (node population) and $q$ (node meeting probability) and derive a stochastic approximation algorithm which we show to converge to the optimal static policy found in the complete information setting. Numerical results illustrate the respective performance of optimal static and dynamic policies as well as the benefit of node cooperation.},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
sorte = "conf-int",
}
-
J. Araujo,
N. Cohen,
F. Giroire,
and F. Havet.
Good edge-labelling of graphs.
In proceedings of the Latin-American Algorithms, Graphs and Optimization Symposium (LAGOS'09),
volume 35 of Electronic Notes in Discrete Mathematics,
Gramado, Brazil,
pages 275--280,
December 2009.
Springer.
[PDF
]
| Abstract: |
|
A good edge-labelling of a graph G is a labelling of its edges such that for any two distinct vertices u, v, there is at most one (u,v)-path with non-decreasing labels. This notion was introduced in [J-C. Bermond, M. Cosnard, and S. Pérennes. Directed acyclic graphs with unique path property. Technical Report RR-6932, INRIA, May 2009] to solve wavelength assignment problems for specific categories of graphs. In this paper, we aim at characterizing the class of graphs that admit a good edge-labelling. First, we exhibit infinite families of graphs for which no such edge-labelling can be found. We then show that deciding if a graph admits a good edge-labelling is NP-complete. Finally, we give large classes of graphs admitting a good edge-labelling: C3-free outerplanar graphs, planar graphs of girth at least 6, subcubic {C3,K2,3}-free graphs. |
@InProceedings{ACGH09a,
author = {J. Araujo and N. Cohen and F. Giroire and F. Havet},
title = {Good edge-labelling of graphs},
booktitle = {proceedings of the Latin-American Algorithms, Graphs and Optimization Symposium (LAGOS'09)},
OPTcrossref = {},
OPTkey = {},
pages = {275--280},
year = {2009},
OPTeditor = {},
volume = {35},
series = {Electronic Notes in Discrete Mathematics},
address = {Gramado, Brazil},
month = dec,
OPTorganization = {},
publisher = {Springer},
OPTannote = {},
abstract = {A good edge-labelling of a graph G is a labelling of its edges such that for any two distinct vertices u, v, there is at most one (u,v)-path with non-decreasing labels. This notion was introduced in [J-C. Bermond, M. Cosnard, and S. Pérennes. Directed acyclic graphs with unique path property. Technical Report RR-6932, INRIA, May 2009] to solve wavelength assignment problems for specific categories of graphs. In this paper, we aim at characterizing the class of graphs that admit a good edge-labelling. First, we exhibit infinite families of graphs for which no such edge-labelling can be found. We then show that deciding if a graph admits a good edge-labelling is NP-complete. Finally, we give large classes of graphs admitting a good edge-labelling: C3-free outerplanar graphs, planar graphs of girth at least 6, subcubic {C3,K2,3}-free graphs.},
OPTurl = {},
pdf = {ftp://ftp-sop.inria.fr/mascotte/Publications/ACGH09.pdf},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
x-pays={BR},
sorte = "conf-int",
}
-
J. Araujo and C. Linhares Sales.
Grundy number on $P_4$-classes.
In proceedings of the Latin-American Algorithms, Graphs and Optimization Symposium (LAGOS'09),
volume 35 of Electronic Notes in Discrete Mathematics,
Gramado, Brazil,
pages 21--27,
December 2009.
Springer.
[PDF
]
| Abstract: |
|
In this article, we define a new class of graphs, the fat-extended P4-laden graphs, and we show a polynomial time algorithm to determine the Grundy number of the graphs in this class. This result implies that the Grundy number can be found in polynomial time for any graph of the following classes: P4-reducible, extended P4-reducible, P4-sparse, extended P4-sparse, P4-extendible, P4-lite, P4-tidy, P4-laden and extended P4-laden, which are all strictly contained in the fat-extended P4-laden class. |
@InProceedings{ArLi09,
author = {Araujo, J. and Linhares Sales, C.},
title = {Grundy number on {$P_4$}-classes},
booktitle = {proceedings of the Latin-American Algorithms, Graphs and Optimization Symposium (LAGOS'09)},
OPTcrossref = {},
OPTkey = {},
pages = {21--27},
year = {2009},
OPTeditor = {},
volume = {35},
series = {Electronic Notes in Discrete Mathematics},
address = {Gramado, Brazil},
month = dec,
OPTorganization = {},
publisher = {Springer},
OPTannote = {},
abstract = {In this article, we define a new class of graphs, the fat-extended P4-laden graphs, and we show a polynomial time algorithm to determine the Grundy number of the graphs in this class. This result implies that the Grundy number can be found in polynomial time for any graph of the following classes: P4-reducible, extended P4-reducible, P4-sparse, extended P4-sparse, P4-extendible, P4-lite, P4-tidy, P4-laden and extended P4-laden, which are all strictly contained in the fat-extended P4-laden class.},
OPTurl = {},
pdf = {ftp://ftp-sop.inria.fr/mascotte/Publications/ArLi09.pdf},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
x-pays={BR},
sorte = "conf-int",
}
-
J. Araujo,
P. Moura,
and M. Campêlo.
Sobre a complexidade de Coloração Mista.
In Encontro Regional de Pesquisa Operacional do Nordeste,
Fortaleza, Brazil,
pages 1--10,
December 2009.
[PDF
]
| Abstract: |
|
Grafos mistos sËao estruturas matem´aticas que mesclam caracter´ısticas de grafos direcionados e nËao-direcionados. Formalmente, um grafo misto pode ser definido por uma tripla GM = (V; A;E), onde V , A e E representam, respectivamente, um conjunto de v´ertices, de arcos e de arestas. Uma k-colorac¸ Ëao mista de GM = (V; A;E) ´e func¸ Ëao c : V ! f0; : : : ; k ¡ 1g tal que c(u) < c(v), se (u; v) 2 A, e c(u) 6= c(v), se [u; v] 2 E. O problema de Colorac¸ Ëao Mista consiste em determinar o n´umero crom´atico misto de GM, denotado por ÃM(GM), que ´e menor inteiro k tal que GM admite uma k-colorac¸ Ëao mista. Esse problema modela variac¸ Ëoes de problemas de escalonamento que consideram simultaneamente restric¸ Ëoes de precedËencia e de compartilhamento de recursos. Neste trabalho, mostramos que Colorac¸ Ëao Mista ´e NP-dif´ıcil para as classes dos grafos cordais, dos grafos linha de grafos bipartidos e dos grafos linha de grafos periplanares. |
@InProceedings{AMC09,
author = {J. Araujo and P. Moura and M. Camp\^{e}lo},
title = {Sobre a complexidade de Colora\c c\~ao Mista},
booktitle = {Encontro Regional de Pesquisa Operacional do Nordeste},
OPTcrossref = {},
OPTkey = {},
pages = {1--10},
year = {2009},
OPTeditor = {},
series = {},
address = {Fortaleza, Brazil},
month = dec,
OPTorganization = {},
publisher = {},
OPTannote = {},
abstract = {Grafos mistos sËao estruturas matem´aticas que mesclam caracter´ısticas de grafos direcionados e nËao-direcionados. Formalmente, um grafo misto pode ser definido por uma tripla GM = (V; A;E), onde V , A e E representam, respectivamente, um conjunto de v´ertices, de arcos e de arestas. Uma k-colorac¸ Ëao mista de GM = (V; A;E) ´e func¸ Ëao c : V ! f0; : : : ; k ¡ 1g tal que c(u) < c(v), se (u; v) 2 A, e c(u) 6= c(v), se [u; v] 2 E. O problema de Colorac¸ Ëao Mista consiste em determinar o n´umero crom´atico misto de GM, denotado por ÃM(GM), que ´e menor inteiro k tal que GM admite uma k-colorac¸ Ëao mista. Esse problema modela variac¸ Ëoes de problemas de escalonamento que consideram simultaneamente restric¸ Ëoes de precedËencia e de compartilhamento de recursos. Neste trabalho, mostramos que Colorac¸ Ëao Mista ´e NP-dif´ıcil para as classes dos grafos cordais, dos grafos linha de grafos bipartidos e dos grafos linha de grafos periplanares. },
OPTurl = {},
pdf = {ftp://ftp-sop.inria.fr/mascotte/Publications/AMC10.pdf},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={no},
x-pays={BR},
sorte = "conf-nat",
}
-
D. Barman,
J. Chandrashekar,
N. Taft,
M. Faloutsos,
L. Huang,
and F. Giroire.
Impact of IT Monoculture on Behavioral End Host Intrusion Detection.
In ACM SIGCOMM Workshop on Research on Enterprise Networking -- WREN,
Barcelona, Spain,
pages 27--36,
August 2009.
ACM.
[PDF
]
| Abstract: |
|
In this paper, we study the impact of today's IT policies, defined based upon a monoculture approach, on the performance of endhost anomaly detectors. This approach leads to the uniform configuration of Host intrusion detection systems (HIDS) across all hosts in an enterprise networks. We assess the performance impact this policy has from the individual's point of view by analyzing network traces collected from 350 enterprise users. We uncover a great deal of diversity in the user population in terms of the ââ¬Åtailâ⬠behavior, i.e., the component which matters for anomaly detection systems. We demonstrate that the monoculture approach to HIDS configuration results in users that experience wildly different false positive and false negatives rates. We then introduce new policies, based upon leveraging this diversity and show that not only do they dramatically improve performance for the vast majority of users, but they also reduce the number of false positives arriving in centralized IT operation centers, and can reduce attack strength. |
@InProceedings{BJF+09,
author = {D. Barman and J. {C}handrashekar and N. Taft and M. Faloutsos and L. Huang and F. Giroire},
title = {Impact of IT Monoculture on Behavioral End Host Intrusion Detection},
OPTtitle = {Debating IT Monoculture for End Host Intrusion Detection},
booktitle = {ACM SIGCOMM Workshop on Research on Enterprise Networking -- WREN},
OPTcrossref = {},
OPTkey = {},
pages = {27--36},
year = {2009},
editor = {},
OPTvolume = {XXXX},
OPTnumber = {XXXX},
OPTseries = {},
OPTaddress = {},
month = aug,
address = {Barcelona, Spain},
organization = {ACM},
OPTpublisher = {},
OPTannote = {},
abstract = {In this paper, we study the impact of today's IT policies, defined based upon a monoculture approach, on the performance of endhost anomaly detectors. This approach leads to the uniform configuration of Host intrusion detection systems (HIDS) across all hosts in an enterprise networks. We assess the performance impact this policy has from the individual's point of view by analyzing network traces collected from 350 enterprise users. We uncover a great deal of diversity in the user population in terms of the ââ¬Åtailâ⬠behavior, i.e., the component which matters for anomaly detection systems. We demonstrate that the monoculture approach to HIDS configuration results in users that experience wildly different false positive and false negatives rates. We then introduce new policies, based upon leveraging this diversity and show that not only do they dramatically improve performance for the vast majority of users, but they also reduce the number of false positives arriving in centralized IT operation centers, and can reduce attack strength.},
pdf = {http://www-sop.inria.fr/members/Frederic.Giroire/publis/BCF09.pdf},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
x-pays = {US},
sorte = "conf-int",
}
-
J-C. Bermond,
D. Coudert,
J. Moulierac,
S. Perennes,
H. Rivano,
I. Sau,
and F. Solano Donado.
MPLS label stacking on the line network.
In L. Fratta et al., editor,
IFIP Networking,
volume 5550 of Lecture Notes in Computer Science,
Aachen, Germany,
pages 809-820,
May 2009.
Springer.
[WWW
] [PDF
]
| Abstract: |
|
All-Optical Label Switching (AOLS) is a new technology that performs forwarding without any Optical-Electrical-Optical (OEO) conversions. In this report, we study the problem of routing a set of requests in AOLS networks with the aim of minimizing the number of labels required to ensure the forwarding. In order to spare the label space, we consider label stacking, allowing the configuration of tunnels. We study particularly this network design problem when the network is a line. We provide an exact algorithm for the case in which all the requests have a common source and present some approximation algorithms and heuristics when an arbitrary number of sources are distributed over the line. We contrast the performance of our proposed algorithms by simulations. |
@InProceedings{BCM+09b,
author = {J-C. Bermond and D. Coudert and J. Moulierac and S. Perennes and H. Rivano and I. Sau and F. {Solano Donado}},
x-pays = {ES,PL},
title = {{MPLS} label stacking on the line network},
OPTcrossref = {},
OPTkey = {},
booktitle = {IFIP Networking},
pages = {809-820},
year = {2009},
editor = {L. Fratta et al.},
volume = {5550},
OPTnumber = {},
series = {Lecture Notes in Computer Science},
address = {Aachen, Germany},
month = may,
OPTorganization = {},
publisher = {Springer},
OPTnote = {},
OPTannote = {},
url = {http://hal.inria.fr/inria-00354267/},
pdf = {ftp://ftp-sop.inria.fr/mascotte/personnel/Joanna.Moulierac/pdf/bermond09mpls.pdf},
abstract = {All-Optical Label Switching (AOLS) is a new technology that performs forwarding without any Optical-Electrical-Optical (OEO) conversions. In this report, we study the problem of routing a set of requests in AOLS networks with the aim of minimizing the number of labels required to ensure the forwarding. In order to spare the label space, we consider label stacking, allowing the configuration of tunnels. We study particularly this network design problem when the network is a line. We provide an exact algorithm for the case in which all the requests have a common source and present some approximation algorithms and heuristics when an arbitrary number of sources are distributed over the line. We contrast the performance of our proposed algorithms by simulations.},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
sorte = "conf-int",
}
-
J-C. Bermond,
D. Coudert,
J. Moulierac,
S. Perennes,
I. Sau,
and F. Solano Donado.
Designing Hypergraph Layouts to GMPLS Routing Strategies.
In 16th International Colloquium on Structural Information and Communication Complexity (SIROCCO),
volume 5869 of Lecture Notes in Computer Science,
Piran, Slovenia,
pages 57--71,
May 2009.
Springer.
[WWW
] [PDF
]
| Abstract: |
|
All-Optical Label Switching (AOLS) is a new technology that performs packet forwarding without any Optical-Electrical-Optical (OEO) conversions. In this paper, we study the problem of routing a set of requests in AOLS networks using GMPLS technology, with the aim of minimizing the number of labels required to ensure the forwarding. We first formalize the problem by associating to each routing strategy a logical hypergraph whose hyperedges are dipaths of the physical graph, called \emph{tunnels} in GMPLS terminology. Such a hypergraph is called a \emph{hypergraph layout}, to which we assign a cost function given by its physical length plus the total number of hops traveled by the traffic. Minimizing the cost of the design of an AOLS network can then be expressed as finding a minimum cost hypergraph layout. We prove hardness results for the problem, namely $C \log n$ hardness for directed networks and non-existence of \textsc{PTAS} for undirected networks, where $C $ is a a positive constant and $n$ is the number of nodes of the network. These hardness results hold even is the traffic instance is a partial broadcast. On the other hand, we provide an $\mathcal{O}(\log n)$-approximation algorithm to the problem for a general network. Finally, we focus on the case where the physical network is a path, providing a polynomial-time dynamic programming algorithm for a bounded number of sources, thus extending the algorithm of~\cite{BCM+09b} for a single source. |
@InProceedings{BCM+09d,
author = {J-C. Bermond and D. Coudert and J. Moulierac and S. Perennes and I. Sau and F. {Solano Donado}},
x-pays = {ES,PL},
title = {Designing Hypergraph Layouts to {GMPLS} Routing Strategies},
OPTcrossref = {},
OPTkey = {},
booktitle = {16th International Colloquium on Structural Information and Communication Complexity (SIROCCO)},
pages = {57--71},
year = {2009},
OPTeditor = {},
volume = {5869},
OPTpages = {YYYY},
OPTnumber = {},
series = {Lecture Notes in Computer Science},
address = {Piran, Slovenia},
month = may,
OPTorganization = {},
publisher = {Springer},
OPTnote = {},
OPTannote = {},
url = {http://hal.inria.fr/inria-00428685/fr/},
pdf = {ftp://ftp-sop.inria.fr/mascotte/personnel/Joanna.Moulierac/pdf/bermond09designing.pdf},
abstract = { All-Optical Label Switching (AOLS) is a new technology that performs packet forwarding without any Optical-Electrical-Optical (OEO) conversions. In this paper, we study the problem of routing a set of requests in AOLS networks using GMPLS technology, with the aim of minimizing the number of labels required to ensure the forwarding. We first formalize the problem by associating to each routing strategy a logical hypergraph whose hyperedges are dipaths of the physical graph, called \emph{tunnels} in GMPLS terminology. Such a hypergraph is called a \emph{hypergraph layout}, to which we assign a cost function given by its physical length plus the total number of hops traveled by the traffic. Minimizing the cost of the design of an AOLS network can then be expressed as finding a minimum cost hypergraph layout. We prove hardness results for the problem, namely $C \log n$ hardness for directed networks and non-existence of \textsc{PTAS} for undirected networks, where $C $ is a a positive constant and $n$ is the number of nodes of the network. These hardness results hold even is the traffic instance is a partial broadcast. On the other hand, we provide an $\mathcal{O}(\log n)$-approximation algorithm to the problem for a general network. Finally, we focus on the case where the physical network is a path, providing a polynomial-time dynamic programming algorithm for a bounded number of sources, thus extending the algorithm of~\cite{BCM+09b} for a single source. },
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
sorte = "conf-int",
}
-
J-C. Bermond,
D. Mazauric,
and P. Nain.
Algorithmes distribués d'ordonnancement dans les réseaux sans-fil.
In 10èmes Journées Doctorales en Informatique et Réseaux (JDIR),
Belfort, France,
February 2009.
[PDF
]
| Abstract: |
|
Nous consid\'erons dans cet article le probl\`eme d'ordonnancement distribu\'e dans les r\'eseaux sans-fil. En raison des interf\'erences dans ce type de r\'eseau, ne peuvent \^etre activ\'es simultan\'ement que des liens n'interf\'erant pas entre eux. Par exemple dans un mod\`ele primaire, on ne peut activer que des liens deux \`a deux non adjacents. Nous nous pla\c cons dans un contexte d'arriv\'ee al\'eatoire de messages et l'objectif est d'assurer un bon comportement du r\'eseau en particulier d'assurer la stabilit\'e des files d'attente, en limitant le nombre moyen de messages en attente. Des algorithmes centralis\'es permettant de d\'ecider quels liens sont activ\'es \`a chaque \'etape existent mais ils supposent une connaissance globale du r\'eseau et sont peu adapt\'es aux applications. Il est donc n\'ecessaire de concevoir des algorithmes distribu\'es qui utilisent une connaissance tr\`es locale du r\'eseau. Nous proposons dans cet article deux algorithmes distribu\'es, valides quelque soit le mod\`ele d'interf\'erence binaire et avec une phase de contr\^ole de dur\'ee constante, am\'eliorant les algorithmes existants v\'erifiant uniquement l'un ou l'autre de ces deux crit\`eres. |
@InProceedings{BMN09,
author = {J-C. Bermond and D. Mazauric and P. Nain},
title = {Algorithmes distribu\'es d'ordonnancement dans les r\'eseaux sans-fil},
booktitle = {10\`emes Journ\'ees Doctorales en Informatique et R\'eseaux (JDIR)},
OPTcrossref = {},
OPTkey = {},
pages = {},
year = {2009},
editor = {},
volume = {},
OPTnumber = {},
series = {},
address = {Belfort, France},
month = feb,
OPTorganization = {},
publisher = {},
OPTannote = {},
pdf = {ftp://ftp-sop.inria.fr/mascotte/Publications/BMN09.pdf},
abstract = {Nous consid\'erons dans cet article le probl\`eme d'ordonnancement distribu\'e dans les r\'eseaux sans-fil. En raison des interf\'erences dans ce type de r\'eseau, ne peuvent \^etre activ\'es simultan\'ement que des liens n'interf\'erant pas entre eux. Par exemple dans un mod\`ele primaire, on ne peut activer que des liens deux \`a deux non adjacents. Nous nous pla\c cons dans un contexte d'arriv\'ee al\'eatoire de messages et l'objectif est d'assurer un bon comportement du r\'eseau en particulier d'assurer la stabilit\'e des files d'attente, en limitant le nombre moyen de messages en attente. Des algorithmes centralis\'es permettant de d\'ecider quels liens sont activ\'es \`a chaque \'etape existent mais ils supposent une connaissance globale du r\'eseau et sont peu adapt\'es aux applications. Il est donc n\'ecessaire de concevoir des algorithmes distribu\'es qui utilisent une connaissance tr\`es locale du r\'eseau. Nous proposons dans cet article deux algorithmes distribu\'es, valides quelque soit le mod\`ele d'interf\'erence binaire et avec une phase de contr\^ole de dur\'ee constante, am\'eliorant les algorithmes existants v\'erifiant uniquement l'un ou l'autre de ces deux crit\`eres.},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={no},
sorte = "conf-nat",
}
-
J-C. Bermond,
N. Nisse,
P. Reyes,
and H. Rivano.
Fast Data Gathering in Radio Grid Networks.
In 11èmes Rencontres Francophones sur les Aspects Algorithmiques de Télécommunications (AlgoTel'09),
pages 4p,
June 2009.
[WWW
] [PDF
]
| Abstract: |
|
Nous présentons des algorithmes efficaces pour la collecte d'informations par une station de base au sein d'un réseau sans-fil multi sauts en présence d'interférences. Nous nous focalisons sur les réseaux en grille car ils sont un bon modèle des réseaux d'accès comme des réseaux aléatoires de capteurs. Le temps est divisé en étapes élémentaires. Au cours d'une étape, un nÅud peut transmettre au plus un message à l'un de ces voisins. Chaque appareil est équipé d'un interface half duplex et ne peut donc émettre et recevoir à la même étape. Ainsi, au cours d'une étape, l'ensemble des transmissions valides induit un couplage de la grille. Le problème consiste à minimiser le nombre d'étapes nécessaires à la collecte de tous les messages par la station de base. Le meilleur algorithme connu était une 3/2 approximation. Nous donnons un algorithme très simple qui approche l'optimum à 2 près, puis nous présentons un algorithme plus évolué qui est une +1 approximation. Nos résultats sont valides lorsque les appareils ne disposent d'aucune mémoire tampon et doivent retransmettre un message à l'étape suivant sa réception. |
@InProceedings{BNRR09,
author = {J-C. Bermond and N. Nisse and P. Reyes and H. Rivano},
title = {Fast Data Gathering in Radio Grid Networks},
booktitle = {11\`emes Rencontres Francophones sur les Aspects Algorithmiques de T\'el\'ecommunications (AlgoTel'09)},
pages = {4p},
year = {2009},
month = jun,
url = {http://www.lif.univ-mrs.fr/algotel09},
pdf = {ftp://ftp-sop.inria.fr/mascotte/Publications/BNRR09.pdf},
abstract = {Nous présentons des algorithmes efficaces pour la collecte d'informations par une station de base au sein d'un réseau sans-fil multi sauts en présence d'interférences. Nous nous focalisons sur les réseaux en grille car ils sont un bon modèle des réseaux d'accès comme des réseaux aléatoires de capteurs. Le temps est divisé en étapes élémentaires. Au cours d'une étape, un nÅud peut transmettre au plus un message à l'un de ces voisins. Chaque appareil est équipé d'un interface half duplex et ne peut donc émettre et recevoir à la même étape. Ainsi, au cours d'une étape, l'ensemble des transmissions valides induit un couplage de la grille. Le problème consiste à minimiser le nombre d'étapes nécessaires à la collecte de tous les messages par la station de base. Le meilleur algorithme connu était une 3/2 approximation. Nous donnons un algorithme très simple qui approche l'optimum à 2 près, puis nous présentons un algorithme plus évolué qui est une +1 approximation. Nos résultats sont valides lorsque les appareils ne disposent d'aucune mémoire tampon et doivent retransmettre un message à l'étape suivant sa réception.},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={no},
sorte = "conf-nat",
}
-
J-C. Bermond,
N. Nisse,
P. Reyes,
and H. Rivano.
Minimum delay Data Gathering in Radio Networks.
In Proceedings of the 8th international conference on Ad Hoc Networks and Wireless (AdHoc-Now),
volume 5793 of Lecture Notes in Computer Science,
pages 69-82,
2009.
Springer.
[WWW
] [PDF
]
| Abstract: |
|
The aim of this paper is to design efficient gathering algorithms (data collection) in a Base Station of a wireless multi hop grid network when interferences constraints are present. We suppose the time is slotted and that during one time slot (step) each node can transmit to one of its neighbours at most one data item. Each device is equipped with a half duplex interface; so a node cannot both receive and transmit simultaneously. During a step only non interfering transmissions can be done. In other words, the non interfering calls done during a step will form a matching. The aim is to minimize the number of steps needed to send to the base station a set of messages generated by the nodes, this completion time is also denoted makespan of the call scheduling. The best known algorithm for open-grids was a multiplicative 1.5-approximation algorithm [Revah, Segal 07]. In such topologies, we give a very simple +2 approximation algorithm and then a more involved +1 approximation algorithm. Moreover, our algorithms work when no buffering is allowed in intermediary nodes, i.e., when a node receives a message at some step, it must transmit it during the next step. |
@inProceedings{BNRR09c,
author = {J-C. Bermond and N. Nisse and P. Reyes and H. Rivano},
title = {Minimum delay Data Gathering in Radio Networks},
booktitle = {Proceedings of the 8th international conference on Ad Hoc Networks and Wireless (AdHoc-Now)},
year = {2009},
pages = {69-82},
volume = {5793},
series = {Lecture Notes in Computer Science},
publisher = {Springer},
url = {http://hal.inria.fr/inria-00363908/fr/},
pdf = {http://www-sop.inria.fr/members/Nicolas.Nisse/publications/adHocNow09.pdf},
abstract = {The aim of this paper is to design efficient gathering algorithms (data collection) in a Base Station of a wireless multi hop grid network when interferences constraints are present. We suppose the time is slotted and that during one time slot (step) each node can transmit to one of its neighbours at most one data item. Each device is equipped with a half duplex interface; so a node cannot both receive and transmit simultaneously. During a step only non interfering transmissions can be done. In other words, the non interfering calls done during a step will form a matching. The aim is to minimize the number of steps needed to send to the base station a set of messages generated by the nodes, this completion time is also denoted makespan of the call scheduling. The best known algorithm for open-grids was a multiplicative 1.5-approximation algorithm [Revah, Segal 07]. In such topologies, we give a very simple +2 approximation algorithm and then a more involved +1 approximation algorithm. Moreover, our algorithms work when no buffering is allowed in intermediary nodes, i.e., when a node receives a message at some step, it must transmit it during the next step.},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
sorte = "conf-int",
}
-
V. Bilò,
M. Flammini,
G. Monaco,
and L. Moscardelli.
On the performances of Nash Equilibria in Isolation Games.
In Proceedings of the 15th International Computing and Combinatorics Conference (COCOON 2009),
volume 5609 of Lecture Notes in Computer Science,
Niagara Falls, New York, U.S.A.,
pages 17-26,
July 2009.
Springer.
[WWW
] [PDF
]
| Abstract: |
|
We study the performances of Nash equilibria in isolation games, a class of competitive location games recently introduced by Zhao et all. For all the cases in which the existence of Nash equilibria has been shown, we give tight or asymptotically tight bounds on the prices of anarchy and stability under the two classical social functions mostly investigated in the scienti¯c literature, namely, the minimum utility per player and the sum of the players' utilities. Moreover, we prove that the convergence to Nash equilibria is not guaranteed in some of the not yet analyzed cases. |
@inproceedings{BFM+09,
sorte = "conf-int",
author = {V. Bil{\`o} and M. Flammini and G. Monaco and L. Moscardelli},
title = {On the performances of Nash Equilibria in Isolation Games},
booktitle= {Proceedings of the 15th International Computing and Combinatorics Conference (COCOON 2009)},
address= {Niagara Falls, New York, U.S.A.},
year= {2009},
month = jul,
volume = {5609},
pages = {17-26},
publisher = {Springer},
series = {Lecture Notes in Computer Science},
OPTnote = {},
OPTannote = {},
url = {http://www.springerlink.com/content/t02154u9h640t1xx/},
PDF={http://www.springerlink.com/content/t02154u9h640t1xx/},
abstract = {We study the performances of Nash equilibria in isolation games, a class of competitive location games recently introduced by Zhao et all. For all the cases in which the existence of Nash equilibria has been shown, we give tight or asymptotically tight bounds on the prices of anarchy and stability under the two classical social functions mostly investigated in the scienti¯c literature, namely, the minimum utility per player and the sum of the players' utilities. Moreover, we prove that the convergence to Nash equilibria is not guaranteed in some of the not yet analyzed cases.},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={no},
}
-
A. Casteigts,
S. Chaumette,
and A. Ferreira.
Characterizing Topological Assumptions of Distributed Algorithms in Dynamic Networks.
In Proc. of 16th Intl. Conference on Structural Information and Communication Complexity (SIROCCO'09),
volume 5869 of Lecture Notes in Computer Science,
Piran, Slovenia,
pages 126-140,
May 2009.
Springer-Verlag.
[PDF
]
| Abstract: |
|
Besides the complexity in time or in number of messages, a common approach for analyzing distributed algorithms is to look at their assumptions on the underlying network. This paper focuses on the study of such assumptions in dynamic networks, where the connectivity is expected to change, predictably or not, during the execution. Our main contribution is a theoretical framework dedicated to such analysis. By combining several existing components (local computations, graph relabellings, and evolving graphs), this framework allows to express detailed properties on the network dynamics and to prove that a given property is necessary, or sufficient, for the success of an algorithm. Consequences of this work include (i)~the possibility to compare distributed algorithms on the basis of their topological requirements, (ii)~the elaboration of a formal classification of dynamic networks with respect to these properties, and (iii)~the possibility to check automatically whether a network trace belongs to one of the classes, and consequently to know which algorithm should run on it. |
@InProceedings{CCF09,
author = {A. Casteigts and S. Chaumette and A. Ferreira},
title = {Characterizing Topological Assumptions of Distributed Algorithms in Dynamic Networks},
booktitle = {Proc. of 16th Intl. Conference on Structural Information and Communication Complexity (SIROCCO'09)},
year = 2009,
month = may,
address = {Piran, Slovenia},
series = {Lecture Notes in Computer Science},
volume = {5869},
pages = {126-140},
pdf = {ftp://ftp-sop.inria.fr/mascotte/Publications/CCF09.pdf},
publisher = {Springer-Verlag},
abstract = {Besides the complexity in time or in number of messages, a common approach for analyzing distributed algorithms is to look at their assumptions on the underlying network. This paper focuses on the study of such assumptions in dynamic networks, where the connectivity is expected to change, predictably or not, during the execution. Our main contribution is a theoretical framework dedicated to such analysis. By combining several existing components (local computations, graph relabellings, and evolving graphs), this framework allows to express detailed properties on the network dynamics and to prove that a given property is necessary, or sufficient, for the success of an algorithm. Consequences of this work include (i)~the possibility to compare distributed algorithms on the basis of their topological requirements, (ii)~the elaboration of a formal classification of dynamic networks with respect to these properties, and (iii)~the possibility to check automatically whether a network trace belongs to one of the classes, and consequently to know which algorithm should run on it.},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
sorte = "conf-int",
}
-
N. Cohen,
F. V. Fomin,
G. Gutin,
E. J. Kim,
S. Saurabh,
and A. Yeo.
Algorithm for Finding it -Vertex Out-trees and Its Application to it -Internal Out-branching Problem.
In 15th Annual International Conference on Computing and Combinatorics (COCOON),
volume 5609 of Lecture Notes in Computer Science,
pages 37-46,
2009.
[WWW
] [PDF
]
| Abstract: |
|
An out-tree T is an oriented tree with exactly one vertex of in-degree zero and a vertex x of T is called internal if its out-degree is positive. We design randomized and deterministic algorithms for deciding whether an input digraph contains a subgraph isomorphic to a given out-tree with k vertices. Both algorithms run in Oâ(5.704^k) time. We apply the deterministic algorithm to obtain an algorithm of runtime Oâ(c^k), where c is a constant, for deciding whether an input digraph contains a spanning out-tree with at least k internal vertices. This answers in affirmative a question of Gutin, Razgon and Kim (Proc. AAIM'08). |
@inproceedings{CF+09,
author = {N. Cohen and F. V. Fomin and G. Gutin and E. J. Kim and S. {S}aurabh and A. Yeo},
title = {Algorithm for Finding {\it }-Vertex Out-trees and Its Application to {\it }-Internal Out-branching Problem},
booktitle = {15th Annual International Conference on Computing and Combinatorics (COCOON)},
year = {2009},
pages = {37-46},
volume = {5609},
series = {Lecture Notes in Computer Science},
url = {http://dx.doi.org/10.1007/978-3-642-02882-3_5},
abstract = {An out-tree T is an oriented tree with exactly one vertex of in-degree zero and a vertex x of T is called internal if its out-degree is positive. We design randomized and deterministic algorithms for deciding whether an input digraph contains a subgraph isomorphic to a given out-tree with k vertices. Both algorithms run in Oâ(5.704^k) time. We apply the deterministic algorithm to obtain an algorithm of runtime Oâ(c^k), where c is a constant, for deciding whether an input digraph contains a spanning out-tree with at least k internal vertices. This answers in affirmative a question of Gutin, Razgon and Kim (Proc. AAIM'08).},
pdf = {ftp://ftp-sop.inria.fr/mascotte/Publications/CF+09.pdf},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
x-pays = {NO, UK},
sorte = "conf-int",
}
-
N. Cohen,
F. Havet,
and T. Müller.
Acyclic edge-colouring of planar graphs.
In European Conference on Combinatorics, Graph Theory and Applications (Eurocomb 2009),
volume 34 of Electronic Notes on Discrete Mathematics,
Bordeaux, France,
pages 417-421,
September 2009.
[PDF
]
| Abstract: |
|
A proper edge-colouring with the property that every cycle contains edges of at least three distinct colours is called an {\it acyclic edge-colouring}. The {\it acyclic chromatic index} of a graph $G$, denoted $\chi'_a(G)$ is the minimum $k$ such that $G$ admits an {\it acyclic edge-colouring} with $k$ colours. We conjecture that if $G$ is planar and $\Delta(G)$ is large enough then $\chi'_a(G)=\Delta(G)$. We settle this conjecture for planar graphs with girth at least $5$ and outerplanar graphs. We also show that if $G$ is planar then $\chi'_a(G)\leq \Delta(G) + 25$. |
@InProceedings{CHM09b,
AUTHOR={N. Cohen and F. Havet and T. M{\"u}ller},
TITLE="Acyclic edge-colouring of planar graphs",
booktitle ="European Conference on Combinatorics, Graph Theory and Applications (Eurocomb 2009)",
series = "Electronic Notes on Discrete Mathematics",
PAGES = "417-421",
VOLUME = "34",
year = "2009",
address = "Bordeaux, France",
month = sep,
abstract={A proper edge-colouring with the property that every cycle contains edges of at least three distinct colours is called an {\it acyclic edge-colouring}. The {\it acyclic chromatic index} of a graph $G$, denoted $\chi'_a(G)$ is the minimum $k$ such that $G$ admits an {\it acyclic edge-colouring} with $k$ colours. We conjecture that if $G$ is planar and $\Delta(G)$ is large enough then $\chi'_a(G)=\Delta(G)$. We settle this conjecture for planar graphs with girth at least $5$ and outerplanar graphs. We also show that if $G$ is planar then $\chi'_a(G)\leq \Delta(G) + 25$.},
pdf = {ftp://ftp-sop.inria.fr/mascotte/Publications/CHM09b.pdf},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
x-pays = {IL},
sorte = "conf-int",
}
-
D. Coudert,
F. Giroire,
and I. Sau.
Edge-Simple Circuits Through 10 Ordered Vertices in Square Grids.
In J. Kratochvìl and M. Miller, editors,
20th International Workshop on Combinatorial Algorithms -- IWOCA,
volume 5874 of Lecture Notes in Computer Science,
Hradec nad Moravicì, Czech Republic,
pages 134-145,
June 2009.
Springer.
[WWW
] [PDF
]
| Abstract: |
|
A \emph{circuit} in a simple undirected graph $G=(V,E)$ is a sequence of vertices $\{v_1,v_2,\ldots,v_{k+1}\}$ such that $v_1=v_{k+1}$ and $\{v_i,v_{i+i}\} \in E$ for $i=1,\ldots,k$. A circuit $C$ is said to be \emph{edge-simple} if no edge of $G$ is used twice in $C$. In this article we study the following problem: which is the largest integer $k$ such that, given any subset of $k$ ordered vertices of an infinite square grid, there exists an edge-simple circuit visiting the $k$ vertices in the prescribed order? We prove that $k=10$. To this end, we first provide a counterexample implying that $k<11$. To show that $k\geq 10$, we introduce a methodology, based on the notion of core graph, to reduce drastically the number of possible vertex configurations, and then we test each one of the resulting configurations with an \textsc{ILP} solver. |
@InProceedings{CGS09b,
author = {D. Coudert and F. Giroire and I. Sau},
title = {Edge-Simple Circuits Through 10 Ordered Vertices in Square Grids},
booktitle = {20th International Workshop on Combinatorial Algorithms -- IWOCA},
OPTcrossref = {},
OPTkey = {},
pages = {134-145},
year = {2009},
editor = {J. Kratochv{\'\i}l and M. Miller},
volume = {5874},
OPTnumber = {XXXX},
series = {Lecture Notes in Computer Science},
address = {Hradec nad Moravic{\'\i}, Czech Republic},
month = jun,
OPTorganization = {},
publisher = {Springer},
OPTnote = {to appear},
OPTannote = {},
abstract = { A \emph{circuit} in a simple undirected graph $G=(V,E)$ is a sequence of vertices $\{v_1,v_2,\ldots,v_{k+1}\}$ such that $v_1=v_{k+1}$ and $\{v_i,v_{i+i}\} \in E$ for $i=1,\ldots,k$. A circuit $C$ is said to be \emph{edge-simple} if no edge of $G$ is used twice in $C$. In this article we study the following problem: which is the largest integer $k$ such that, given any subset of $k$ ordered vertices of an infinite square grid, there exists an edge-simple circuit visiting the $k$ vertices in the prescribed order? We prove that $k=10$. To this end, we first provide a counterexample implying that $k<11$. To show that $k\geq 10$, we introduce a methodology, based on the notion of core graph, to reduce drastically the number of possible vertex configurations, and then we test each one of the resulting configurations with an \textsc{ILP} solver.},
url = {http://hal.inria.fr/inria-00429146},
pdf = {http://hal.inria.fr/docs/00/42/91/46/PDF/CGS09_IWOCA_nostyle.pdf},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
sorte = "conf-int",
}
-
D. Coudert,
F. Huc,
D. Mazauric,
N. Nisse,
and J-S. Sereni.
Reconfiguration of the Routing in WDM Networks with Two Classes of Services.
In 13th Conference on Optical Network Design and Modeling (ONDM),
Braunschweig, Germany,
pages 6p,
February 2009.
IEEE.
[WWW
]
| Abstract: |
|
In WDM backbone networks, the traffic pattern evolves constantly due to the nature of the demand itself or because of equipment failures leading to reroute affected connections. In this context, requests are routed greedily using available resources without changing the routing of pre-established connections. However, such a policy leads to a poor usage of resources and so higher blocking probability: new connection requests might be rejected while network resources are sufficient to serve all the traffic. Therefore, it is important to regularly reconfigure the network by rerouting established connections in order to optimize the usage of network resources. In this paper, we consider the network reconfiguration problem that consists in switching existing connections one after the other from the current routing to a new pre-computed routing. Due to cyclic dependencies between connections, some requests may have to be temporarily interrupted during this process. Clearly, the number of requests simultaneously interrupted has to be minimized. Furthermore, it might be impossible for the network operator to interrupt some connections because of the contract signed with the corresponding clients. In this setting, the network reconfiguration problem consists in going from a routing to another one given that some priority connections cannot be interrupted. The network reconfiguration problem without priority connections has previously been modeled as a cops-and-robber game in [CPPS05,CoSe07]. Here, we first extend this model to handle priority connections. Then we identify cases where no solution exists. Using a simple transformation, we prove that the reconfiguration problem with priority connections can be reduced to the problem without this constraint. Finally, we propose a new heuristic algorithm that improves upon previous proposals. |
@InProceedings{CHM+09,
author = {D. Coudert and F. Huc and D. Mazauric and N. Nisse and J-S. Sereni},
title = {Reconfiguration of the Routing in {WDM} Networks with Two Classes of Services},
booktitle = {13th Conference on Optical Network Design and Modeling (ONDM)},
OPTcrossref = {},
OPTkey = {},
pages = {6p},
year = {2009},
OPTeditor = {},
OPTvolume = {},
OPTnumber = {},
OPTseries = {},
address = {Braunschweig, Germany},
month = feb,
OPTorganization = {},
publisher = {IEEE},
OPTnote = {},
OPTannote = {},
url = {http://hal.inria.fr/inria-00331807},
abstract = { In WDM backbone networks, the traffic pattern evolves constantly due to the nature of the demand itself or because of equipment failures leading to reroute affected connections. In this context, requests are routed greedily using available resources without changing the routing of pre-established connections. However, such a policy leads to a poor usage of resources and so higher blocking probability: new connection requests might be rejected while network resources are sufficient to serve all the traffic. Therefore, it is important to regularly reconfigure the network by rerouting established connections in order to optimize the usage of network resources. In this paper, we consider the network reconfiguration problem that consists in switching existing connections one after the other from the current routing to a new pre-computed routing. Due to cyclic dependencies between connections, some requests may have to be temporarily interrupted during this process. Clearly, the number of requests simultaneously interrupted has to be minimized. Furthermore, it might be impossible for the network operator to interrupt some connections because of the contract signed with the corresponding clients. In this setting, the network reconfiguration problem consists in going from a routing to another one given that some priority connections cannot be interrupted. The network reconfiguration problem without priority connections has previously been modeled as a cops-and-robber game in [CPPS05,CoSe07]. Here, we first extend this model to handle priority connections. Then we identify cases where no solution exists. Using a simple transformation, we prove that the reconfiguration problem with priority connections can be reduced to the problem without this constraint. Finally, we propose a new heuristic algorithm that improves upon previous proposals. },
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
sorte = "conf-int",
}
-
D. Coudert,
F. Huc,
D. Mazauric,
N. Nisse,
and J-S. Sereni.
Reconfiguration dans les réseaux optiques.
In A. Chaintreau and C. Magnien, editors,
11ème Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications (AlgoTel'09),
Carry le Rouet,
pages 4p,
June 2009.
[WWW
] [PDF
]
| Abstract: |
|
L'\'evolution permanente du trafic, les op\'erations de maintenance et l'existence de pannes dans les r\'eseaux WDM, obligent \`a rerouter r\'eguli\`erement des connexions. Les nouvelles demandes de connexions sont rout\'ees en utilisant les ressources disponibles et, si possible, sans modifier le routage des connexions existantes. Ceci peut engendrer une mauvaise utilisation des ressources disponibles. Il est donc pr\'ef\'erable de reconfigurer r\'eguli\`erement l'ensemble des routes des diff\'erentes connexions. Un objectif particuli\`erement important est alors de minimiser le nombre de requ\^etes simultan\'ement interrompues lors de la reconfiguration. Nous proposons une heuristique pour r\'esoudre ce probl\`eme dans les r\'eseaux WDM. Les simulations montrent que cette heuristique r\'ealise de meilleures performances que celle propos\'ee par Jose et Somani (2003). Nous proposons \'egalement un mod\`ele permettant de prendre en compte diff\'erentes classes de clients, avec notamment la contrainte que des requ\^etes, dites prioritaires, ne peuvent pas \^etre interrompues. Une simple transformation permet de r\'eduire le probl\`eme avec requ\^etes prioritaires au probl\`eme initial. De ce fait, notre heuristique s'applique \'egalement au cas autorisant des requ\^etes prioritaires. |
@InProceedings{CHM+09b,
author = {D. Coudert and F. Huc and D. Mazauric and N. Nisse and J-S. Sereni},
title = {Reconfiguration dans les r\'eseaux optiques},
booktitle = {11\`eme Rencontres Francophones sur les Aspects Algorithmiques des T\'el\'ecommunications (AlgoTel'09)},
OPTcrossref = {},
OPTkey = {},
pages = {4p},
year = {2009},
editor = {A. Chaintreau and C. Magnien},
OPTvolume = {},
OPTnumber = {},
OPTseries = {},
address = {Carry le Rouet},
month = jun,
OPTorganization = {},
OPTpublisher = {},
OPTannote = {},
url = {http://hal.inria.fr/inria-00331807},
pdf = {http://hal.inria.fr/docs/00/38/32/06/PDF/CHMNS09b.pdf},
abstract = { L'\'evolution permanente du trafic, les op\'erations de maintenance et l'existence de pannes dans les r\'eseaux WDM, obligent \`a rerouter r\'eguli\`erement des connexions. Les nouvelles demandes de connexions sont rout\'ees en utilisant les ressources disponibles et, si possible, sans modifier le routage des connexions existantes. Ceci peut engendrer une mauvaise utilisation des ressources disponibles. Il est donc pr\'ef\'erable de reconfigurer r\'eguli\`erement l'ensemble des routes des diff\'erentes connexions. Un objectif particuli\`erement important est alors de minimiser le nombre de requ\^etes simultan\'ement interrompues lors de la reconfiguration. Nous proposons une heuristique pour r\'esoudre ce probl\`eme dans les r\'eseaux WDM. Les simulations montrent que cette heuristique r\'ealise de meilleures performances que celle propos\'ee par Jose et Somani (2003). Nous proposons \'egalement un mod\`ele permettant de prendre en compte diff\'erentes classes de clients, avec notamment la contrainte que des requ\^etes, dites prioritaires, ne peuvent pas \^etre interrompues. Une simple transformation permet de r\'eduire le probl\`eme avec requ\^etes prioritaires au probl\`eme initial. De ce fait, notre heuristique s'applique \'egalement au cas autorisant des requ\^etes prioritaires.},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={no},
sorte = "conf-nat",
}
-
D. Coudert,
D. Mazauric,
and N. Nisse.
On Rerouting Connection Requests in Networks with Shared Bandwidth.
In DIMAP workshop on Algorithmic Graph Theory (AGT09),
volume 32 of Electronic Notes in Discrete Mathematics,
Warwick, UK,
pages 109-116,
March 2009.
Elsevier.
[WWW
] [PDF
]
| Abstract: |
|
In this paper, we address the problem of scheduling the switching of a set of connection requests one after the other from current routing to another pre-determined routing. We propose a model that handles requests using only a constant fraction of the bandwidth of a link, thus generalizing the model proposed in [CoSe07,JoSo03] for WDM networks. Our main result is the proof that the problem of deciding whether it exists a scheduling of the rerouting of connection requests without traffic interruption is NP-complete even if requests use the third of the bandwidth of a link. Note that the problem is polynomial when the bandwidth of a link cannot be shared [CoSe07]. |
@InProceedings{CMN09b,
author = {D. Coudert and D. Mazauric and N. Nisse},
title = {On Rerouting Connection Requests in Networks with Shared Bandwidth},
OPTcrossref = {},
OPTkey = {},
booktitle = {DIMAP workshop on Algorithmic Graph Theory (AGT09)},
pages = {109-116},
year = {2009},
OPTeditor = {},
volume = {32},
OPTnumber = {},
series = {Electronic Notes in Discrete Mathematics},
address = {Warwick, UK},
month = mar,
OPTorganization = {},
publisher = {Elsevier},
OPTannote = {},
url = {http://dx.doi.org/10.1016/j.endm.2009.02.015},
abstract = { In this paper, we address the problem of scheduling the switching of a set of connection requests one after the other from current routing to another pre-determined routing. We propose a model that handles requests using only a constant fraction of the bandwidth of a link, thus generalizing the model proposed in [CoSe07,JoSo03] for WDM networks. Our main result is the proof that the problem of deciding whether it exists a scheduling of the rerouting of connection requests without traffic interruption is NP-complete even if requests use the third of the bandwidth of a link. Note that the problem is polynomial when the bandwidth of a link cannot be shared [CoSe07]. },
pdf = {http://hal.inria.fr/docs/00/35/00/25/PDF/RR-6790.pdf},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
sorte = "conf-int",
}
-
D. Coudert,
N. Nepomuceno,
and H. Rivano.
Joint Optimization of Routing and Radio Configuration in Fixed Wireless Networks.
In A. Chaintreau and C. Magnien, editors,
11ème Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications (AlgoTel'09),
Carry le Rouet,
pages 4p,
June 2009.
[WWW
] [PDF
]
| Abstract: |
|
Nous étudions la minimisation de la consommation d'énergie des réseaux sans-fil fixes à transmission par liens micro-ondes, par l'optimisation jointe du routage des flux de données et la sélection de la configuration des liens. Nous présentons une formulation mathématique exacte basée sur un multiflot entier de coût minimum avec des fonctions de coût en escalier, rendant le problème très difficile à résoudre. Nous proposons ensuite une fonction linéaire par morceaux convexe, obtenue par interpolation linéaire des points de configuration efficaces en énergie, qui fournit une bonne approximation de la consommation d'énergie sur les liens, et présentons une relaxation qui exploite la convexité des fonctions de coût. Ceci rapporte des limites inférieures sur la consommation d'énergie, et finalement un algorithme heuristique basé sur l'optimum fractionnaire est utilisé pour produire des solutions réalisables. Les résultats attestent du potentiel de notre nouvelle approche. |
@InProceedings{CNR09b,
author = {D. Coudert and N. Nepomuceno and H. Rivano},
title = {Joint Optimization of Routing and Radio Configuration in Fixed Wireless Networks},
booktitle = {11\`eme Rencontres Francophones sur les Aspects Algorithmiques des T\'el\'ecommunications (AlgoTel'09)},
pages = {4p},
year = {2009},
editor = {A. Chaintreau and C. Magnien},
address = {Carry le Rouet},
month = jun,
abstract = {Nous étudions la minimisation de la consommation d'énergie des réseaux sans-fil fixes à transmission par liens micro-ondes, par l'optimisation jointe du routage des flux de données et la sélection de la configuration des liens. Nous présentons une formulation mathématique exacte basée sur un multiflot entier de coût minimum avec des fonctions de coût en escalier, rendant le problème très difficile à résoudre. Nous proposons ensuite une fonction linéaire par morceaux convexe, obtenue par interpolation linéaire des points de configuration efficaces en énergie, qui fournit une bonne approximation de la consommation d'énergie sur les liens, et présentons une relaxation qui exploite la convexité des fonctions de coût. Ceci rapporte des limites inférieures sur la consommation d'énergie, et finalement un algorithme heuristique basé sur l'optimum fractionnaire est utilisé pour produire des solutions réalisables. Les résultats attestent du potentiel de notre nouvelle approche.},
url = {http://hal.inria.fr/inria-00384968/fr/},
pdf = {http://hal.inria.fr/docs/00/38/49/68/PDF/AlgoTel.pdf},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={no},
x-pays = {BR},
sorte = "conf-nat",
}
-
D. Coudert,
N. Nepomuceno,
and H. Rivano.
Minimizing Energy Consumption by Power-Efficient Radio Configuration in Fixed Broadband Wireless Networks.
In First IEEE WoWMoM Workshop on Hot Topics in Mesh Networking (HotMESH),
Kos, Greece,
pages 6p,
June 2009.
IEEE.
[WWW
] [PDF
]
| Abstract: |
|
"In this paper, we investigate on minimizing the energy consumption of a fixed broadband wireless network through a joint optimization of data routing and radio configuration. The network is modeled by a digraph in which the nodes represent radio base stations and the arcs denote radio links. Under this scenario, a power-efficient configuration can be characterized by a modulation constellation size and a transmission power level. Every link holds a set of power-efficient configurations, each of them associating a capacity with its energy cost. The optimization problem involves deciding the network's configuration and flows that minimize the total energy consumption, while handling all the traffic requirements simultaneously. An exact mathematical formulation of the problem is presented. It relies on a minimum cost multicommodity flow with step increasing cost functions, which is very hard to optimize. We then propose a piecewise linear convex function, obtained by linear interpolation of powerefficient configuration points, that provides a good approximation of the energy consumption on the links, and present a relaxation of the previous formulation that exploits the convexity of the energy cost functions. This yields lower bounds on the energy consumption, and finally a heuristic algorithm based on the fractional optimum is employed to produce feasible solutions. Our models are validated through extensive experiments that are reported and discussed. The results verify the potentialities behind this novel approach. In particular, our algorithm induces a satisfactory integrality gap in practice." |
@INPROCEEDINGS{CNR09,
AUTHOR="D. Coudert and N. Nepomuceno and H. Rivano",
TITLE="Minimizing Energy Consumption by {Power-Efficient} Radio Configuration in Fixed Broadband Wireless Networks",
BOOKTITLE="First IEEE WoWMoM Workshop on Hot Topics in Mesh Networking (HotMESH)",
pages = {6p},
publisher = {IEEE},
ADDRESS="Kos, Greece",
OPTDAYS=15,
MONTH=jun,
YEAR=2009,
ABSTRACT="In this paper, we investigate on minimizing the energy consumption of a fixed broadband wireless network through a joint optimization of data routing and radio configuration. The network is modeled by a digraph in which the nodes represent radio base stations and the arcs denote radio links. Under this scenario, a power-efficient configuration can be characterized by a modulation constellation size and a transmission power level. Every link holds a set of power-efficient configurations, each of them associating a capacity with its energy cost. The optimization problem involves deciding the network's configuration and flows that minimize the total energy consumption, while handling all the traffic requirements simultaneously. An exact mathematical formulation of the problem is presented. It relies on a minimum cost multicommodity flow with step increasing cost functions, which is very hard to optimize. We then propose a piecewise linear convex function, obtained by linear interpolation of powerefficient configuration points, that provides a good approximation of the energy consumption on the links, and present a relaxation of the previous formulation that exploits the convexity of the energy cost functions. This yields lower bounds on the energy consumption, and finally a heuristic algorithm based on the fractional optimum is employed to produce feasible solutions. Our models are validated through extensive experiments that are reported and discussed. The results verify the potentialities behind this novel approach. In particular, our algorithm induces a satisfactory integrality gap in practice.",
url = {http://dx.doi.org/10.1109/WOWMOM.2009.5282434},
pdf = {ftp://ftp-sop.inria.fr/mascotte/Publications/CNR09.pdf},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
x-pays = {BR},
sorte = "conf-int",
}
-
O. Dalle,
F. Giroire,
J. Monteiro,
and S. Pérennes.
Analyse des Corrélations entre Pannes dans les Systèmes de Stockage Pair-à-Pair.
In Augustin Chaintreau and Clemence Magnien, editors,
11ème rencontres francophones sur les Aspects Algorithmiques des Télécommunications (Algotel'2009),
Carry-Le-Rouet France,
pages 4p,
2009.
Note: Best Student Paper Award.
[WWW
] [PDF
]
| Abstract: |
|
{D}ans cet article, nous pr{\'e}sentons et {\'e}tudions des mod{\`e}les analytiques de syst{\`e}mes de stockage pair-{\`a}-pair fiables {\`a} long terme. {L}es pairs sont sujets {\`a} des pannes d{\'e}finitives (d{\'e}faillance du disque, d{\'e}part du pair) induisant la perte de toutes les donn{\'e}es stock{\'e}es par le pair. {C}es pannes ont lieu en continu. {A}fin de p{\'e}renniser les donn{\'e}es il est indispensable d'user de redondance et de maintenir celle-ci au moyen d'un processus permanent de reconstruction. {D}ans un premier temps nous consid{\'e}rons une approche classiquement utilis{\'e}e dans la litt{\'e}rature, consistant {\`a} mod{\'e}liser chaque bloc par une cha{\^i}ne de {M}arkov et {\`a} n{\'e}gliger les interd{\'e}pendances entre blocs. {S}i celle-ci permet le calcul du comportement moyen du syst{\`e}me (par exemple la demande moyenne en bande passante), elle est insuffisante pour en {\'e}valuer les fluctuations. {N}os simulations d{\'e}montrent que ces fluctuations sont tr{\`e}s importantes m{\^e}me pour des grands syst{\`e}mes comportant des milliers de pairs. {N}ous proposons alors un nouveau mod{\`e}le stochastique prenant en compte l'interd{\'e}pendance des pannes de blocs, et nous en donnons une approximation fluide. {C}eci nous permet de caract{\'e}riser le comportement du syst{\`e}me (calcul de tous les moments) mais aussi de le simuler efficacement, car il est ind{\'e}pendant de la taille du syst{\`e}me. {L}a pertinence de notre mod{\`e}le est valid{\'e}e en comparant les r{\'e}sultats obtenus par des simulations utilisant d'un c{\^o}t{\'e} notre mod{\`e}le fluide et de l'autre un mod{\`e}le {\`a} {\'e}v{\'e}nements discrets reproduisant fid{\`e}lement le comportement du syst{\`e}me. |
@CONFERENCE{DGMP09a,
author = {O. Dalle and F. Giroire and J. Monteiro and S. P\'erennes},
title = {Analyse des Corr{\'e}lations entre Pannes dans les Syst{\`e}mes de Stockage Pair-{\`a}-Pair},
booktitle = {11\`eme rencontres francophones sur les Aspects Algorithmiques des T\'el\'ecommunications (Algotel'2009)},
pages = {4p},
year = {2009},
editor = {Augustin Chaintreau and Clemence Magnien},
address = {{C}arry-{L}e-{R}ouet {F}rance },
note = {Best Student Paper Award},
abstract = {{D}ans cet article, nous pr{\'e}sentons et {\'e}tudions des mod{\`e}les analytiques de syst{\`e}mes de stockage pair-{\`a}-pair fiables {\`a} long terme. {L}es pairs sont sujets {\`a} des pannes d{\'e}finitives (d{\'e}faillance du disque, d{\'e}part du pair) induisant la perte de toutes les donn{\'e}es stock{\'e}es par le pair. {C}es pannes ont lieu en continu. {A}fin de p{\'e}renniser les donn{\'e}es il est indispensable d'user de redondance et de maintenir celle-ci au moyen d'un processus permanent de reconstruction. {D}ans un premier temps nous consid{\'e}rons une approche classiquement utilis{\'e}e dans la litt{\'e}rature, consistant {\`a} mod{\'e}liser chaque bloc par une cha{\^i}ne de {M}arkov et {\`a} n{\'e}gliger les interd{\'e}pendances entre blocs. {S}i celle-ci permet le calcul du comportement moyen du syst{\`e}me (par exemple la demande moyenne en bande passante), elle est insuffisante pour en {\'e}valuer les fluctuations. {N}os simulations d{\'e}montrent que ces fluctuations sont tr{\`e}s importantes m{\^e}me pour des grands syst{\`e}mes comportant des milliers de pairs. {N}ous proposons alors un nouveau mod{\`e}le stochastique prenant en compte l'interd{\'e}pendance des pannes de blocs, et nous en donnons une approximation fluide. {C}eci nous permet de caract{\'e}riser le comportement du syst{\`e}me (calcul de tous les moments) mais aussi de le simuler efficacement, car il est ind{\'e}pendant de la taille du syst{\`e}me. {L}a pertinence de notre mod{\`e}le est valid{\'e}e en comparant les r{\'e}sultats obtenus par des simulations utilisant d'un c{\^o}t{\'e} notre mod{\`e}le fluide et de l'autre un mod{\`e}le {\`a} {\'e}v{\'e}nements discrets reproduisant fid{\`e}lement le comportement du syst{\`e}me.},
pdf = {ftp://ftp-sop.inria.fr/mascotte/Publications/DGMP09a.pdf},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={no},
x-pays = {},
url = {http://hal.inria.fr/inria-00485847/en/},
sorte = "conf-nat",
}
-
O. Dalle,
F. Giroire,
J. Monteiro,
and S. Pérennes.
Analysis of Failure Correlation Impact on Peer-to-Peer Storage Systems.
In Proceedings of the 9th IEEE International Conference on Peer-to-Peer Computing (P2P),
pages 184--193,
September 2009.
[WWW
] [PDF
]
| Abstract: |
|
Peer-to-peer storage systems aim to provide a reliable long-term storage at low cost. In such systems, peers fail continuously, hence, the necessity of self-repairing mechanisms to achieve high durability. In this paper, we propose and study analytical models that assess the bandwidth consumption and the probability to lose data of storage systems that use erasure coded redundancy. We show by simulations that the classical stochastic approach found in the literature, that models each block independently, gives a correct approximation of the system average behavior, but fails to capture its variations over time. These variations are caused by the simultaneous loss of multiple data blocks that results from a peer failing (or leaving the system). We then propose a new stochastic model based on a fluid approximation that better captures the system behavior. In addition to its expectation, it gives a correct estimation of its standard deviation. This new model is validated by simulations. |
@INPROCEEDINGS{DGMP09b,
author = {O. Dalle and F. Giroire and J. Monteiro and S. P{\'e}rennes},
title = {Analysis of Failure Correlation Impact on Peer-to-Peer Storage Systems},
booktitle = {Proceedings of the 9th IEEE International Conference on Peer-to-Peer Computing (P2P)},
year = {2009},
month = {sep},
pages = {184--193},
url={http://dx.doi.org/10.1109/P2P.2009.5284518},
abstract = {Peer-to-peer storage systems aim to provide a reliable long-term storage at low cost. In such systems, peers fail continuously, hence, the necessity of self-repairing mechanisms to achieve high durability. In this paper, we propose and study analytical models that assess the bandwidth consumption and the probability to lose data of storage systems that use erasure coded redundancy. We show by simulations that the classical stochastic approach found in the literature, that models each block independently, gives a correct approximation of the system average behavior, but fails to capture its variations over time. These variations are caused by the simultaneous loss of multiple data blocks that results from a peer failing (or leaving the system). We then propose a new stochastic model based on a fluid approximation that better captures the system behavior. In addition to its expectation, it gives a correct estimation of its standard deviation. This new model is validated by simulations.},
pdf = {ftp://ftp-sop.inria.fr/mascotte/Publications/DGMP09b.pdf},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
x-pays = {},
sorte = "conf-int",
}
-
A. Ferreira.
Road-mapping the Digital Revolution: Visions from COST Foresight 2030 (An exercise in multi-disciplinarity).
In Proceedings of IEEE Wireless VITAE'09,
Aalborg, Denmark,
pages 5p,
May 2009.
IEEE Press.
[PDF
]
| Abstract: |
|
From innovation triggered by user virtual communities to remote surgery and new financial instruments, the creative power of individuals is being fostered at proportions previously unseen. The main driver enabling such a pace of innovation, scientific progress, and user adoption is the Digital Revolution. One consequence is that interrelationships between science, technology and society are increasing in complexity and harder to understand. COST Foresight 2030 is an initiative encompassing a set of events designed to explore a multi-disciplinary vision for a future permeated and shaped by the digital revolution. This paper describes the vision behind COST Foresight 2030 and highlights several issues that are likely to become central in the next decades. |
@InProceedings{Fer09,
author = {Ferreira, A.},
title = {Road-mapping the Digital Revolution: Visions from COST Foresight 2030 (An exercise in multi-disciplinarity)},
booktitle = {Proceedings of IEEE Wireless VITAE'09},
year = 2009,
pages = {5p},
month = {May},
address = {Aalborg, Denmark},
publisher = {IEEE Press},
pdf = {ftp://ftp-sop.inria.fr/mascotte/Publications/Fer09.pdf},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
abstract = {From innovation triggered by user virtual communities to remote surgery and new financial instruments, the creative power of individuals is being fostered at proportions previously unseen. The main driver enabling such a pace of innovation, scientific progress, and user adoption is the Digital Revolution. One consequence is that interrelationships between science, technology and society are increasing in complexity and harder to understand. COST Foresight 2030 is an initiative encompassing a set of events designed to explore a multi-disciplinary vision for a future permeated and shaped by the digital revolution. This paper describes the vision behind COST Foresight 2030 and highlights several issues that are likely to become central in the next decades.},
sorte = "conf-int",
}
-
M. Flammini,
A. Marchetti-Spaccamela,
G. Monaco,
L. Moscardelli,
and S. Zaks.
On the complexity of the regenerator placement problem in optical networks.
In Proceedings of the 21st ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2009),
Calgary, Canada,
pages 154-162,
August 2009.
ACM.
[WWW
] [PDF
]
| Abstract: |
|
Placement of regenerators in optical networks has attracted the attention of recent research works in optical networks. In this problem we are given a network, with an underlying topology of a graph G, and with a set of requests that correspond to paths in G. There is a need to put a regenerator every certain distance, because of a decrease in the power of the signal. In this work we investigate the problem of minimizing the number of locations to place the regenerators. We present analytical results regarding the complexity of this problem, in four cases, depending on whether or not there is a bound on the number of regenerators at each node, and depending on whether or not the routing is given or only the requests are given (and part of the solution is also to determine the actual routing). These results include polynomial time algorithms, NP-complete results, approximation algorithms, and inapproximability results. |
@inproceedings{FMM+09b,
sorte = "conf-int",
author = {M. Flammini and A. Marchetti-Spaccamela and G. Monaco and L. Moscardelli and S. Zaks},
title = {On the complexity of the regenerator placement problem in optical networks},
booktitle= {Proceedings of the 21st ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2009)},
address= {Calgary, Canada},
year= {2009},
month = aug,
volume = {},
pages = {154-162},
publisher = {ACM},
series = {},
OPTnote = {},
OPTannote = {},
url = {http://portal.acm.org/citation.cfm?doid=1583991.1584035},
PDF={http://portal.acm.org/citation.cfm?doid=1583991.1584035},
abstract = {Placement of regenerators in optical networks has attracted the attention of recent research works in optical networks. In this problem we are given a network, with an underlying topology of a graph G, and with a set of requests that correspond to paths in G. There is a need to put a regenerator every certain distance, because of a decrease in the power of the signal. In this work we investigate the problem of minimizing the number of locations to place the regenerators. We present analytical results regarding the complexity of this problem, in four cases, depending on whether or not there is a bound on the number of regenerators at each node, and depending on whether or not the routing is given or only the requests are given (and part of the solution is also to determine the actual routing). These results include polynomial time algorithms, NP-complete results, approximation algorithms, and inapproximability results.},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={no},
}
-
M. Flammini,
G. Monaco,
L. Moscardelli,
H. Shachnai,
M. Shalom,
T. Tamir,
and S. Zaks.
Minimizing total busy time in parallel scheduling with application to optical networks.
In Proceedings of the 23rd IEEE International Parallel and Distributed Processing Symposium (IPDPS 2009),
Rome, Italy,
pages 1-12,
May 2009.
IEEE.
[WWW
] [PDF
]
| Abstract: |
|
We consider a scheduling problem in which a bounded number of jobs can be processed simultaneously by a single machine. The input is a set of n jobs J = {J1,..., Jn}. Each job, Jj, is associated with an interval [sj, cj] along which it should be processed. Also given is the parallelism parameter g ges 1, which is the maximal number of jobs that can be processed simultaneously by a single machine. Each machine operates along a contiguous time interval, called its busy interval, which contains all the intervals corresponding to the jobs it processes. The goal is to assign the jobs to machines such that the total busy time of the machines is minimized. The problem is known to be NP-hard already for g = 2. We present a 4-approximation algorithm for general instances, and approximation algorithms with improved ratios for instances with bounded lengths, for instances where any two intervals intersect, and for instances where no interval is properly contained in another. Our study has important application in optimizing the switching costs of optical networks. |
@inproceedings{FMM+09a,
sorte = "conf-int",
author = {M. Flammini and G. Monaco and L. Moscardelli and H. Shachnai and M. Shalom and T. Tamir and S. Zaks},
title = {Minimizing total busy time in parallel scheduling with application to optical networks},
booktitle= {Proceedings of the 23rd IEEE International Parallel and Distributed Processing Symposium (IPDPS 2009)},
address= {Rome, Italy},
year= {2009},
month = may,
volume = {},
pages = {1-12},
publisher = {IEEE},
series = {},
OPTnote = {},
OPTannote = {},
url = {http://ieeexplore.ieee.org/search/wrapper.jsp?arnumber=5161017},
PDF={http://ieeexplore.ieee.org/search/wrapper.jsp?arnumber=5161017},
abstract = {We consider a scheduling problem in which a bounded number of jobs can be processed simultaneously by a single machine. The input is a set of n jobs J = {J1,..., Jn}. Each job, Jj, is associated with an interval [sj, cj] along which it should be processed. Also given is the parallelism parameter g ges 1, which is the maximal number of jobs that can be processed simultaneously by a single machine. Each machine operates along a contiguous time interval, called its busy interval, which contains all the intervals corresponding to the jobs it processes. The goal is to assign the jobs to machines such that the total busy time of the machines is minimized. The problem is known to be NP-hard already for g = 2. We present a 4-approximation algorithm for general instances, and approximation algorithms with improved ratios for instances with bounded lengths, for instances where any two intervals intersect, and for instances where no interval is properly contained in another. Our study has important application in optimizing the switching costs of optical networks.},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={no},
}
-
N. Fountoulakis and B. Reed.
A general critical condition for the emergence of a giant component in random graphs with given degrees.
In European Conference on Combinatorics, Graph Theory and Applications (Eurocomb 2009),
volume 34 of Electronic Notes on Discrete Mathematics,
Bordeaux, France,
pages 639--645,
September 2009.
@InProceedings{FoRe09,
sorte = "conf-int",
AUTHOR={N. Fountoulakis and B. Reed},
TITLE="A general critical condition for the emergence of a giant component in random graphs with given degrees",
booktitle ="European Conference on Combinatorics, Graph Theory and Applications (Eurocomb 2009)",
series = "Electronic Notes on Discrete Mathematics",
PAGES = "639--645",
VOLUME = "34",
year = "2009",
address = "Bordeaux, France",
month = sep,
x-pays={DE},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
abstract = {},
pdf = {},
url ={}
}
-
P. Giabbanelli.
Why having in-person lectures when e-learning and podcasts are available?.
In Proceedings of the 14th Western Canadian Conference on Computing Education (ACM SIGCSE),
pages 42-44,
2009.
@inproceedings{Gia10a,
title = "Why having in-person lectures when e-learning and podcasts are available?",
author = "P. Giabbanelli",
booktitle = "Proceedings of the 14th Western Canadian Conference on Computing Education (ACM SIGCSE)",
pages = {42-44},
year = "2009",
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
sorte = "conf-int",
}
-
F. Giroire,
J. Chandrashekar,
N. Taft,
E. Schooler,
and K. Papagiannaki.
Exploiting Temporal Persistence to Detect Covert Botnet Channels.
In Springer, editor,
12th International Symposium on Recent Advances in Intrusion Detection (RAID'09),
volume 5758 of Lecture Notes in Computer Science,
Saint Malo, France,
pages 326--345,
September 2009.
[PDF
]
| Abstract: |
|
We describe a method to detect botnet command and control traffic and individual end-hosts. We introduce the notion of â⬠destination traffic atomsâ⬠which aggregate the destinations and services that are communicated with. We then compute the â⬠persistenceâ⬠, which is a measure of temporal regularity and that we propose in this paper, for individual destination atoms. Very persistent destination atoms are added to a host's whitelist during a training period. Subsequently, we track the persistence of new destination atoms not already whitelisted, to identify suspicious C&C destinations. A particularly novel aspect is that we track persistence at multiple timescales concurrently. Importantly, our method does not require any a-priori information about destinations, ports, or protocols used in the C&C, nor do we require payload inspection. We evaluate our system using extensive user traffic traces collected from an enterprise network, along with collected botnet traces. We demonstrate that our method correctly identifies a botnet's C&C traffic, even when it is very stealthy. We also show that filtering outgoing traffic with the constructed whitelists dramatically improves the performance of traditional anomaly detectors. Finally, we show that the C&C detection can be achieved with a very low false positive rate. |
@InProceedings{GCT+09,
author = {F. Giroire and J. {C}handrashekar and N. Taft and E. Schooler and K. Papagiannaki},
title = {Exploiting Temporal Persistence to Detect Covert Botnet Channels},
booktitle = {12th International Symposium on Recent Advances in Intrusion Detection (RAID'09)},
OPTcrossref = {},
OPTkey = {},
pages = {326--345},
year = {2009},
editor = {Springer},
volume = {5758},
OPTnumber = {XXXX},
series = {Lecture Notes in Computer Science},
month = sep,
address = {Saint Malo, France},
OPTorganization = {},
OPTpublisher = {},
OPTannote = {},
abstract = {We describe a method to detect botnet command and control traffic and individual end-hosts. We introduce the notion of â⬠destination traffic atomsâ⬠which aggregate the destinations and services that are communicated with. We then compute the â⬠persistenceâ⬠, which is a measure of temporal regularity and that we propose in this paper, for individual destination atoms. Very persistent destination atoms are added to a host's whitelist during a training period. Subsequently, we track the persistence of new destination atoms not already whitelisted, to identify suspicious C&C destinations. A particularly novel aspect is that we track persistence at multiple timescales concurrently. Importantly, our method does not require any a-priori information about destinations, ports, or protocols used in the C&C, nor do we require payload inspection. We evaluate our system using extensive user traffic traces collected from an enterprise network, along with collected botnet traces. We demonstrate that our method correctly identifies a botnet's C&C traffic, even when it is very stealthy. We also show that filtering outgoing traffic with the constructed whitelists dramatically improves the performance of traditional anomaly detectors. Finally, we show that the C&C detection can be achieved with a very low false positive rate.},
pdf = {http://www-sop.inria.fr/members/Frederic.Giroire/publis/GCT09.pdf},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
x-pays = {US},
sorte = "conf-int",
}
-
F. Giroire,
J. Monteiro,
and S. Pérennes.
P2P Storage Systems: How Much Locality Can They Tolerate?.
In Proceedings of the 34th IEEE Conference on Local Computer Networks (LCN),
pages 320--323,
October 2009.
[PDF
]
Keywords:
P2P storage system,
data placement,
performance evaluation,
data durability.
| Abstract: |
|
Large scale peer-to-peer systems are foreseen as a way to provide highly reliable data storage at low cost. To achieve high durability, such P2P systems encode the user data in a set of redundant fragments and distribute them among the peers. In this paper, we study the impact of different data placement strategies on the system performance when using erasure codes redundancy schemes. We compare three policies: two of them local, in which the data are stored in logical neighbors, and the other one global, in which the data are spread randomly in the whole system. We focus on the study of the probability to lose a data block and the bandwidth consumption to maintain enough redundancy. We use simulations to show that, without resource constraints, the average values are the same no matter which placement policy is used. However, the variations in the use of bandwidth are much more bursty under the local policies. When the bandwidth is limited, these bursty variations induce longer maintenance time and henceforth a higher risk of data loss. Finally, we propose a new external reconstruction strategy and a suitable degree of locality that could be introduced in order to combine the efficiency of the global policy with the practical advantages of a local placement. |
@INPROCEEDINGS{GMP09b,
author = {F. Giroire and J. Monteiro and S. P\'erennes},
title = {{P2P} Storage Systems: How Much Locality Can They Tolerate?},
booktitle = {Proceedings of the 34th IEEE Conference on Local Computer Networks (LCN)},
year = {2009},
pages = {320--323},
month = {Oct},
abstract = {Large scale peer-to-peer systems are foreseen as a way to provide highly reliable data storage at low cost. To achieve high durability, such P2P systems encode the user data in a set of redundant fragments and distribute them among the peers. In this paper, we study the impact of different data placement strategies on the system performance when using erasure codes redundancy schemes. We compare three policies: two of them local, in which the data are stored in logical neighbors, and the other one global, in which the data are spread randomly in the whole system. We focus on the study of the probability to lose a data block and the bandwidth consumption to maintain enough redundancy. We use simulations to show that, without resource constraints, the average values are the same no matter which placement policy is used. However, the variations in the use of bandwidth are much more bursty under the local policies. When the bandwidth is limited, these bursty variations induce longer maintenance time and henceforth a higher risk of data loss. Finally, we propose a new external reconstruction strategy and a suitable degree of locality that could be introduced in order to combine the efficiency of the global policy with the practical advantages of a local placement.},
keywords = {P2P storage system, data placement, performance evaluation, data durability},
pdf = {ftp://ftp-sop.inria.fr/mascotte/Publications/GMP09.pdf},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
x-pays = {},
sorte = "conf-int",
}
-
C. Gomes and J. Galtier.
Optimal and Fair Transmission Rate Allocation Problem in Multi-hop Cellular Networks.
In 8th International Conference on AD-HOC Networks & Wireless (ADHOC NOW),
volume 5793 of Lecture Notes in Computer Science,
Murcia, Spain,
pages 327-340,
September 2009.
Springer.
[PDF
]
| Abstract: |
|
We deal with the rate allocation problem for downlink in a Multi-hop Cellular Network. A mathematical model is provided to assign transmission rates in order to reach an optimal and fair solution. We prove that under some conditions that are often met, the problem can be reduced to a single-hop cellular network problem. The validity of our proof is confirmed experimentally. |
@InProceedings{GG09,
sorte = "conf-int",
author ={C. Gomes and J. Galtier},
title = {Optimal and Fair Transmission Rate Allocation Problem in Multi-hop Cellular Networks},
booktitle ={8th International Conference on AD-HOC Networks \& Wireless (ADHOC NOW)},
month = sep,
year ={2009},
publisher = {Springer},
series = {Lecture Notes in Computer Science},
volume = {5793},
pages = {327-340},
address = {Murcia, Spain},
abstract = {We deal with the rate allocation problem for downlink in a Multi-hop Cellular Network. A mathematical model is provided to assign transmission rates in order to reach an optimal and fair solution. We prove that under some conditions that are often met, the problem can be reduced to a single-hop cellular network problem. The validity of our proof is confirmed experimentally.},
PDF = {sftp://cgomes@mascotte.inria.fr/net/serveurs/www-sop/members/Cristiana.Gomes/id085_GomesGaltier.pdf},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
}
-
D. Gonçalves,
F. Havet,
A. Pinlou,
and S. Thomassé.
Spanning galaxies in digraphs.
In European Conference on Combinatorics, Graph Theory and Applications (Eurocomb 2009),
volume 34 of Electronic Notes on Discrete Mathematics,
Bordeaux, France,
pages 139--143,
September 2009.
[PDF
]
| Abstract: |
|
A \emph{star} is an arborescence in which the root dominates all the other vertices. A \emph{galaxy} is a vertex-disjoint union of stars. The \emph{directed star arboricity} of a digraph $D$,denoted by $dst(D)$, is the minimum number of galaxies needed to cover $A(D)$. In this paper, we show that $dst(D)\leq \Delta(D)+1$ and that if $D$ is ascyclic then $dst(D)\leq \Delta(D)$. These results are proving by considering the existence of spanning galaxy in digraphs. Thus, we study the problem of deciding whether a digraph $D$ has a spanning galaxy or not. We show that it is NP-complete (even when restricted to acyclic digraphs) but that it becomes polynomial-time solvable when restricted to strongly connected digraphs. |
@InProceedings{GHPT09,
sorte = "conf-int",
AUTHOR="D. Gon\c{c}alves and F. Havet and A. Pinlou and S. Thomass\'e",
TITLE="Spanning galaxies in digraphs",
booktitle ="European Conference on Combinatorics, Graph Theory and Applications (Eurocomb 2009)",
series = "Electronic Notes on Discrete Mathematics",
PAGES = "139--143",
VOLUME = "34",
year = "2009",
address = "Bordeaux, France",
month = sep,
pdf = {ftp://ftp-sop.inria.fr/mascotte/Publications/GHPT09.pdf},
abstract={A \emph{star} is an arborescence in which the root dominates all the other vertices. A \emph{galaxy} is a vertex-disjoint union of stars. The \emph{directed star arboricity} of a digraph $D$,denoted by $dst(D)$, is the minimum number of galaxies needed to cover $A(D)$. In this paper, we show that $dst(D)\leq \Delta(D)+1$ and that if $D$ is ascyclic then $dst(D)\leq \Delta(D)$. These results are proving by considering the existence of spanning galaxy in digraphs. Thus, we study the problem of deciding whether a digraph $D$ has a spanning galaxy or not. We show that it is NP-complete (even when restricted to acyclic digraphs) but that it becomes polynomial-time solvable when restricted to strongly connected digraphs. },
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
x-pays = {}
}
-
F. Guinand and B. Onfroy.
MANET : étude de l'impact de la mobilité sur la connexité du réseau.
In 11èmes Rencontres Francophones sur les Aspects Algorithmiques de Télécommunications (AlgoTel'09),
pages 2p,
June 2009.
Note: Poster.
[PDF
]
Keywords:
réseau mobile ad-hoc,
graphe dynamique,
MANET,
connexité,
algorithme.
| Abstract: |
|
Avec la multiplication des terminaux communiquant, les r\'eseaux ad-hoc dynamiques ont maintenant la capacit\'e de se d\'evelopper. Ces r\'eseaux ne poss\`edent pas d'infrastructure fixe, et les d\'eplacements rapides des terminaux rendent instables les voisins de ces noeuds mobiles. Dans l'objectif de concevoir des m\'ethodes d\'ecentralis\'ees efficaces, nos travaux actuels tentent d'\'evaluer l'impact des diff\'erents param\`etres de mobilit\'e sur la connexit\'e du graphe repr\'esentatif du r\'eseau form\'e par ces terminaux mobiles. Le mod\`ele de mobilit\'e \'etudi\'e est le Random Waypoint. L'objectif est donc de d\'eterminer quels param\`etres de mobilit\'e (vitesse de d\'eplacement, temps de pause, ...) ont un impact significatif sur la connexit\'e du r\'eseau. |
@InProceedings{GuOn09a,
sorte = "conf-nat",
OPTKEY = { },
AUTHOR = { Guinand, F. and Onfroy, B. },
TITLE = { {MANET} : \'etude de l'impact de la mobilit\'e sur la connexit\'e du r\'eseau },
booktitle = {11\`emes Rencontres Francophones sur les Aspects Algorithmiques de T\'el\'ecommunications (AlgoTel'09) },
pages = {2p},
MONTH = jun,
PDF = {ftp://ftp-sop.inria.fr/mascotte/personnel/Brice.Onfroy/publi/2009/pdf/2009_algotel_[guinand-onfroy]_mobility_impact_on_connectivity__poster.pdf},
YEAR = { 2009 },
NOTE = { Poster },
OPTANNOTE = {},
KEYWORDS = {r\'eseau mobile ad-hoc, graphe dynamique, MANET, connexit\'e, algorithme},
ABSTRACT = {Avec la multiplication des terminaux communiquant, les r\'eseaux ad-hoc dynamiques ont maintenant la capacit\'e de se d\'evelopper. Ces r\'eseaux ne poss\`edent pas d'infrastructure fixe, et les d\'eplacements rapides des terminaux rendent instables les voisins de ces noeuds mobiles. Dans l'objectif de concevoir des m\'ethodes d\'ecentralis\'ees efficaces, nos travaux actuels tentent d'\'evaluer l'impact des diff\'erents param\`etres de mobilit\'e sur la connexit\'e du graphe repr\'esentatif du r\'eseau form\'e par ces terminaux mobiles. Le mod\`ele de mobilit\'e \'etudi\'e est le Random Waypoint. L'objectif est donc de d\'eterminer quels param\`etres de mobilit\'e (vitesse de d\'eplacement, temps de pause, ...) ont un impact significatif sur la connexit\'e du r\'eseau.},
OPTx-editorial-board = {yes},
OPTx-proceedings = {yes},
OPTx-international-audience = {yes}
}
-
F. Havet and C. Linhares Sales.
Combinatória e Problemas em Redes de Telecomunicações.
In Colloque d'Informatique: Brésil / INRIA, Coopérations, Avancées et Défis,
Bento Gonçalves, Brazil,
pages 4p,
July 2009.
[PDF
]
| Abstract: |
|
In this paper, we summarize some problems arising in telecommunication networks which have been studied in the scope of the cooperation between our teams ParGO (UFC) and Mascotte (INRIA). We also present their modeling by graph coloring problems and some partial results we have ob- tained. |
@InProceedings{HaLi09,
sorte = "conf-int",
AUTHOR="Havet, F. and Linhares Sales, C.",
TITLE="Combinat\'{o}ria e Problemas em Redes de Telecomunica\c{c}\~{o}es",
booktitle ="Colloque d'Informatique: Br\'esil / INRIA, Coop\'erations, Avanc\'ees et D\'efis",
year = "2009",
pages = {4p},
address = "Bento Gon\c{c}alves, Brazil",
month = jul,
pdf = {ftp://ftp-sop.inria.fr/mascotte/Publications/HaLi09.pdf},
abstract={In this paper, we summarize some problems arising in telecommunication networks which have been studied in the scope of the cooperation between our teams ParGO (UFC) and Mascotte (INRIA). We also present their modeling by graph coloring problems and some partial results we have ob- tained.},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
x-pays = {BR},
}
-
J. Himmelspach,
O. Dalle,
and J. Ribault.
Design considerations for M&S software.
In D. Rossetti,
R. R. Hill,
B. Johansson,
A. Dunkin,
and R. G. Ingalls, editors,
Proceedings of the Winter Simulation Conference (WSC'09),
Austin, TX,
pages 12p,
December 2009.
Note: Invited Paper.
[WWW
] [PDF
]
| Abstract: |
|
The development of M&S products often seems to be driven by need: people start coding because they are interested in either a concrete simulation study, or they are interested in a (single) research subject of M&S methodology. We claim that discussing, designing, developing, and comparing M&S products should be based on software engineering concepts. We shortly introduce some of these engineering concepts and discuss how these relate to the M&S domain. By describing two examples, OSA and JAMES II, we illustrate that reuse might play an important role in the development of high quality M&S products as the examples allow reuse on the level of models and scenarios, on the level of "simulation studies", of algorithms (e.g., reuse of event queues, random number generators), across hardware architectures / operating systems, and of analysis tools. |
@InProceedings{HDR09,
author = {J. Himmelspach and O. Dalle and J. Ribault},
title = {Design considerations for {M}\&{S} software},
x-pays = {DE},
OPTcrossref = {},
OPTkey = {},
booktitle = {Proceedings of the Winter Simulation Conference (WSC'09)},
pages = {12p},
year = {2009},
editor = {D. Rossetti and R. R. Hill and B. Johansson and A. Dunkin and R. G. Ingalls},
OPTvolume = {},
OPTnumber = {},
OPTseries = {},
address = {Austin, TX},
month = dec,
OPTorganization = {},
OPTpublisher = {},
note = {Invited Paper},
OPTannote = {},
ABSTRACT = {The development of M&S products often seems to be driven by need: people start coding because they are interested in either a concrete simulation study, or they are interested in a (single) research subject of M&S methodology. We claim that discussing, designing, developing, and comparing M&S products should be based on software engineering concepts. We shortly introduce some of these engineering concepts and discuss how these relate to the M&S domain. By describing two examples, OSA and JAMES II, we illustrate that reuse might play an important role in the development of high quality M&S products as the examples allow reuse on the level of models and scenarios, on the level of "simulation studies", of algorithms (e.g., reuse of event queues, random number generators), across hardware architectures / operating systems, and of analysis tools.},
URL = {http://wwwmosi.informatik.uni-rostock.de/mosi/veroeffentlichungen/inproceedingsreference.2009-06-01.2218174380},
pdf = {ftp://ftp-sop.inria.fr/mascotte/Publications/HiDaRi09.pdf},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
sorte = "inv-conf",
}
-
K. Kawarabayashi and B. Reed.
Hadwiger's Conjecture is decidable.
In 41th ACM Symposium on Theory of Computing (STOC 2009),
pages 445--454,
2009.
[WWW
] [PDF
]
| Abstract: |
|
The famous Hadwiger's conjecture asserts that every graph with no Kt-minor is (t-1)-colorable. The case t=5 is known to be equivalent to the Four Color Theorem by Wagner, and the case t=6 is settled by Robertson, Seymour and Thomas. So far the cases t \geq 7 are wide open. In this paper, we prove the following two theorems: There is an O(n2) algorithm to decide whether or not a given graph G satisfies Hadwiger's conjecture for the case t. Every minimal counterexample to Hadwiger's conjecture for the case t has at most f(t) vertices for some explicit bound f(t). The bound f(t) is at most pppt, where p=101010t. Our proofs for both results use the well-known result by Thomassen [46] for 5-list-coloring planar graphs, together with some results (but not the decomposition theorem) of Graph Minors in [36]. Concerning the first result, we prove the following stronger theorem: For a given graph G and any fixed t, there is an O(n2) algorithm to output one of the following: a (t-1)-coloring of G, or a Kt- minor of G, or a minor H of G of order at most f(t) such that H does not have a Kt-minor nor is (t-1)-colorable. The last conclusion implies that H is a counterexample to Hadwiger's conjecture with at most f(t) vertices for the case t. The time complexity of the algorithm matches the best known algorithms for 4-coloring planar graphs (the Four Color Theorem), due to Appel and Hakken, and Robertson, Sanders, Seymour and Thomas, respectively. Let us observe that when t=5, the algorithm gives rise to an algorithm for the Four Color Theorem. The second theorem follows from our structure theorem, which has the following corollary: Every minimal counterexample G to Hadwiger's conjecture for the case t either has at most f(t) vertices, or has a vertex set Z of order at most t-5 such that G-Z is planar. It follows from the Four Color Theorem that the second assertion does not happen to any minimal counterexample to Hadwiger's conjecture for the case t. Thus in constant time, we can decide Hadwiger's conjecture for the case t. |
@InProceedings{KaRe09c,
sorte = "conf-int",
author={K. Kawarabayashi and B. Reed},
booktitle = {41th ACM Symposium on Theory of Computing (STOC 2009)},
title={Hadwiger's Conjecture is decidable},
year={2009},
PAGES ={445--454},
x-pays = {JP},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
abstract = {The famous Hadwiger's conjecture asserts that every graph with no Kt-minor is (t-1)-colorable. The case t=5 is known to be equivalent to the Four Color Theorem by Wagner, and the case t=6 is settled by Robertson, Seymour and Thomas. So far the cases t \geq 7 are wide open. In this paper, we prove the following two theorems: There is an O(n2) algorithm to decide whether or not a given graph G satisfies Hadwiger's conjecture for the case t. Every minimal counterexample to Hadwiger's conjecture for the case t has at most f(t) vertices for some explicit bound f(t). The bound f(t) is at most pppt, where p=101010t. Our proofs for both results use the well-known result by Thomassen [46] for 5-list-coloring planar graphs, together with some results (but not the decomposition theorem) of Graph Minors in [36]. Concerning the first result, we prove the following stronger theorem: For a given graph G and any fixed t, there is an O(n2) algorithm to output one of the following: a (t-1)-coloring of G, or a Kt- minor of G, or a minor H of G of order at most f(t) such that H does not have a Kt-minor nor is (t-1)-colorable. The last conclusion implies that H is a counterexample to Hadwiger's conjecture with at most f(t) vertices for the case t. The time complexity of the algorithm matches the best known algorithms for 4-coloring planar graphs (the Four Color Theorem), due to Appel and Hakken, and Robertson, Sanders, Seymour and Thomas, respectively. Let us observe that when t=5, the algorithm gives rise to an algorithm for the Four Color Theorem. The second theorem follows from our structure theorem, which has the following corollary: Every minimal counterexample G to Hadwiger's conjecture for the case t either has at most f(t) vertices, or has a vertex set Z of order at most t-5 such that G-Z is planar. It follows from the Four Color Theorem that the second assertion does not happen to any minimal counterexample to Hadwiger's conjecture for the case t. Thus in constant time, we can decide Hadwiger's conjecture for the case t.},
pdf = {http://portal.acm.org/ft_gateway.cfm?id=1536476&type=pdf&coll=GUIDE&dl=GUIDE&CFID=60373272&CFTOKEN=66048899},
url ={http://portal.acm.org/citation.cfm?id=1536414.1536476}
}
-
K. Kawarabayashi and B. Reed.
A nearly linear time algorithm for the half integral parity disjoint paths packing problem.
In Proceedings of the ACM-SIAM Symposium on Discrete Algorithm (SODA 2009),
pages 1183--1192,
January 2009.
[WWW
] [PDF
]
| Abstract: |
|
We consider the following problem, which is called the half integral parity disjoint paths packing problem. Input: A graph G, k pair of vertices (s1, t1), (s2, t2), ...,(sk, tk) in G (which are sometimes called terminals), and a parity li for each i with $1 \leq i \leq k$, where li = 0 or 1. Output: Paths P1, ..., Pk in G such that Pi joins si and ti for i = 1, 2, ..., k and parity of length of the path Pi is li, i.e, if li = 0, then length of Pi is even, and if li = 1, then length of Pi is odd for i = 1, 2, ..., k. In addition, each vertex is on at most two of these paths. We present an O(m \alpha(m, n) log n) algorithm for fixed k, where n, m are the number of vertices and the number of edges, respectively, and the function \alpha(m, n) is the inverse of the Ackermann function (see by Tarjan [43]). This is the first polynomial time algorithm for this problem, and generalizes polynomial time algorithms by Kleinberg [23] and Kawarabayashi and Reed [20], respectively, for the half integral disjoint paths packing problem, i.e., without the parity requirement. As with the Robertson-Seymour algorithm to solve the k disjoint paths problem, in each iteration, we would like to either use a huge clique minor as a "crossbar", or exploit the structure of graphs in which we cannot find such a minor. Here, however, we must maintain the parity of the paths and can only use an "odd clique minor". We must also describe the structure of those graphs in which we cannot find such a minor and discuss how to exploit it. We also have algorithms running in O(m(1 + \epsilon)) time for any \epsilon > 0 for this problem, if k is up to o(log log log n) for general graphs, up to o(log log n) for planar graphs, and up to o(log log n/g) for graphs on the surface, where g is Euler genus. Furthermore, if k is fixed, then we have linear time algorithms for the planar case and for the bounded genus case. |
@InProceedings{KaRe09b,
sorte = "conf-int",
author={K. Kawarabayashi and B. Reed},
booktitle={Proceedings of the ACM-SIAM Symposium on Discrete Algorithm (SODA 2009)},
month={jan},
title={A nearly linear time algorithm for the half integral parity disjoint paths packing problem},
year={2009},
PAGES ={1183--1192},
x-pays = {JP},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
abstract = {We consider the following problem, which is called the half integral parity disjoint paths packing problem. Input: A graph G, k pair of vertices (s1, t1), (s2, t2), ...,(sk, tk) in G (which are sometimes called terminals), and a parity li for each i with $1 \leq i \leq k$, where li = 0 or 1. Output: Paths P1, ..., Pk in G such that Pi joins si and ti for i = 1, 2, ..., k and parity of length of the path Pi is li, i.e, if li = 0, then length of Pi is even, and if li = 1, then length of Pi is odd for i = 1, 2, ..., k. In addition, each vertex is on at most two of these paths. We present an O(m \alpha(m, n) log n) algorithm for fixed k, where n, m are the number of vertices and the number of edges, respectively, and the function \alpha(m, n) is the inverse of the Ackermann function (see by Tarjan [43]). This is the first polynomial time algorithm for this problem, and generalizes polynomial time algorithms by Kleinberg [23] and Kawarabayashi and Reed [20], respectively, for the half integral disjoint paths packing problem, i.e., without the parity requirement. As with the Robertson-Seymour algorithm to solve the k disjoint paths problem, in each iteration, we would like to either use a huge clique minor as a "crossbar", or exploit the structure of graphs in which we cannot find such a minor. Here, however, we must maintain the parity of the paths and can only use an "odd clique minor". We must also describe the structure of those graphs in which we cannot find such a minor and discuss how to exploit it. We also have algorithms running in O(m(1 + \epsilon)) time for any \epsilon > 0 for this problem, if k is up to o(log log log n) for general graphs, up to o(log log n) for planar graphs, and up to o(log log n/g) for graphs on the surface, where g is Euler genus. Furthermore, if k is fixed, then we have linear time algorithms for the planar case and for the bounded genus case.},
pdf = {http://www.siam.org/proceedings/soda/2009/SODA09_128_kawarabayashik.pdf},
url ={http://portal.acm.org/citation.cfm?id=1496770.1496898}
}
-
S. Kennedy,
C. Meagher,
and B. Reed.
Fractionally Edge Colouring Graphs with Large Maximum Degree in Linear Time.
In European Conference on Combinatorics, Graph Theory and Applications (Eurocomb 2009),
volume 34 of Electronic Notes on Discrete Mathematics,
Bordeaux, France,
pages 47--51,
September 2009.
| Abstract: |
|
For any c>1, we describe a linear time algorithm for fractionally edge colouring simple graphs with maximum degree at least |V|/c. |
@InProceedings{KMR09,
sorte = "conf-int",
AUTHOR={S. Kennedy and C. Meagher and B. Reed},
TITLE="Fractionally Edge Colouring Graphs with Large Maximum Degree in Linear Time",
booktitle ="European Conference on Combinatorics, Graph Theory and Applications (Eurocomb 2009)",
series = "Electronic Notes on Discrete Mathematics",
PAGES = "47--51",
VOLUME = "34",
year = "2009",
address = "Bordeaux, France",
month = sep,
x-pays = {CA},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
abstract = {For any c>1, we describe a linear time algorithm for fractionally edge colouring simple graphs with maximum degree at least |V|/c.},
pdf = {},
url ={}
}
-
Z. Li and I. Sau.
Graph Partitioning and Traffic Grooming with Bounded Degree Request Graph.
In 35th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2009),
volume 5911 of Lecture Notes in Computer Science,
pages 250-261,,
June 2009.
Note: Best student paper award.
[PDF
]
| Abstract: |
|
We study a graph partitioning problem which arises from traffic grooming in optical networks. We wish to minimize the equipment cost in a SONET WDM ring network by minimizing the number of Add-Drop Multiplexers (ADMs) used. We consider the version introduced by Mu{\~n}oz and Sau~[Mu{\~n}oz and Sau, WG 08] where the ring is unidirectional with a grooming factor $C$, and we must design the network (namely, place the ADMs at the nodes) so that it can support \emph{any} request graph with maximum degree at most $\Delta$. This problem is essentially equivalent to finding the least integer $M(C,\Delta)$ such that the edges of any graph with maximum degree at most $\Delta$ can be partitioned into subgraphs with at most $C$ edges and each vertex appears in at most $M(C,\Delta)$ subgraphs~[Mu{\~n}oz and Sau, WG 08] . The cases where $\Delta=2$ and $\Delta=3,C\neq 4$ were solved by Mu{\~n}oz and Sau~[Mu{\~n}oz and Sau, WG 08] . In this article we establish the value of $M(C,\Delta)$ for many more cases, leaving open only the case where $\Delta \geq 5$ is odd, $\Delta \pmod{2C}$ is between $3$ and $C-1$, $C\geq 4$, and the request graph does not contain a perfect matching. In particular, we answer a conjecture of~[Mu{\~n}oz and Sau, WG 08] . |
@INPROCEEDINGS{LiSa09a,
sorte = "conf-int",
title = {Graph Partitioning and Traffic Grooming with Bounded Degree Request Graph},
author = {Z. Li and I. Sau},
booktitle = {35th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2009)},
year = {2009},
month = jun,
series= {Lecture Notes in Computer Science},
volume= {5911},
pages = {250-261,},
location = {Montpellier, France},
note = {Best student paper award},
pdf = {ftp://ftp-sop.inria.fr/mascotte/Publications/LiSa09.pdf},
abstract = {We study a graph partitioning problem which arises from traffic grooming in optical networks. We wish to minimize the equipment cost in a SONET WDM ring network by minimizing the number of Add-Drop Multiplexers (ADMs) used. We consider the version introduced by Mu{\~n}oz and Sau~[Mu{\~n}oz and Sau, WG 08] where the ring is unidirectional with a grooming factor $C$, and we must design the network (namely, place the ADMs at the nodes) so that it can support \emph{any} request graph with maximum degree at most $\Delta$. This problem is essentially equivalent to finding the least integer $M(C,\Delta)$ such that the edges of any graph with maximum degree at most $\Delta$ can be partitioned into subgraphs with at most $C$ edges and each vertex appears in at most $M(C,\Delta)$ subgraphs~[Mu{\~n}oz and Sau, WG 08] . The cases where $\Delta=2$ and $\Delta=3,C\neq 4$ were solved by Mu{\~n}oz and Sau~[Mu{\~n}oz and Sau, WG 08] . In this article we establish the value of $M(C,\Delta)$ for many more cases, leaving open only the case where $\Delta \geq 5$ is odd, $\Delta \pmod{2C}$ is between $3$ and $C-1$, $C\geq 4$, and the request graph does not contain a perfect matching. In particular, we answer a conjecture of~[Mu{\~n}oz and Sau, WG 08] .},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
}
-
C. Linhares Sales and L. Sampaio.
b-coloring of m-tight graphs.
In T. Liebling and J. Szwarcfiter, editors,
LAGOS'09 - V Latin-American Algorithms, Graphs and Optimization Symposium,
volume 35 of Electronic Notes in Discrete Mathematics,
Gramado, Brazil,
pages 209 - 214,
March 2009.
Elsevier.
[WWW
] [PDF
]
@InProceedings{LiSa09b,
sorte = "conf-int",
author = {Linhares Sales, C. and Sampaio, L.},
title = {b-coloring of m-tight graphs},
OPTcrossref = {},
OPTkey = {},
booktitle = {LAGOS'09 - V Latin-American Algorithms, Graphs and Optimization Symposium},
year = {2009},
editor = {T. Liebling and J. Szwarcfiter},
volume = {35},
OPTnumber = {},
pages = {209 - 214},
series = {Electronic Notes in Discrete Mathematics},
issn = "1571-0653",
address = {Gramado, Brazil},
month = mar,
OPTorganization = {},
publisher = {Elsevier},
OPTannote = {},
doi = "DOI: 10.1016/j.endm.2009.11.035",
url = {http://dx.doi.org/10.1016/j.endm.2009.11.035},
pdf = {ftp://ftp-sop.inria.fr/mascotte/Publications/LiSab.pdf},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
x-pays = {BR},
}
-
J-C. Maureira Bravo,
D. Dujovne,
and O. Dalle.
Generation of Realistic 802.11 Interferences in the OMNeT++ INET Framework Based on Real Traffic Measurements.
In Second International Workshop on OMNeT++,
Rome, Italy,
pages 8p,
March 2009.
[PDF
]
| Abstract: |
|
Realistic simulation of 802.11 traffic subject to high interference, for example in dense urban areas, is still an open issue. Many studies do not address the interference problem properly. In this paper, we present our preliminary work on a method to recreate interference traffic from real measurements. The method consists in capturing real traffic traces and generating interference patterns based on the recorded information. Furthermore, we assume that the coordinates of the sources of interference in the real scene are not known a priori. We introduce an extension to Omnet++ INET-Framework to replay the recreated interference in a transparent way into a simulation. We validate our proposed method by comparing it against the real measurements taken from the scene. Furthermore we present an evaluation of how the injected interference affects the simulated results on three arbitrary simulated scenarios. |
@InProceedings{DDM09,
author = {J-C. {Maureira Bravo} and D. Dujovne and O. Dalle},
title = {Generation of Realistic 802.11 Interferences in the {OMNeT}++ {INET} Framework Based on Real Traffic Measurements},
OPTcrossref = {},
OPTkey = {},
booktitle = {Second International Workshop on {OMNeT}++},
pages = {8p},
year = {2009},
OPTeditor = {},
OPTvolume = {},
OPTnumber = {},
OPTseries = {},
address = {Rome, Italy},
month = mar,
OPTorganization = {},
OPTpublisher = {},
OPTannote = {},
ABSTRACT = {Realistic simulation of 802.11 traffic subject to high interference, for example in dense urban areas, is still an open issue. Many studies do not address the interference problem properly. In this paper, we present our preliminary work on a method to recreate interference traffic from real measurements. The method consists in capturing real traffic traces and generating interference patterns based on the recorded information. Furthermore, we assume that the coordinates of the sources of interference in the real scene are not known a priori. We introduce an extension to Omnet++ INET-Framework to replay the recreated interference in a transparent way into a simulation. We validate our proposed method by comparing it against the real measurements taken from the scene. Furthermore we present an evaluation of how the injected interference affects the simulated results on three arbitrary simulated scenarios.},
PDF = {ftp://ftp-sop.inria.fr/mascotte/Publications/DDM09.pdf},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
x-pays = {CL},
sorte = "conf-int",
}
-
J-C. Maureira Bravo,
P. Uribe,
O. Dalle,
T. Asahi,
and J. Amaya.
Component based approach using OMNeT++ for Train Communication Modeling.
In Proceedings of 9th International Conference on ITS Telecommunication,
Lille, France,
pages 6p,
October 2009.
[PDF
]
| Abstract: |
|
This paper reports on our experience in using OMNeT++ to develop a network simulator focused on railway environments. Common design problems are analyzed, making emphasis on radio communication models. Scalability issues are raised when modeling the large topologies that are associated with railway communications. Our conclusions point out that model reusability must be reinforced and that a component-based design must be adopted in order to build a tool for generating valuable performance results. |
@InProceedings{AA+09,
author = {J-C. {Maureira Bravo} and P. Uribe and O. Dalle and T. Asahi and J. Amaya},
title = {Component based approach using {OMNeT++} for Train Communication Modeling},
OPTcrossref = {},
OPTkey = {},
booktitle = {Proceedings of 9th International Conference on ITS Telecommunication},
pages = {6p},
year = {2009},
editor = {},
OPTvolume = {},
OPTnumber = {},
OPTseries = {},
address = {Lille, France},
month = oct,
OPTorganization = {INRETS},
OPTpublisher = {},
OPTannote = {},
ABSTRACT = {This paper reports on our experience in using OMNeT++ to develop a network simulator focused on railway environments. Common design problems are analyzed, making emphasis on radio communication models. Scalability issues are raised when modeling the large topologies that are associated with railway communications. Our conclusions point out that model reusability must be reinforced and that a component-based design must be adopted in order to build a tool for generating valuable performance results.},
PDF = {ftp://ftp-sop.inria.fr/mascotte/Publications/AADMU09.pdf},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
x-lisa09pays = {CL},
sorte = "conf-int",
}
-
G. Mertzios,
I. Sau,
and S. Zaks.
A New Intersection Model and Improved Algorithms for Tolerance Graphs.
In 35th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2009),
volume 5911 of Lecture Notes in Computer Science,
pages 285-295,
06 2009.
[PDF
]
| Abstract: |
|
Tolerance graphs model interval relations in such a way that intervals can tolerate a certain degree of overlap without being in con ict. This class of graphs, which generalizes in a natural way both interval and permutation graphs, has attracted many research efforts since their introduction in [10], as it finds many important applications in constraint-based temporal reasoning, resource allocation and scheduling problems, among others. In this article we propose the first non-trivial intersection model for general tolerance graphs, given by three-dimensional parallelepipeds, which extends the widely known intersection model of parallelograms in the plane that characterizes the class of bounded tolerance graphs. Apart from being important on its own, this new representation also enables us to improve the time complexity of three problems on tolerance graphs. Namely, we present optimal ${\cal O}(n \log n)$ algorithms for computing a minimum coloring and a maximum clique, and an ${\cal O}(n2)$ algorithm for computing a maximum weight independent set in a tolerance graph with n vertices, thus improving the best known running times ${\cal O}(n2)$ and ${\cal O}(n3)$ for these problems, respectively. |
@INPROCEEDINGS{MSZ09a,
sorte = "conf-int",
title = {A New Intersection Model and Improved Algorithms for Tolerance Graphs},
author = {G. Mertzios and I. Sau and S. Zaks},
booktitle = {35th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2009)},
year = {2009},
month = 06,
series= {Lecture Notes in Computer Science},
volume= {5911},
pages = {285-295},
location = {Montpellier, France},
pdf = {ftp://ftp-sop.inria.fr/mascotte/Publications/MSZ09.pdf},
abstract = {Tolerance graphs model interval relations in such a way that intervals can tolerate a certain degree of overlap without being in con ict. This class of graphs, which generalizes in a natural way both interval and permutation graphs, has attracted many research efforts since their introduction in [10], as it finds many important applications in constraint-based temporal reasoning, resource allocation and scheduling problems, among others. In this article we propose the first non-trivial intersection model for general tolerance graphs, given by three-dimensional parallelepipeds, which extends the widely known intersection model of parallelograms in the plane that characterizes the class of bounded tolerance graphs. Apart from being important on its own, this new representation also enables us to improve the time complexity of three problems on tolerance graphs. Namely, we present optimal ${\cal O}(n \log n)$ algorithms for computing a minimum coloring and a maximum clique, and an ${\cal O}(n2)$ algorithm for computing a maximum weight independent set in a tolerance graph with n vertices, thus improving the best known running times ${\cal O}(n2)$ and ${\cal O}(n3)$ for these problems, respectively.},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
}
-
C. Molle and M-E. Voge.
Effects of the Acknowledgment Traffic on the Capacity of Wireless Mesh Networks.
In 69th IEEE Vehicular Technology Conference (VTC2009-Spring),
Barcelona, Spain,
pages 5p,
April 2009.
[PDF
]
| Abstract: |
|
Since the emergence of ubiquitous computing, evaluating wireless network performances has become one of the major economic issues. Among the existing performance indicators, the network {\em capacity}, defined as the maximal amount of flow carried by a topology during a fixed time period, is essential. Some cross-layer characteristics have to be taken into account in order to optimally allocate the common resources. In this article, a comparative study is done between interference consequences in the two following models: (i) usual IEEE 802.11 MAC layer with acknowledgments at each hop, and (ii) block acknowledgments reported at the transport layer that can be included in the IEEE 802.16 standard. Cross-layer properties are modeled in a linear programming formulation that is solved using the column generation process. We quantify the gain in capacity induced by the move of the MAC acknowledgments into the transport layer, and show the better load distribution obtained in the network with the second model. |
@inproceedings{MoVo09,
sorte = "conf-int",
author = {C. Molle and M-E. Voge},
title = {Effects of the Acknowledgment Traffic on the Capacity of Wireless Mesh Networks},
booktitle= {69th IEEE Vehicular Technology Conference (VTC2009-Spring)},
pages = {5p},
address= {Barcelona, Spain},
year= {2009},
month = apr,
OPTnote = {},
OPTannote = {},
PDF={ftp://ftp-sop.inria.fr/mascotte/Publications/MoVo09.pdf},
abstract = {Since the emergence of ubiquitous computing, evaluating wireless network performances has become one of the major economic issues. Among the existing performance indicators, the network {\em capacity}, defined as the maximal amount of flow carried by a topology during a fixed time period, is essential. Some cross-layer characteristics have to be taken into account in order to optimally allocate the common resources. In this article, a comparative study is done between interference consequences in the two following models: (i) usual IEEE 802.11 MAC layer with acknowledgments at each hop, and (ii) block acknowledgments reported at the transport layer that can be included in the IEEE 802.16 standard. Cross-layer properties are modeled in a linear programming formulation that is solved using the column generation process. We quantify the gain in capacity induced by the move of the MAC acknowledgments into the transport layer, and show the better load distribution obtained in the network with the second model.},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
}
-
M. Molloy and B. A. Reed.
Asymptotically optimal frugal colouring.
In Proceedings of Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA),
pages 106-114,
2009.
[WWW
] [PDF
]
| Abstract: |
|
We prove that every graph with maximum degree \Delta can be properly (\Delta + 1)-coloured so that no colour appears more than O(log \Delta / log log \Delta) times in the neighbourhood of any vertex. This is best possible up to the constant factor in the O(â) term. We also provide an efficient algorithm to produce such a colouring. |
@inproceedings{MoRe09,
sorte = "conf-int",
author = {M. Molloy and B. A. Reed},
title = {Asymptotically optimal frugal colouring},
booktitle = {Proceedings of Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)},
year = {2009},
pages = {106-114},
x-pays = {CA},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
abstract = {We prove that every graph with maximum degree \Delta can be properly (\Delta + 1)-coloured so that no colour appears more than O(log \Delta / log log \Delta) times in the neighbourhood of any vertex. This is best possible up to the constant factor in the O(â) term. We also provide an efficient algorithm to produce such a colouring.},
pdf = {http://www.siam.org/proceedings/soda/2009/SODA09_012_molloym.pdf},
url ={http://portal.acm.org/citation.cfm?id=1496782}
}
-
N. Nisse,
I. Rapaport,
and K. Suchan.
Distributed computing of efficient routing schemes in generalized chordal graphs.
In Proceedings of the 16th International Colloquium on Structural Information and Communication Complexity (SIROCCO),
volume 5869 of Lecture Notes in Computer Science,
Piran, Slovenia,
pages 252-265,
2009.
Springer-Verlag.
[PDF
]
| Abstract: |
|
Efficient algorithms for computing routing tables should take advantage of the particular properties arising in large scale networks. There are in fact at least two properties that any routing scheme must consider: low (logarithmic) diameter and high clustering coefficient. High clustering coefficient implies the existence of few large induced cycles. Therefore, we propose a routing scheme that computes short routes in the class of k-chordal graphs, i.e., graphs with no chordless cycles of length more than k. We study the tradeoff between the length of routes and the time complexity for computing them. In the class of k-chordal graphs, our routing scheme achieves an additive stretch of at most k â 1, i.e., for all pairs of nodes, the length of the route never exceeds their distance plus k â 1. In order to compute the routing tables of any n-node graph with diameter D we propose a distributed algorithm which uses O(log n)-bit messages and takes O(D) time. We then propose a slightly modified version of the algorithm for computing routing tables in time O(min{âÂÂD, n}), where â is the the maximum degree of the graph. Using these tables, our routing scheme achieves a better additive stretch of 1 in chordal graphs (notice that chordal graphs are 3-chordal graphs). The routing scheme uses addresses of size log n bits and local memory of size 2(d â 1) log n bits in a node of degree d. |
@inproceedings{NRS09,
sorte = "conf-int",
author = {N. Nisse and I. Rapaport and K. Suchan},
title = {Distributed computing of efficient routing schemes in generalized chordal graphs},
booktitle = {Proceedings of the 16th International Colloquium on Structural Information and Communication Complexity (SIROCCO)},
publisher= { Springer-Verlag },
series= {Lecture Notes in Computer Science},
address= {Piran, Slovenia},
volume= {5869},
pages = {252-265},
year= {2009},
x-pays = {CL},
PDF={http://www-sop.inria.fr/members/Nicolas.Nisse/publications/distribRouting.pdf},
abstract={Efficient algorithms for computing routing tables should take advantage of the particular properties arising in large scale networks. There are in fact at least two properties that any routing scheme must consider: low (logarithmic) diameter and high clustering coefficient. High clustering coefficient implies the existence of few large induced cycles. Therefore, we propose a routing scheme that computes short routes in the class of k-chordal graphs, i.e., graphs with no chordless cycles of length more than k. We study the tradeoff between the length of routes and the time complexity for computing them. In the class of k-chordal graphs, our routing scheme achieves an additive stretch of at most k â 1, i.e., for all pairs of nodes, the length of the route never exceeds their distance plus k â 1. In order to compute the routing tables of any n-node graph with diameter D we propose a distributed algorithm which uses O(log n)-bit messages and takes O(D) time. We then propose a slightly modified version of the algorithm for computing routing tables in time O(min{âÂÂD, n}), where â is the the maximum degree of the graph. Using these tables, our routing scheme achieves a better additive stretch of 1 in chordal graphs (notice that chordal graphs are 3-chordal graphs). The routing scheme uses addresses of size log n bits and local memory of size 2(d â 1) log n bits in a node of degree d.},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
}
-
J. Ribault and O. Dalle.
OSA : A Federative Simulation Platform.
In Proceedings of the Winter Simulation Conference (WSC'09),
Austin, TX, USA,
2009.
Note: Ph.D. Colloquium.
[WWW
]
| Abstract: |
|
{OSA} ({O}pen {S}imulation {A}rchitecture) is a collaborative platform for component-based discrete-event simulation. {I}t has been created to support both {M}\&{S} studies and research on {M}\&{S} techniques and methodology. {T}he {OSA} project started from the observation that despite no single simulation software seems to be perfect, most of the elements required to make a perfect simulator already exist as part of existing simulators. {H}ence, the particular area of research that motivated the {OSA} project is to investigate practical means of reusing and combining any valuable piece of {M}\&{S} software at large, including models, simulation engines and algorithms, and supporting tools for the {M}\&{S} methodology. {T}o achieve this goal, the {OSA} project investigates in advanced software engineering techniques such as component-based framework, layered patterns and aspect-oriented programming. {I}n cases studies, the {OSA} project is among others involved in a large-scale simulation, and a distributed simulation over the {REST}ful protocol. |
@inproceedings{RiDa09,
title = { {OSA} : {A} {F}ederative {S}imulation {P}latform},
author = {Ribault, J. and Dalle, O.},
abstract = {{OSA} ({O}pen {S}imulation {A}rchitecture) is a collaborative platform for component-based discrete-event simulation. {I}t has been created to support both {M}\&{S} studies and research on {M}\&{S} techniques and methodology. {T}he {OSA} project started from the observation that despite no single simulation software seems to be perfect, most of the elements required to make a perfect simulator already exist as part of existing simulators. {H}ence, the particular area of research that motivated the {OSA} project is to investigate practical means of reusing and combining any valuable piece of {M}\&{S} software at large, including models, simulation engines and algorithms, and supporting tools for the {M}\&{S} methodology. {T}o achieve this goal, the {OSA} project investigates in advanced software engineering techniques such as component-based framework, layered patterns and aspect-oriented programming. {I}n cases studies, the {OSA} project is among others involved in a large-scale simulation, and a distributed simulation over the {REST}ful protocol.},
language = {{A}nglais},
affiliation = {{MASCOTTE} - {INRIA} {S}ophia {A}ntipolis / {L}aboratoire {I}3{S} - {INRIA} - {U}niversit{\'e} de {N}ice {S}ophia-{A}ntipolis - {CNRS} : {UMR}6070 },
booktitle = {{P}roceedings of the {W}inter {S}imulation {C}onference ({WSC}'09) },
address = {{A}ustin, TX, USA },
note = {{P}h.{D}. {C}olloquium },
audience = {internationale },
year = {2009},
URL = {http://hal.inria.fr/inria-00449642/en/},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
x-pays = {},
sorte = "conf-int",
}
-
I. Sau and D. M. Thilikos.
On Self-Duality of Branchwidth in Graphs of Bounded Genus.
In 8th Cologne Twente Workshop on Graphs and Combinatorial Optimization (CTW),
Paris, France,
pages 19-22,
June 2009.
[PDF
]
| Abstract: |
|
A graph parameter is self-dual in some class of graphs embeddable in some surface if its value does not change in the dual graph more than a constant factor. Self-duality has been examined for several width-parameters, such as branchwidth in graphs in some surface. In this direction, we prove that ${\mathbf bw}(G^*) \leq 6\times {\mathbf bw}(G) +2g-4$ for any graph $G$ embedded in a surface of Euler genus $g$. |
@inproceedings{SaTh09b,
sorte = "conf-int",
author = {I. Sau and D. M. Thilikos},
title = {{On Self-Duality of Branchwidth in Graphs of Bounded Genus}},
booktitle = {8th Cologne Twente Workshop on Graphs and Combinatorial Optimization (CTW)},
year = {2009},
month = jun,
pages = {19-22},
address = {Paris, France},
abstract = {A graph parameter is self-dual in some class of graphs embeddable in some surface if its value does not change in the dual graph more than a constant factor. Self-duality has been examined for several width-parameters, such as branchwidth in graphs in some surface. In this direction, we prove that ${\mathbf bw}(G^*) \leq 6\times {\mathbf bw}(G) +2g-4$ for any graph $G$ embedded in a surface of Euler genus $g$.},
pdf = {ftp://ftp-sop.inria.fr/mascotte/Publications/SaTh09b.pdf},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
}
-
I. Sau and D. M. Thilikos.
Subexponential Parameterized Algorithms for Bounded-Degree Connected Subgraph Problems on Planar Graphs.
In DIMAP workshop on Algorithmic Graph Theory (AGT09),
volume 32 of Electronic Notes in Discrete Mathematics,
Warwick, UK,
pages 59-66,
March 2009.
Elsevier.
[PDF
]
| Abstract: |
|
We present subexponential parameterized algorithms on planar graphs for a family of problems that consist in, given a graph $G$, finding a connected subgraph $H$ with bounded maximum degree, while maximising the number of edges (or vertices) of $H$. These problems are natural generalisations of the \textsc{Longest Path} problem. Our approach uses bidimensionality theory to obtain combinatorial bounds, combined with dynamic programming techniques over a branch decomposition of the input graph. These techniques need to be able to keep track of the connected components of the partial solutions over the branch decomposition, and can be seen as an \emph{algorithmic tensor} that can be applied to a wide family of problems that deal with finding connected subgraphs under certain constraints. |
@InProceedings{SaTh09,
sorte = "conf-int",
author = {I. Sau and D. M. Thilikos},
title = {Subexponential Parameterized Algorithms for Bounded-Degree Connected Subgraph Problems on Planar Graphs},
booktitle = {DIMAP workshop on Algorithmic Graph Theory (AGT09)},
year = {2009},
volume = {32},
pages = {59-66},
series = {Electronic Notes in Discrete Mathematics},
address = {Warwick, UK},
month = mar,
publisher = {Elsevier},
abstract = {We present subexponential parameterized algorithms on planar graphs for a family of problems that consist in, given a graph $G$, finding a connected subgraph $H$ with bounded maximum degree, while maximising the number of edges (or vertices) of $H$. These problems are natural generalisations of the \textsc{Longest Path} problem. Our approach uses bidimensionality theory to obtain combinatorial bounds, combined with dynamic programming techniques over a branch decomposition of the input graph. These techniques need to be able to keep track of the connected components of the partial solutions over the branch decomposition, and can be seen as an \emph{algorithmic tensor} that can be applied to a wide family of problems that deal with finding connected subgraphs under certain constraints.},
pdf = {ftp://ftp-sop.inria.fr/mascotte/Publications/SaTh09.pdf},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
}
-
A. Silva,
P. Reyes,
and M. Debbah.
Congestion in Randomly Deployed Wireless Ad-Hoc and Sensor Networks.
In International Conference on Ultra Modern Telecommunications,
St. Petersburg, Russia,
pages 10p,
October 2009.
[WWW
] [PDF
]
Keywords:
Random Matrix Theory,
Random Graph Theory,
Wireless Ad-Hoc Networks,
Wireless Sensor Networks.
| Abstract: |
|
Congestion in wireless ad-hoc sensor networks not only causes packet loss and increases queueing delay, but also leads to unnecessary energy consumption. In these networks, two types of congestion can occur: node-level congestion, which is caused by buffer overflow in the node, or link-level congestion, when wireless channels are shared by several nodes arising in collisions. We study a measure of link-level congestion in static wireless ad-hoc and sensor networks randomly deployed over an area. The measure of congestion considered is the inverse of the greatest eigenvalue of the adjacency matrix of the random graph. This measure gives an approximation of the average quantity of wireless links of a certain length on the network. We review the results to find this measure in Bernoulli random graphs. We use tools from random graph and random matrix theory to extend this measure on Geometric random graphs. |
@INPROCEEDINGS{SRD09b,
sorte = "conf-int",
AUTHOR={A. Silva and P. Reyes and M. Debbah},
TITLE={Congestion in Randomly Deployed Wireless {Ad-Hoc} and Sensor Networks},
BOOKTITLE={International Conference on Ultra Modern Telecommunications},
ADDRESS={St. Petersburg, Russia},
pages = {10p},
MONTH=oct,
YEAR={2009},
KEYWORDS={Random Matrix Theory, Random Graph Theory, Wireless Ad-Hoc Networks, Wireless Sensor Networks},
url = {http://hal.inria.fr/inria-00417774/en},
pdf = {http://hal.inria.fr/docs/00/36/43/70/PDF/RR-6854.pdf},
ABSTRACT={Congestion in wireless ad-hoc sensor networks not only causes packet loss and increases queueing delay, but also leads to unnecessary energy consumption. In these networks, two types of congestion can occur: node-level congestion, which is caused by buffer overflow in the node, or link-level congestion, when wireless channels are shared by several nodes arising in collisions. We study a measure of link-level congestion in static wireless ad-hoc and sensor networks randomly deployed over an area. The measure of congestion considered is the inverse of the greatest eigenvalue of the adjacency matrix of the random graph. This measure gives an approximation of the average quantity of wireless links of a certain length on the network. We review the results to find this measure in Bernoulli random graphs. We use tools from random graph and random matrix theory to extend this measure on Geometric random graphs.},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
}
-
F. Solano Donado and J. Moulierac.
Routing in All-Optical Label Switched-based Networks with Small Label Spaces.
In 13th Conference on Optical Network Design and Modeling (ONDM),
Braunschweig, Germany,
pages 6p,
February 2009.
IFIP/IEEE.
[WWW
]
| Abstract: |
|
With the development of All-Optical Label Switching (AOLS) network, nodes are capable of forwarding labeled packets without performing Optical-Electrical-Optical (OEO) conversions, speeding up the forwarding. However, this new technology also brings new constraints and, consequently, new problems have to be adressed. We study in this paper the problem of routing a set of demands in such a network, considering that routers have limited label space, preventing from the usage of label swapping techniques. Label stripping is a solution that ensures forwarding, concerning these constraints, of all the paths at expenses of increasing the stack size and wasting bandwith. We propose an intermediate feasible solution that keeps the GMPLS stack size smaller than label stripping, in order to gain bandwidth resources. After proposing an heuristic for this problem, we present simulations that show the performance of our solution. |
@InProceedings{SoMo09,
sorte = "conf-int",
author = {F. {Solano Donado} and J. Moulierac},
title = {Routing in All-Optical Label Switched-based Networks with Small Label Spaces},
booktitle = {13th Conference on Optical Network Design and Modeling (ONDM)},
pages = {6p},
year = {2009},
x-pays = {PL,ES},
address = {Braunschweig, Germany},
month = feb,
publisher = {IFIP/IEEE},
url = {ftp://ftp-sop.inria.fr/mascotte/personnel/Joanna.Moulierac/pdf/solano09routing.pdf},
abstract = { With the development of All-Optical Label Switching (AOLS) network, nodes are capable of forwarding labeled packets without performing Optical-Electrical-Optical (OEO) conversions, speeding up the forwarding. However, this new technology also brings new constraints and, consequently, new problems have to be adressed. We study in this paper the problem of routing a set of demands in such a network, considering that routers have limited label space, preventing from the usage of label swapping techniques. Label stripping is a solution that ensures forwarding, concerning these constraints, of all the paths at expenses of increasing the stack size and wasting bandwith. We propose an intermediate feasible solution that keeps the GMPLS stack size smaller than label stripping, in order to gain bandwidth resources. After proposing an heuristic for this problem, we present simulations that show the performance of our solution.},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
}
-
J. Araujo,
N. Cohen,
F. Giroire,
and F. Havet.
Good edge-labelling of graphs.
Research Report 6934,
INRIA,
2009.
[WWW
] [PDF
]
Keywords:
graph theory,
complexity,
edge-labelling,
planar graphs,
matching-cut,
channel assignment.
| Abstract: |
|
A {\em good edge-labelling} of a graph ${G}$ is a labelling of its edges such that, for any ordered pair of vertices $(x,y)$, there do not exist two paths from $x$ to $y$ with increasing labels. {T}his notion was introduced in~\cite{{BCP}} to solve wavelength assignment problems for specific categories of graphs. {I}n this paper, we aim at characterizing the class of graphs that admit a good edge-labelling. {F}irst, we exhibit infinite families of graphs for which no such edge-labelling can be found. {W}e then show that deciding if a graph admits a good edge-labelling is {NP}-complete. {F}inally, we give large classes of graphs admitting a good edge-labelling: forests, ${C}_3$-free outerplanar graphs, planar graphs of girth at least 6, subcubic ${{C}_3,{K}_{2,3}}$-free graphs. |
@techreport{ACGH09b,
title={{G}ood edge-labelling of graphs},
author = {J. Araujo and N. Cohen and F. Giroire and F. Havet},
abstract={A {\em good edge-labelling} of a graph ${G}$ is a labelling of its edges such that, for any ordered pair of vertices $(x,y)$, there do not exist two paths from $x$ to $y$ with increasing labels. {T}his notion was introduced in~\cite{{BCP}} to solve wavelength assignment problems for specific categories of graphs. {I}n this paper, we aim at characterizing the class of graphs that admit a good edge-labelling. {F}irst, we exhibit infinite families of graphs for which no such edge-labelling can be found. {W}e then show that deciding if a graph admits a good edge-labelling is {NP}-complete. {F}inally, we give large classes of graphs admitting a good edge-labelling: forests, ${C}_3$-free outerplanar graphs, planar graphs of girth at least 6, subcubic ${{C}_3,{K}_{2,3}}$-free graphs.},
keywords={graph theory; complexity; edge-labelling; planar graphs; matching-cut; channel assignment},
type={Research Report},
institution={INRIA},
number={6934},
year={2009},
URL={http://hal.inria.fr/inria-00383343/en/},
pdf = {http://hal.inria.fr/docs/00/38/41/18/PDF/RR-6934.pdf},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
x-pays={BR},
sorte = "Rapports",
}
-
J-C. Bermond,
C.J. Colbourn,
L. Gionfriddo,
G. Quattrocchi,
and I. Sau.
Drop cost and wavelength optimal two-period grooming with ratio 4.
Technical report RR-7101,
INRIA,
November 2009.
[PDF
]
| Abstract: |
|
We study grooming for two-period optical networks, a variation of the traffic grooming problem for WDM ring networks introduced by Colbourn, Quattrocchi, and Syrotiuk. In the two-period grooming problem, during the first period of time, there is all-to-all uniform traffic among $n$ nodes, each request using $1/C$ of the bandwidth; and during the second period, there is all-to-all uniform traffic only among a subset $V$ of $v$ nodes, each request now being allowed to use $1/C'$ of the bandwidth, where $C' < C$. We determine the minimum drop cost (minimum number of ADMs) for any $n,v$ and $C=4$ and $C' \in \{1,2,3\}$. To do this, we use tools of graph decompositions. Indeed the two-period grooming problem corresponds to minimizing the total number of vertices in a partition of the edges of the complete graph $K_n$ into subgraphs, where each subgraph has at most $C$ edges and where furthermore it contains at most $C'$ edges of the complete graph on $v$ specified vertices. Subject to the condition that the two-period grooming has the least drop cost, the minimum number of wavelengths required is also determined in each case. |
@TechReport{BCG+09,
author = {J-C. Bermond and C.J. Colbourn and L. Gionfriddo and G. Quattrocchi and I. Sau},
title = {Drop cost and wavelength optimal two-period grooming with ratio 4},
institution = {INRIA},
year = {2009},
x-pays = {US,ES,IT},
number = {RR-7101},
month = nov,
pdf = {ftp://ftp-sop.inria.fr/mascotte/Publications/BCG+09.pdf},
abstract = {We study grooming for two-period optical networks, a variation of the traffic grooming problem for WDM ring networks introduced by Colbourn, Quattrocchi, and Syrotiuk. In the two-period grooming problem, during the first period of time, there is all-to-all uniform traffic among $n$ nodes, each request using $1/C$ of the bandwidth; and during the second period, there is all-to-all uniform traffic only among a subset $V$ of $v$ nodes, each request now being allowed to use $1/C'$ of the bandwidth, where $C' < C$. We determine the minimum drop cost (minimum number of ADMs) for any $n,v$ and $C=4$ and $C' \in \{1,2,3\}$. To do this, we use tools of graph decompositions. Indeed the two-period grooming problem corresponds to minimizing the total number of vertices in a partition of the edges of the complete graph $K_n$ into subgraphs, where each subgraph has at most $C$ edges and where furthermore it contains at most $C'$ edges of the complete graph on $v$ specified vertices. Subject to the condition that the two-period grooming has the least drop cost, the minimum number of wavelengths required is also determined in each case.},
sorte = "Rapports",
}
-
J-C. Bermond,
M. Cosnard,
and S. Pérennes.
Directed acyclic graphs with unique path property.
Technical report 6932,
INRIA,
May 2009.
[WWW
] [PDF
]
| Abstract: |
|
Let P be a family of dipaths of a DAG (Directed Acyclic Graph) G. The load of an arc is the number of dipaths containing this arc. Let Ï(G, P) be the maximum of the load of all the arcs and let w(G, P) be the minimum number of wavelengths (colors) needed to color the family of dipaths P in such a way that two dipaths with the same wavelength are arc-disjoint. There exist DAGs such that the ratio between w(G, P) and Ï(G, P) cannot be bounded. An internal cycle is an oriented cycle such that all the vertices have at least one prede- cessor and one successor in G (said otherwise every cycle contain neither a source nor a sink of G). We prove that, for any family of dipaths P, w(G, P) = Ï(G, P) if and only if G is without internal cycle. We also consider a new class of DAGs, which is of interest in itself, those for which there is at most one dipath from a vertex to another. We call these digraphs UPP-DAGs. For these UPP-DAGs we show that the load is equal to the maximum size of a clique of the conï¬ict graph. We prove that the ratio between w(G, P) and Ï(G, P) cannot be bounded (a result conjectured in an other article). For that we introduce âgood labelingsâ of the conï¬ict graph associated to G and P, namely labelings of the edges such that for any ordered pair of vertices (x, y) there do not exist two paths from x to y with increasing labels. |
@TechReport{BCP09a,
author = {J-C. Bermond and M. Cosnard and S. P\'erennes},
title = {Directed acyclic graphs with unique path property},
institution = {INRIA},
year = {2009},
OPTkey = {},
OPTtype = {},
number = {6932},
month = may,
abstract = { Let P be a family of dipaths of a DAG (Directed Acyclic Graph) G. The load of an arc is the number of dipaths containing this arc. Let Ï(G, P) be the maximum of the load of all the arcs and let w(G, P) be the minimum number of wavelengths (colors) needed to color the family of dipaths P in such a way that two dipaths with the same wavelength are arc-disjoint. There exist DAGs such that the ratio between w(G, P) and Ï(G, P) cannot be bounded. An internal cycle is an oriented cycle such that all the vertices have at least one prede- cessor and one successor in G (said otherwise every cycle contain neither a source nor a sink of G). We prove that, for any family of dipaths P, w(G, P) = Ï(G, P) if and only if G is without internal cycle. We also consider a new class of DAGs, which is of interest in itself, those for which there is at most one dipath from a vertex to another. We call these digraphs UPP-DAGs. For these UPP-DAGs we show that the load is equal to the maximum size of a clique of the conï¬ict graph. We prove that the ratio between w(G, P) and Ï(G, P) cannot be bounded (a result conjectured in an other article). For that we introduce âgood labelingsâ of the conï¬ict graph associated to G and P, namely labelings of the edges such that for any ordered pair of vertices (x, y) there do not exist two paths from x to y with increasing labels.},
url = {http://hal.inria.fr/index.php?halsid=m0tbsqjvcd9gauk3gfbnp872g3&view_this_doc=inria-00387085&version=1},
pdf = {http://hal.inria.fr/docs/00/38/70/85/PDF/upp0509.pdf},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
sorte = "Rapports",
}
-
J-C. Bermond,
D. Coudert,
J. Moulierac,
S. Perennes,
H. Rivano,
I. Sau,
and F. Solano Donado.
MPLS label stacking on the line network.
Technical report RR-6803,
INRIA,
January 2009.
[WWW
] [PDF
]
| Abstract: |
|
All-Optical Label Switching (AOLS) is a new technology that performs forwarding without any Optical-Electrical-Optical (OEO) conversions. In this report, we study the problem of routing a set of requests in AOLS networks with the aim of minimizing the number of labels required to ensure the forwarding. In order to spare the label space, we consider label stacking, allowing the configuration of tunnels. We study particularly this network design problem when the network is a line. We provide an exact algorithm for the case in which all the requests have a common source and present some approximation algorithms and heuristics when an arbitrary number of sources are distributed over the line. We contrast the performance of our proposed algorithms by simulations. |
@TechReport{BCM+09,
author = {J-C. Bermond and D. Coudert and J. Moulierac and S. Perennes and H. Rivano and I. Sau and F. {Solano Donado}},
title = {{MPLS} label stacking on the line network},
institution = {INRIA},
year = {2009},
x-pays = {PL,ES},
OPTkey = {},
OPTtype = {},
number = {RR-6803},
OPTaddress = {},
month = jan,
OPTnote = {},
OPTannote = {},
url = {http://hal.inria.fr/inria-00354267/},
pdf = {http://hal.inria.fr/docs/00/35/42/67/PDF/RR-6803.pdf},
abstract = {All-Optical Label Switching (AOLS) is a new technology that performs forwarding without any Optical-Electrical-Optical (OEO) conversions. In this report, we study the problem of routing a set of requests in AOLS networks with the aim of minimizing the number of labels required to ensure the forwarding. In order to spare the label space, we consider label stacking, allowing the configuration of tunnels. We study particularly this network design problem when the network is a line. We provide an exact algorithm for the case in which all the requests have a common source and present some approximation algorithms and heuristics when an arbitrary number of sources are distributed over the line. We contrast the performance of our proposed algorithms by simulations.},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
sorte = "Rapports",
}
-
J-C. Bermond,
D. Coudert,
J. Moulierac,
S. Perennes,
I. Sau,
and F. Solano Donado.
GMPLS Routing Strategies based on the Design of Hypergraph Layouts.
Technical report RR-6842,
INRIA,
February 2009.
[WWW
] [PDF
]
| Abstract: |
|
All-Optical Label Switching (AOLS) is a new technology that performs packet forwarding without any Optical-Electrical-Optical (OEO) conversions. In this paper, we study the problem of routing a set of requests in AOLS networks using GMPLS technology, with the aim of minimizing the number of labels required to ensure the forwarding. We first formalize the problem by associating to each routing strategy a logical hypergraph whose hyperedges are dipaths of the physical graph, called \emph{tunnels} in GMPLS terminology. Such a hypergraph is called a \emph{hypergraph layout}, to which we assign a cost function given by its physical length plus the total number of hops traveled by the traffic. Minimizing the cost of the design of an AOLS network can then be expressed as finding a minimum cost hypergraph layout. We prove hardness results for the problem, namely $C \log n$ hardness for directed networks and non-existence of \textsc{PTAS} for undirected networks, where $C$ is a a positive constant and $n$ is the number of nodes of the network. These hardness results hold even is the traffic instance is a partial broadcast. On the other hand, we provide an $\mathcal{O}(\log n)$-approximation algorithm to the problem for a general network. Finally, we focus on the case where the physical network is a path, providing a polynomial-time dynamic programming algorithm for a bounded number of sources, thus extending the algorithm of~\cite{BCM+09b} for a single source. |
@TechReport{BCM+09c,
author = {J-C. Bermond and D. Coudert and J. Moulierac and S. Perennes and I. Sau and F. {Solano Donado}},
title = {{GMPLS} Routing Strategies based on the Design of Hypergraph Layouts},
institution = {INRIA},
year = {2009},
OPTkey = {},
OPTtype = {},
number = {RR-6842},
OPTaddress = {},
month = feb,
OPTnote = {},
OPTannote = {},
url = {http://hal.inria.fr/inria-00360576/},
pdf = {http://hal.inria.fr/docs/00/36/05/76/PDF/RR-6842.pdf},
abstract = { All-Optical Label Switching (AOLS) is a new technology that performs packet forwarding without any Optical-Electrical-Optical (OEO) conversions. In this paper, we study the problem of routing a set of requests in AOLS networks using GMPLS technology, with the aim of minimizing the number of labels required to ensure the forwarding. We first formalize the problem by associating to each routing strategy a logical hypergraph whose hyperedges are dipaths of the physical graph, called \emph{tunnels} in GMPLS terminology. Such a hypergraph is called a \emph{hypergraph layout}, to which we assign a cost function given by its physical length plus the total number of hops traveled by the traffic. Minimizing the cost of the design of an AOLS network can then be expressed as finding a minimum cost hypergraph layout. We prove hardness results for the problem, namely $C \log n$ hardness for directed networks and non-existence of \textsc{PTAS} for undirected networks, where $C$ is a a positive constant and $n$ is the number of nodes of the network. These hardness results hold even is the traffic instance is a partial broadcast. On the other hand, we provide an $\mathcal{O}(\log n)$-approximation algorithm to the problem for a general network. Finally, we focus on the case where the physical network is a path, providing a polynomial-time dynamic programming algorithm for a bounded number of sources, thus extending the algorithm of~\cite{BCM+09b} for a single source. },
x-pays = {PL,ES},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
sorte = "Rapports",
}
-
J-C. Bermond,
D. Coudert,
J. Moulierac,
S. Perennes,
I. Sau,
and F. Solano Donado.
GMPLS Label Space Minimization through Hypergraph Layouts.
Research Report RR-7071,
INRIA,
October 2009.
[WWW
] [PDF
]
Keywords:
GMPLS,
optical networks,
label stacking,
hypergraph layout,
approximation algorithms,
dynamic programming..
| Abstract: |
|
{A}ll-{O}ptical {L}abel {S}witching ({AOLS}) is a new technology that performs packet forwarding without any optical-electrical-optical conversions. {I}n this report, we study the problem of routing a set of requests in {AOLS} networks using {GMPLS} technology, with the aim of minimizing the number of labels required to ensure the forwarding. {W}e first formalize the problem by associating to each routing strategy a logical hypergraph, called a hypergraph layout, whose hyperarcs are dipaths of the physical graph, called tunnels in {GMPLS} terminology. {W}e define a cost function for the hypergraph layout, depending on its total length plus its total hop count. {M}inimizing the cost of the design of an {AOLS} network can then be expressed as finding a minimum cost hypergraph layout. {W}e prove hardness results for the problem, namely for general directed networks we prove that it is {NP}-hard to find a {C} log n-approximation, where {C} is a positive constant and n is the number of nodes of the network. {F}or symmetric directed networks, we prove that the problem is {APX}-hard. {T}hese hardness results hold even if the traffic instance is a partial broadcast. {O}n the other hand, we provide approximation algorithms, in particular an {O}(log n)-approximation for symmetric directed networks. {F}inally, we focus on the case where the physical network is a directed path, providing a polynomial-time dynamic programming algorithm for a fixed number k of sources running in {O}(n^{k+2}) time. |
@techreport{BCM+09e,
title = { {GMPLS} {L}abel {S}pace {M}inimization through {H}ypergraph {L}ayouts},
author = {J-C. Bermond and D. Coudert and J. Moulierac and S. Perennes and I. Sau and F. {Solano Donado}},
x-pays = {PL,ES},
abstract = {{A}ll-{O}ptical {L}abel {S}witching ({AOLS}) is a new technology that performs packet forwarding without any optical-electrical-optical conversions. {I}n this report, we study the problem of routing a set of requests in {AOLS} networks using {GMPLS} technology, with the aim of minimizing the number of labels required to ensure the forwarding. {W}e first formalize the problem by associating to each routing strategy a logical hypergraph, called a hypergraph layout, whose hyperarcs are dipaths of the physical graph, called tunnels in {GMPLS} terminology. {W}e define a cost function for the hypergraph layout, depending on its total length plus its total hop count. {M}inimizing the cost of the design of an {AOLS} network can then be expressed as finding a minimum cost hypergraph layout. {W}e prove hardness results for the problem, namely for general directed networks we prove that it is {NP}-hard to find a {C} log n-approximation, where {C} is a positive constant and n is the number of nodes of the network. {F}or symmetric directed networks, we prove that the problem is {APX}-hard. {T}hese hardness results hold even if the traffic instance is a partial broadcast. {O}n the other hand, we provide approximation algorithms, in particular an {O}(log n)-approximation for symmetric directed networks. {F}inally, we focus on the case where the physical network is a directed path, providing a polynomial-time dynamic programming algorithm for a fixed number k of sources running in {O}(n^{k+2}) time.},
keywords = {{GMPLS}; optical networks; label stacking; hypergraph layout; approximation algorithms; dynamic programming.},
language = {{A}nglais},
affiliation = {{MASCOTTE} - {INRIA} {S}ophia {A}ntipolis / {L}aboratoire {I}3{S} - {INRIA} - {U}niversit{\'e} de {N}ice {S}ophia-{A}ntipolis - {CNRS} : {UMR}6070 - {I}nstitute of {T}elecommunications - {W}arsaw {U}niversity of {T}echnology },
type = {Research Report},
institution = {INRIA},
month = {oct},
year = {2009},
number = {RR-7071},
URL = {http://hal.archives-ouvertes.fr/inria-00426681/en/},
pdf = {ftp://ftp-sop.inria.fr/mascotte/personnel/Joanna.Moulierac/pdf/RR-7071.pdf},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
sorte = "Rapports",
}
-
J-C. Bermond,
D. Coudert,
and J. Peters.
Online Distributed Traffic Grooming on Path Networks.
Technical report RR-6833,
INRIA,
February 2009.
[WWW
] [PDF
]
| Abstract: |
|
The {\em grooming factor} $C$ of a WDM optical network is the number of connections that can share the bandwidth of each wavelength and the process of grouping the requests that will share each wavelength is called {\em traffic grooming}. The goal of traffic grooming is either to reduce the transmission cost by reducing the number of wavelengths or to reduce the hardware cost by reducing the number of Add-Drop Multiplexors (ADM). In this paper, we investigate traffic grooming for directed path networks with online connection requests and distributed routing algorithms. When connection requests are online, the {\em virtual topology} that results from the assignment of ADMs to wavelengths cannot be changed with each request. The design of efficient virtual topologies that minimize either the number of ADMs needed to satisfy any set of connection requests or the blocking of connection requests depends strongly on the routing algorithm. We show how to design the best possible virtual topologies, independently of the routing algorithm, when each node is equipped with the same number of ADMs, and we analyze the performance of distributed greedy routing algorithms. |
@TechReport{BCP09b,
author = {J-C. Bermond and D. Coudert and J. Peters},
title = {Online Distributed Traffic Grooming on Path Networks},
institution = {INRIA},
year = {2009},
OPTkey = {},
OPTtype = {},
number = {RR-6833},
OPTaddress = {},
month = feb,
OPTnote = {},
OPTannote = {},
url = {http://hal.inria.fr/inria-00359810/},
pdf = {http://hal.inria.fr/docs/00/35/98/10/PDF/RR-6833.pdf},
abstract = {The {\em grooming factor} $C$ of a WDM optical network is the number of connections that can share the bandwidth of each wavelength and the process of grouping the requests that will share each wavelength is called {\em traffic grooming}. The goal of traffic grooming is either to reduce the transmission cost by reducing the number of wavelengths or to reduce the hardware cost by reducing the number of Add-Drop Multiplexors (ADM). In this paper, we investigate traffic grooming for directed path networks with online connection requests and distributed routing algorithms. When connection requests are online, the {\em virtual topology} that results from the assignment of ADMs to wavelengths cannot be changed with each request. The design of efficient virtual topologies that minimize either the number of ADMs needed to satisfy any set of connection requests or the blocking of connection requests depends strongly on the routing algorithm. We show how to design the best possible virtual topologies, independently of the routing algorithm, when each node is equipped with the same number of ADMs, and we analyze the performance of distributed greedy routing algorithms.},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={no},
x-pays = {CA},
sorte = "Rapports",
}
-
J-C. Bermond,
X. Muñoz,
and I. Sau.
Traffic Grooming in Bidirectional WDM Ring Networks.
Technical report RR-7080,
INRIA,
October 2009.
[WWW
] [PDF
]
| Abstract: |
|
We study the minimization of ADMs (Add-Drop Multiplexers) in optical WDM bidirectional rings considering symmetric shortest path routing and all-to-all unitary requests. We precisely formulate the problem in terms of graph decompositions, and state a general lower bound for all the values of the grooming factor $C$ and $N$, the size of the ring. We first study exhaustively the cases $C=1$, $C = 2$, and $C=3$, providing improved lower bounds, optimal constructions for several infinite families, as well as asymptotically optimal constructions and approximations. We then study the case $C>3$, focusing specifically on the case $C = k(k+1)/2$ for some $k \geq 1$. We give optimal decompositions for several congruence classes of $N$ using the existence of some combinatorial designs. We conclude with a comparison of the cost functions in unidirectional and bidirectional WDM rings. |
@TechReport{BMS09,
sorte = "Rapports",
author = {J-C. Bermond and X. Mu{\~n}oz and I. Sau},
title = {{Traffic Grooming in Bidirectional WDM Ring Networks}},
institution = {INRIA},
year = {2009},
x-pays = {PL,ES},
OPTkey = {},
OPTtype = {},
number = {RR-7080},
OPTaddress = {},
month = oct,
OPTnote = {},
OPTannote = {},
url = {http://hal.inria.fr/inria-00429155/},
pdf = {http://hal.inria.fr/docs/00/42/91/55/PDF/RR-7080.pdf},
abstract = {We study the minimization of ADMs (Add-Drop Multiplexers) in optical WDM bidirectional rings considering symmetric shortest path routing and all-to-all unitary requests. We precisely formulate the problem in terms of graph decompositions, and state a general lower bound for all the values of the grooming factor $C$ and $N$, the size of the ring. We first study exhaustively the cases $C=1$, $C = 2$, and $C=3$, providing improved lower bounds, optimal constructions for several infinite families, as well as asymptotically optimal constructions and approximations. We then study the case $C>3$, focusing specifically on the case $C = k(k+1)/2$ for some $k \geq 1$. We give optimal decompositions for several congruence classes of $N$ using the existence of some combinatorial designs. We conclude with a comparison of the cost functions in unidirectional and bidirectional WDM rings.},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
}
-
J-C. Bermond,
N. Nisse,
P. Reyes,
and H. Rivano.
Fast Data Gathering in Radio Grid Networks.
Research Report RR-6851,
INRIA,
March 2009.
[WWW
] [PDF
]
| Abstract: |
|
The aim of this paper is to design efficient gathering algorithms (data collection) in a Base Station of a wireless multi hop grid network when interferences constraints are present. We suppose the time is slotted and that during one time slot (step) each node can transmit to one of its neighbor at most one data item. Each device is equipped with a half duplex interface; so a node cannot both receive and transmit simultaneously. During a step only non interfering transmissions can be done. In other words, the non interfering calls done during a step will form a matching. The aim is to minimize the number of steps needed to send all messages to the base station, a.k.a. makespan or completion time. The best known algorithm for grids was a multiplicative 1.5-approximation algorithm. In such topologies, we give a very simple +2 approximation algorithm and then a more involved +1 approximation algorithm. Moreover, our algorithms work when no buffering is allowed in intermediary nodes, i.e., when a node receives a message at some step, it must transmit it during the next step. |
@TechReport{BNRR09b,
author = {J-C. Bermond and N. Nisse and P. Reyes and H. Rivano},
title = {Fast Data Gathering in Radio Grid Networks},
institution = {INRIA},
type = {Research Report},
number = {RR-6851},
year = {2009},
month = mar,
url = {http://hal.inria.fr/inria-00363908},
pdf = {http://hal.inria.fr/docs/00/37/11/50/PDF/RR-6851.pdf},
abstract = {The aim of this paper is to design efficient gathering algorithms (data collection) in a Base Station of a wireless multi hop grid network when interferences constraints are present. We suppose the time is slotted and that during one time slot (step) each node can transmit to one of its neighbor at most one data item. Each device is equipped with a half duplex interface; so a node cannot both receive and transmit simultaneously. During a step only non interfering transmissions can be done. In other words, the non interfering calls done during a step will form a matching. The aim is to minimize the number of steps needed to send all messages to the base station, a.k.a. makespan or completion time. The best known algorithm for grids was a multiplicative 1.5-approximation algorithm. In such topologies, we give a very simple +2 approximation algorithm and then a more involved +1 approximation algorithm. Moreover, our algorithms work when no buffering is allowed in intermediary nodes, i.e., when a node receives a message at some step, it must transmit it during the next step.},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
sorte = "Rapports",
}
-
N. Cohen,
D. Coudert,
D. Mazauric,
N. Nepomuceno,
and N. Nisse.
Tradeoffs when optimizing Lightpaths Reconfiguration in WDM networks..
Technical report RR-7047,
INRIA,
September 2009.
[WWW
] [PDF
]
| Abstract: |
|
In this report, we study the problem of rerouting a set of lightpaths in WDM networks. The reconfiguration issue arises for instance when it is necessary to improve the usage of resources or when a maintenance operation is planned on a particular link of the network. In order to avoid service interruptions, old lightpaths should not be torn down before the new ones are set up. However, this may not be possible since establishing the new routes of lightpaths may require the release of resources previously seized by old routes. Then it could be important for the operator to minimize 1) the total number of temporarily disrupted lightpaths, and/or 2) the number of concurrent disrupted lightpaths. In this paper, we study the tradeoff between both these conflicting objectives. More precisely, we prove that there exist some instances for which minimizing one of these objectives arbitrarily impairs the quality of the solution for the other one. We show that such bad tradeoffs may happen even in the case of basic network topologies. On the other hand, we exhibit classes of instances where good tradeoffs can be achieved. Finally, we investigate instances from various networks through simulations. |
@TechReport{CCM+09,
author = {N. Cohen and D. Coudert and D. Mazauric and N. Nepomuceno and N. Nisse},
title = {Tradeoffs when optimizing Lightpaths Reconfiguration in WDM networks.},
institution = {INRIA},
year = {2009},
number = {RR-7047},
month = sep,
url = {http://hal.archives-ouvertes.fr/inria-00421140/fr/},
abstract = {In this report, we study the problem of rerouting a set of lightpaths in WDM networks. The reconfiguration issue arises for instance when it is necessary to improve the usage of resources or when a maintenance operation is planned on a particular link of the network. In order to avoid service interruptions, old lightpaths should not be torn down before the new ones are set up. However, this may not be possible since establishing the new routes of lightpaths may require the release of resources previously seized by old routes. Then it could be important for the operator to minimize 1) the total number of temporarily disrupted lightpaths, and/or 2) the number of concurrent disrupted lightpaths. In this paper, we study the tradeoff between both these conflicting objectives. More precisely, we prove that there exist some instances for which minimizing one of these objectives arbitrarily impairs the quality of the solution for the other one. We show that such bad tradeoffs may happen even in the case of basic network topologies. On the other hand, we exhibit classes of instances where good tradeoffs can be achieved. Finally, we investigate instances from various networks through simulations.},
pdf = {http://hal.archives-ouvertes.fr/docs/00/42/11/40/PDF/RR-7047.pdf},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
x-pays = {BR},
sorte = "Rapports",
}
-
N. Cohen and F. Havet.
Planar graphs with maximum degree $\Delta\geq 9$ are ($\Delta+1$)-edge-choosable -- short proof.
Research Report RR-7098,
November 2009.
[WWW
]
Keywords:
edge-colouring,
list colouring,
List Colouring Conjecture,
planar graphs.
| Abstract: |
|
{W}e give a short proof of the following theorem due to {B}orodin~\cite{{B}or90}. {E}very planar graph with maximum degree $\{D}elta\geq 9$ is $(\{D}elta+1)$-edge-choosable. |
@techreport{CoHa09,
title = { {P}lanar graphs with maximum degree $\Delta\geq 9$ are ($\Delta+1$)-edge-choosable -- short proof},
author = {N. Cohen and F. Havet},
abstract = {{W}e give a short proof of the following theorem due to {B}orodin~\cite{{B}or90}. {E}very planar graph with maximum degree $\{D}elta\geq 9$ is $(\{D}elta+1)$-edge-choosable.},
keywords = {edge-colouring, list colouring, {L}ist {C}olouring {C}onjecture, planar graphs},
language = {{E}nglish},
affiliation = {{MASCOTTE} - {INRIA} {S}ophia {A}ntipolis / {L}aboratoire {I}3{S} - {INRIA} - {U}niversit{\'e} de {N}ice {S}ophia-{A}ntipolis - {CNRS} : {UMR}6070 },
type = {Research Report},
URL = {http://hal.archives-ouvertes.fr/inria-00432389/en/},
month = {nov},
year = {2009},
number = {RR-7098},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
sorte = "Rapports",
}
-
N. Cohen,
F. Havet,
and T. Müller.
Acyclic edge-colouring of planar graphs.
Research Report 6876,
INRIA,
March 2009.
[WWW
] [PDF
]
| Abstract: |
|
A proper edge-colouring with the property that every cycle contains edges of at least three distinct colours is called an {\it acyclic edge-colouring}. The {\it acyclic chromatic index} of a graph $G$, denoted $\chi'_a(G)$ is the minimum $k$ such that $G$ admits an {\it acyclic edge-colouring} with $k$ colours. We conjecture that if $G$ is planar and $\Delta(G)$ is large enough then $\chi'_a(G)=\Delta(G)$. We settle this conjecture for planar graphs with girth at least $5$ and outerplanar graphs. We also show that $\chi'_a(G)\leq \Delta(G) + 25$ for all planar graph $G$, which improves a previous result by Muthu et al. |
@TechReport{CHM09,
author = {N. Cohen and F. Havet and T. M{\"u}ller},
title = {Acyclic edge-colouring of planar graphs },
year = {2009},
month = mar,
institution = {INRIA},
number = {6876},
type = {Research Report},
abstract = {A proper edge-colouring with the property that every cycle contains edges of at least three distinct colours is called an {\it acyclic edge-colouring}. The {\it acyclic chromatic index} of a graph $G$, denoted $\chi'_a(G)$ is the minimum $k$ such that $G$ admits an {\it acyclic edge-colouring} with $k$ colours. We conjecture that if $G$ is planar and $\Delta(G)$ is large enough then $\chi'_a(G)=\Delta(G)$. We settle this conjecture for planar graphs with girth at least $5$ and outerplanar graphs. We also show that $\chi'_a(G)\leq \Delta(G) + 25$ for all planar graph $G$, which improves a previous result by Muthu et al.},
URL={http://hal.inria.fr/inria-00367394/fr/},
PDF = {http://hal.inria.fr/docs/00/36/73/94/PDF/RR-6876.pdf},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
x-pays = {IL},
sorte = "Rapports",
}
-
D. Coudert,
F. Giroire,
and I. Sau.
Circuit visiting 10 ordered vertices in infinite grids.
Technical report RR-6910,
INRIA,
2009.
[WWW
] [PDF
]
| Abstract: |
|
A \emph{circuit} in a simple undirected graph $G=(V,E)$ is a sequence of vertices ${v_1,v_2,\ldots,v_{k+1}}$ such that $v_1=v_{k+1}$ and ${v_i,v_{i+i}} \in E$ for $i=1,\ldots,k$. A circuit $C$ is said to be \emph{edge-simple} if no edge of $G$ is used twice in $C$. In this article we study the following problem: which is the largest integer $k$ such that, given any subset of $k$ ordered vertices of an infinite square grid, there exists an edge-simple circuit visiting the $k$ vertices in the prescribed order? We prove that $k=10$. To this end, we first provide a counterexample implying that $k<11$. To show that $k\geq 10$, we introduce a methodology, based on the notion of core graph, to reduce drastically the number of possible vertex configurations, and then we test each one of the resulting configurations with an \textsc{ILP} solver. |
@TechReport{CGS09,
author = {D. Coudert and F. Giroire and I. Sau},
title = {Circuit visiting 10 ordered vertices in infinite grids},
institution = {INRIA},
year = {2009},
OPTkey = {},
OPTtype = {},
number = {RR-6910},
OPTaddress = {},
OPTmonth = {},
OPTnote = {},
OPTannote = {},
url = {http://hal.inria.fr/inria-00378586},
pdf = {http://hal.inria.fr/docs/00/37/85/86/PDF/RR-6910.pdf},
abstract = { A \emph{circuit} in a simple undirected graph $G=(V,E)$ is a sequence of vertices ${v_1,v_2,\ldots,v_{k+1}}$ such that $v_1=v_{k+1}$ and ${v_i,v_{i+i}} \in E$ for $i=1,\ldots,k$. A circuit $C$ is said to be \emph{edge-simple} if no edge of $G$ is used twice in $C$. In this article we study the following problem: which is the largest integer $k$ such that, given any subset of $k$ ordered vertices of an infinite square grid, there exists an edge-simple circuit visiting the $k$ vertices in the prescribed order? We prove that $k=10$. To this end, we first provide a counterexample implying that $k<11$. To show that $k\geq 10$, we introduce a methodology, based on the notion of core graph, to reduce drastically the number of possible vertex configurations, and then we test each one of the resulting configurations with an \textsc{ILP} solver. },
OPTx-editorial-board={yes},
OPTx-proceedings={no},
OPTx-international-audience={yes},
sorte = "Rapports",
}
-
D. Coudert,
D. Mazauric,
and N. Nisse.
Routing Reconfiguration/Process Number: Networks with Shared Bandwidth..
Technical report RR-6790,
INRIA,
January 2009.
[WWW
] [PDF
]
| Abstract: |
|
In this paper, we address the problem of scheduling the switching of a set of connection requests one after the other from current routing to another pre-determined routing. We propose a model that handles requests using only a constant fraction of the bandwidth of a link, thus generalizing the model proposed in~\cite{CoSe07,JoSo03} for WDM networks. Our main result is the proof that the problem of deciding whether it exists a scheduling of the rerouting of connection requests without traffic interruption is NP-complete even if requests use the third of the bandwidth of a link. Note that the problem is polynomial when the bandwidth of a link cannot be shared~\cite{CoSe07} |
@TechReport{CMN09,
author = {D. Coudert and D. Mazauric and N. Nisse},
title = {Routing Reconfiguration/Process Number: Networks with Shared Bandwidth.},
institution = {INRIA},
year = {2009},
OPTkey = {},
OPTtype = {},
number = {RR-6790},
OPTaddress = {},
month = jan,
OPTnote = {},
OPTannote = {},
url = {http://hal.inria.fr/inria-00350025/},
abstract = {In this paper, we address the problem of scheduling the switching of a set of connection requests one after the other from current routing to another pre-determined routing. We propose a model that handles requests using only a constant fraction of the bandwidth of a link, thus generalizing the model proposed in~\cite{CoSe07,JoSo03} for WDM networks. Our main result is the proof that the problem of deciding whether it exists a scheduling of the rerouting of connection requests without traffic interruption is NP-complete even if requests use the third of the bandwidth of a link. Note that the problem is polynomial when the bandwidth of a link cannot be shared~\cite{CoSe07}},
pdf = {http://hal.inria.fr/docs/00/35/00/25/PDF/RR-6790.pdf},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
sorte = "Rapports",
}
-
N. Eggemann,
F. Havet,
and S. Noble.
$k$-$L(2,1)$-Labelling for Planar Graphs is NP-Complete for $k\geq 4$.
Research Report 6840,
INRIA,
February 2009.
[WWW
] [PDF
]
| Abstract: |
|
A mapping from the vertex set of a graph $G=(V,E)$ into an interval of integers $0, \dots ,k$ is an $L(2,1)$-labelling of $G$ of span $k$ if any two adjacent vertices are mapped onto integers that are at least 2 apart, and every two vertices with a common neighbour are mapped onto distinct integers. It is known that for any fixed $k\ge 4$, deciding the existence of such a labelling is an NP-complete problem while it is polynomial for $k\leq 3$. For even $k\geq 8$, it remains NP-complete when restricted to planar graphs. In this paper, we show that it remains NP-complete for any $k \ge 4$ by reduction from Planar Cubic Two-Colourable Perfect Matching. Schaefer stated without proof that Planar Cubic Two-Colourable Perfect Matching is NP-complete. In this paper we give a proof of this. |
@TechReport{EHN09,
sorte = "Rapports",
author = {N. Eggemann and F. Havet and S. Noble},
title = {$k$-$L(2,1)$-Labelling for Planar Graphs is {NP}-Complete for $k\geq 4$},
year = {2009},
month = feb,
institution = {INRIA},
number = {6840},
type = {Research Report},
abstract = {A mapping from the vertex set of a graph $G=(V,E)$ into an interval of integers $0, \dots ,k$ is an $L(2,1)$-labelling of $G$ of span $k$ if any two adjacent vertices are mapped onto integers that are at least 2 apart, and every two vertices with a common neighbour are mapped onto distinct integers. It is known that for any fixed $k\ge 4$, deciding the existence of such a labelling is an NP-complete problem while it is polynomial for $k\leq 3$. For even $k\geq 8$, it remains NP-complete when restricted to planar graphs. In this paper, we show that it remains NP-complete for any $k \ge 4$ by reduction from Planar Cubic Two-Colourable Perfect Matching. Schaefer stated without proof that Planar Cubic Two-Colourable Perfect Matching is NP-complete. In this paper we give a proof of this. },
URL={http://hal.inria.fr/inria-00360505/fr/},
PDF = {http://hal.inria.fr/docs/00/36/05/05/PDF/RR-6840.pdf},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
x-pays = {UK}
}
-
R. Erman,
F. Havet,
B. Lidicky,
and O. Pangrác.
5-colouring graphs with 4 crossings.
Research Report 7110,
INRIA,
November 2009.
| Abstract: |
|
We disprove a conjecture of Oporowski and Zhao stating that every graph with crossing number at most 5 and clique number at most 5 is 5-colourable. However, we show that every graph with crossing number at most 4 and clique number at most 5 is 5-colourable. We also show some colourability results on graphs that can be made planar by removing few edges. In particular, we show that if there exists three edges whose removal leaves the graph planar then it is $5$-colourable. |
@TechReport{EHL+09,
sorte = "Rapports",
author = {R. Erman and F. Havet and B. Lidicky and O. Pangr\'ac},
title = {5-colouring graphs with 4 crossings},
year = {2009},
month = {nov},
institution = {INRIA},
number = {7110},
type = {Research Report},
abstract = {We disprove a conjecture of Oporowski and Zhao stating that every graph with crossing number at most 5 and clique number at most 5 is 5-colourable. However, we show that every graph with crossing number at most 4 and clique number at most 5 is 5-colourable. We also show some colourability results on graphs that can be made planar by removing few edges. In particular, we show that if there exists three edges whose removal leaves the graph planar then it is $5$-colourable.},
x-editorial-board={yes},
x-proceedings={yes},
x-international-audience={yes},
x-pays={CZ,SI},
}
-
F. Giroire,
J. Monteiro,
and S. Pérennes.
P2P Storage Systems: How Much Locality Can They Tolerate?.
Research Report RR-7006,
INRIA,
July 2009.
[WWW
] [PDF
]
Keywords:
P2P storage system,
data placement,
performance evaluation,
data durability.
| Abstract: |
|
{L}arge scale peer-to-peer systems are foreseen as a way to provide highly reliable data storage at low cost. {T}o achieve high durability, such {P}2{P} systems encode the user data in a set of redundant fragments and distribute them among the peers. {W}e study here the impact of different data placement strategies on the system performance when using erasure codes redundancy schemes. {S}everal practical factors (easier control, software reuse, latency) tend to favor data placement strategies that preserve some degree of locality. {I}n this paper, we compare three policies: two of them local, in which the data are stored in logical neighbors, and the other one global, in which the data are spread randomly in the whole system. {W}e focus on the study of the probability to lose a data block and the bandwidth consumption to maintain such redundancy. {W}e use simulations to show that, without resource constraints, the average values are the same no matter which placement policy is used. {H}owever, the variations in the use of bandwidth are much more bursty under the local policies. {W}hen the bandwidth is limited, these bursty variations induce longer maintenance time and henceforth a higher risk of data loss. {W}e then show that a suitable degree of locality could be introduced in order to combine the efficiency of the global policy with the practical advantages of a local placement. {F}inally, we propose a new external reconstruction strategy that greatly improves the performance of local placement strategies. |
@TECHREPORT{GMP09,
author = {F. Giroire and J. Monteiro and S. P\'erennes},
title = {{P2P} Storage Systems: How Much Locality Can They Tolerate?},
institution = {INRIA},
year = {2009},
type = {Research Report},
number = {{RR}-7006},
month = jul,
abstract = {{L}arge scale peer-to-peer systems are foreseen as a way to provide highly reliable data storage at low cost. {T}o achieve high durability, such {P}2{P} systems encode the user data in a set of redundant fragments and distribute them among the peers. {W}e study here the impact of different data placement strategies on the system performance when using erasure codes redundancy schemes. {S}everal practical factors (easier control, software reuse, latency) tend to favor data placement strategies that preserve some degree of locality. {I}n this paper, we compare three policies: two of them local, in which the data are stored in logical neighbors, and the other one global, in which the data are spread randomly in the whole system. {W}e focus on the study of the probability to lose a data block and the bandwidth consumption to maintain such redundancy. {W}e use simulations to show that, without resource constraints, the average values are the same no matter which placement policy is used. {H}owever, the variations in the use of bandwidth are much more bursty under the local policies. {W}hen the bandwidth is limited, these bursty variations induce longer maintenance time and henceforth a higher risk of data loss. {W}e then show that a suitable degree of locality could be introduced in order to combine the efficiency of the global policy with the practical advantages of a local placement. {F}inally, we propose a new external reconstruction strategy that greatly improves the performance of local placement strategies.},
keywords = {P2P storage system, data placement, performance evaluation, data durability},
pages = {20 },
url = {http://hal.inria.fr/inria-00408078/en/},
pdf = {http://hal.inria.fr/docs/00/40/80/78/PDF/RR-7006.pdf},
x-pays = {},
sorte = "Rapports",
}
-
F. Havet,
S. Jendrol',
R. Soták,
and E. Skrabul'aková.
Facial non-repetitive edge-colouring of plane graphs.
Research Report 6873,
INRIA,
February 2009.
[WWW
] [PDF
]
| Abstract: |
|
A sequence $r_1,r_2,\dots,r_{2n}$ such that $r_i=r_{n+i}$ for all $1\leq i \leq n$, is called a {\em repetition}. A sequence $S$ is called {\em non-repetitive} if no {\it block} (i.e. subsequence of consecutive terms of $S$) is a repetition. Let $G$ be a graph whose edges are coloured. A trail is called {\em non-repetitive} if the sequence of colours of its edges is non-repetitive. If $G$ is a plane graph, a {\em facial non-repetitive edge-colouring} of $G$ is an edge-colouring such that any {\it facial trail} (i.e. trail of consecutive edges on the boundary walk of a face) is non-repetitive. We denote $\pi'_f(G)$ the minimum number of colours of a facial non-repetitive edge-colouring of $G$. In this paper, we show that $\pi'_f(G)\leq 8$ for any plane graph $G$. We also get better upper bounds for $\pi'_f(G)$ in the cases when $G$ is a tree, a plane triangulation, a simple $3$-connected plane graph, a hamiltonian plane graph, an outerplanar graph or a Halin graph. The bound $4$ for trees is tight. |
@TechReport{HJS+09,
sorte = "Rapports",
author = {F. Havet and S. Jendrol' and R. Sot\'ak and E. \v{S}krabul'akov\'a},
title = {Facial non-repetitive edge-colouring of plane graphs},
year = {2009},
month = {feb},
institution = {INRIA},
number = {6873},
type = {Research Report},
abstract = {A sequence $r_1,r_2,\dots,r_{2n}$ such that $r_i=r_{n+i}$ for all $1\leq i \leq n$, is called a {\em repetition}. A sequence $S$ is called {\em non-repetitive} if no {\it block} (i.e. subsequence of consecutive terms of $S$) is a repetition. Let $G$ be a graph whose edges are coloured. A trail is called {\em non-repetitive} if the sequence of colours of its edges is non-repetitive. If $G$ is a plane graph, a {\em facial non-repetitive edge-colouring} of $G$ is an edge-colouring such that any {\it facial trail} (i.e. trail of consecutive edges on the boundary walk of a face) is non-repetitive. We denote $\pi'_f(G)$ the minimum number of colours of a facial non-repetitive edge-colouring of $G$. In this paper, we show that $\pi'_f(G)\leq 8$ for any plane graph $G$. We also get better upper bounds for $\pi'_f(G)$ in the cases when $G$ is a tree, a plane triangulation, a simple $3$-connected plane graph, a hamiltonian plane graph, an outerplanar graph or a Halin graph. The bound $4$ for trees is tight.},
URL={http://hal.inria.fr/inria-00366589/en/},
PDF = {http://hal.inria.fr/docs/00/36/65/89/PDF/RR-6873.pdf},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
x-pays = {SK},
}
-
L. Hogie,
D. Papadimitriou,
I. Tahiri,
and F. Majorczyk.
Simulating routing schemes on large-scale topologies.
Technical report RT-0371,
INRIA,
November 2009.
[WWW
] [PDF
]
| Abstract: |
|
The expansion of the Internet routing system results in a number of research challenges, in particular, the Border Gateway Protocol (BGP) starts to show its limits a.o. in terms of the number of routing table entries it can dynamically process and control. Dynamic routing protocols showing better scaling properties are thus under investigation. However, because deploying under-development routing protocols on the Internet is not practicable at a large-scale (due to the size of the Internet topology), simulation is an unavoidable step to validate the properties of a newly proposed routing scheme. Unfortunately, the simulation of inter-domain routing protocols over large networks (order of tens of thousands of nodes) poses real challenges due to the limited memory and computational power that computers impose. This paper presents the Dynamic Routing Model simulator \drmsim which addresses the specific problem of large-scale simulations of (inter-domain) routing models on large networks. The motivation for developing a new simulator lies in the limitation of existing simulation tools in terms of the number of nodes they can handle and in the models they propose. |
@TECHREPORT{Hog09,
sorte = "Rapports",
author = {L. Hogie and D. Papadimitriou and I. Tahiri and F. Majorczyk},
title = {Simulating routing schemes on large-scale topologies},
abstract = {The expansion of the Internet routing system results in a number of research challenges, in particular, the Border Gateway Protocol (BGP) starts to show its limits a.o. in terms of the number of routing table entries it can dynamically process and control. Dynamic routing protocols showing better scaling properties are thus under investigation. However, because deploying under-development routing protocols on the Internet is not practicable at a large-scale (due to the size of the Internet topology), simulation is an unavoidable step to validate the properties of a newly proposed routing scheme. Unfortunately, the simulation of inter-domain routing protocols over large networks (order of tens of thousands of nodes) poses real challenges due to the limited memory and computational power that computers impose. This paper presents the Dynamic Routing Model simulator \drmsim which addresses the specific problem of large-scale simulations of (inter-domain) routing models on large networks. The motivation for developing a new simulator lies in the limitation of existing simulation tools in terms of the number of nodes they can handle and in the models they propose. },
url = {http://hal.inria.fr/inria-00440114/},
pdf = {http://hal.inria.fr/docs/00/44/01/14/PDF/simulating_routing_schemes_on_large-scale_topologies.pdf},
institution = {INRIA},
year = {2009},
number = {RT-0371},
month = {nov},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
x-pays = {BE}
}
-
F. Huc,
C. Molle,
N. Nisse,
S. Perennes,
and H. Rivano.
Stability of a local greedy distributed routing algorithm.
Technical report RR-6871,
INRIA,
March 2009.
[WWW
] [PDF
]
| Abstract: |
|
In this work, we study the problem of routing packets between undifferentiated sources and sinks in a network modeled by a multigraph. We provide a distributed and local algorithm that transmits packets hop by hop in the network and study its behaviour. At each step, a node transmits its queued packets to its neighbours in order to optimize a local gradient. This protocol is thus greedy since it does not require to record the history about the past actions, and lazy since it only needs informations of the neighborhood. We prove that this protocol is however optimal in the sense that the number of packets stored in the network stays bounded as soon as the sources injects a flow that another method could have exhausted. We therefore reinforce a result from the literature that worked for differentiated suboptimal flows. |
@TechReport{HMN+09,
sorte = "Rapports",
author = {F. Huc and C. Molle and N. Nisse and S. Perennes and H. Rivano},
title = {Stability of a local greedy distributed routing algorithm},
institution = {INRIA},
year = {2009},
OPTkey = {},
OPTtype = {},
number = {RR-6871},
OPTaddress = {},
month = mar,
OPTnote = {},
OPTannote = {},
url = {http://hal.inria.fr/inria-00366441/},
pdf = {http://hal.inria.fr/docs/00/36/64/41/PDF/RR-6871.pdf},
abstract = {In this work, we study the problem of routing packets between undifferentiated sources and sinks in a network modeled by a multigraph. We provide a distributed and local algorithm that transmits packets hop by hop in the network and study its behaviour. At each step, a node transmits its queued packets to its neighbours in order to optimize a local gradient. This protocol is thus greedy since it does not require to record the history about the past actions, and lazy since it only needs informations of the neighborhood. We prove that this protocol is however optimal in the sense that the number of packets stored in the network stays bounded as soon as the sources injects a flow that another method could have exhausted. We therefore reinforce a result from the literature that worked for differentiated suboptimal flows.},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
}
-
J-C. Maureira Bravo,
D. Dujovne,
and O. Dalle.
Network Provisioning for High Speed Vehicles Moving along Predictable Routes - Part 1: Spiderman Handover.
Research Report RR-6850,
INRIA,
2009.
[WWW
]
| Abstract: |
|
{T}his report presents our on-going work on a new system designed to provide a continuous network connectivity to communicating devices located on-board a vehicle moving at âhigh speedâ with a predictable trajectory such as trains, subways or buses. {T}he devices on-board the vehicle form a sub-network called the âin-motion networkâ. {T}his system we propose is composed of two parts. {T}he mobile part, called {S}piderman {D}evice ({SD}), installed on the roof of the vehicle, and the fixed part is composed of multiples access points, called {W}ireless {S}witch {A}ccess {P}oints ({WS} {AP}s), installed along the predictable route of the vehicle. {T}o provide a continuous connectivity, we designed a new handover algorithm that relies on a two {IEEE}802.11 radio hardware placed in the {SD} device. {T}his dual-radio architecture allows to minimize or even hide the handover effects, achieving a seamless continuous data-link connection at high speeds, up-to 150 {K}m/h and possibly more. {T}he link between the {SD} and the {WS} {AP} forms a {L}ayer 2 {E}thernet {B}ridge, supporting any {L}ayer 3 protocol between the infrastructure network and the in-motion network. {T}his concept has been validated by simulations and is currently tested using a real prototype in order to assess the performances and practical feasibility of the system. |
@techreport{MDD09,
sorte = "Rapports",
title = { {N}etwork {P}rovisioning for {H}igh {S}peed {V}ehicles {M}oving along {P}redictable {R}outes - {P}art 1: {S}piderman {H}andover},
author = {J-C. {Maureira Bravo} and D. Dujovne and O. Dalle},
abstract = {{T}his report presents our on-going work on a new system designed to provide a continuous network connectivity to communicating devices located on-board a vehicle moving at âhigh speedâ with a predictable trajectory such as trains, subways or buses. {T}he devices on-board the vehicle form a sub-network called the âin-motion networkâ. {T}his system we propose is composed of two parts. {T}he mobile part, called {S}piderman {D}evice ({SD}), installed on the roof of the vehicle, and the fixed part is composed of multiples access points, called {W}ireless {S}witch {A}ccess {P}oints ({WS} {AP}s), installed along the predictable route of the vehicle. {T}o provide a continuous connectivity, we designed a new handover algorithm that relies on a two {IEEE}802.11 radio hardware placed in the {SD} device. {T}his dual-radio architecture allows to minimize or even hide the handover effects, achieving a seamless continuous data-link connection at high speeds, up-to 150 {K}m/h and possibly more. {T}he link between the {SD} and the {WS} {AP} forms a {L}ayer 2 {E}thernet {B}ridge, supporting any {L}ayer 3 protocol between the infrastructure network and the in-motion network. {T}his concept has been validated by simulations and is currently tested using a real prototype in order to assess the performances and practical feasibility of the system.},
language = {{A}nglais},
affiliation = {{MASCOTTE} - {INRIA} {S}ophia {A}ntipolis / {L}aboratoire {I}3{S} - {INRIA} - {U}niversit{\'e} de {N}ice {S}ophia-{A}ntipolis - {CNRS} : {UMR}6070 - {PLANETE} - {INRIA} {S}ophia {A}ntipolis / {INRIA} {R}h{\^o}ne-{A}lpes - {INRIA} },
type = {Research Report},
institution = {INRIA},
number = {{RR}-6850},
year = {2009},
URL = {http://hal.inria.fr/inria-00369419/en/},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
x-pays = {CL},
}
-
J. Rué,
I. Sau,
and D. M. Thilikos.
Dynamic Programming for Graphs on Surfaces.
Technical report RR-7166,
INRIA,
December 2009.
[PDF
]
| Abstract: |
|
We provide a framework for the design of $2^{\mathcal{O}(k)}\cdot n$ step dynamic programming algorithms for surface-embedded graphs on $n$ vertices of branchwidth at most $k$. Our technique applies to graph problems for which dynamic programming uses tables encoding set partitions. For general graphs, the best known algorithms for such problems run in $2^{\mathcal{O}(k\cdot \log k)}\cdot n$ steps. That way, we considerably extend the class of problems that can be solved by algorithms whose running times have a {\em single exponential dependence} on branchwidth, and improve the running time of several existing algorithms. Our approach is based on a new type of branch decomposition called {\em surface cut decomposition}, which generalizes sphere cut decompositions for planar graphs, and where dynamic programming should be applied for each particular problem. The construction of such a decomposition uses a new graph-topological tool called {\em polyhedral decomposition}. The main result is that if dynamic programming is applied on surface cut decompositions, then the time dependence on branchwidth is {\sl single exponential}. This fact is proved by a detailed analysis of how non-crossing partitions are arranged on surfaces with boundary and uses diverse techniques from topological graph theory and analytic combinatorics. |
@TechReport{RST09,
sorte = "Rapports",
author = {J. Ru\'e and I. Sau and D. M. Thilikos},
title = {{Dynamic Programming for Graphs on Surfaces}},
institution = {INRIA},
year = {2009},
number = {RR-7166},
month = dec,
abstract = {We provide a framework for the design of $2^{\mathcal{O}(k)}\cdot n$ step dynamic programming algorithms for surface-embedded graphs on $n$ vertices of branchwidth at most $k$. Our technique applies to graph problems for which dynamic programming uses tables encoding set partitions. For general graphs, the best known algorithms for such problems run in $2^{\mathcal{O}(k\cdot \log k)}\cdot n$ steps. That way, we considerably extend the class of problems that can be solved by algorithms whose running times have a {\em single exponential dependence} on branchwidth, and improve the running time of several existing algorithms. Our approach is based on a new type of branch decomposition called {\em surface cut decomposition}, which generalizes sphere cut decompositions for planar graphs, and where dynamic programming should be applied for each particular problem. The construction of such a decomposition uses a new graph-topological tool called {\em polyhedral decomposition}. The main result is that if dynamic programming is applied on surface cut decompositions, then the time dependence on branchwidth is {\sl single exponential}. This fact is proved by a detailed analysis of how non-crossing partitions are arranged on surfaces with boundary and uses diverse techniques from topological graph theory and analytic combinatorics.},
pdf = {ftp://ftp-sop.inria.fr/mascotte/Publications/RR-7166.pdf},
}
-
A. Silva,
P. Reyes,
and M. Debbah.
Congestion in Randomly Deployed Wireless Ad-Hoc and Sensor Networks.
Research Report RR-6854,
INRIA,
March 2009.
[WWW
] [PDF
]
| Abstract: |
|
Congestion in wireless ad-hoc and sensor networks not only causes packet loss, and increases queueing delay, but also leads to unnecessary energy consumption. In a wireless ad-hoc and sensor network, two types of congestion can occur: node-level congestion, which is caused by buffer overflow in the node, or link-level congestion, when wireless channels are shared by several nodes and collisions occur when multiple active nodes try to seize the channel at the same time. We study a measure of link-level congestion in a static wireless ad-hoc and sensor network randomly deployed over an area. The measure considered on this paper is the inverse of the greatest eigenvalue of the adjacency matrix of the random graph. This measure of congestion gives an approximation of the average quantity of wireless links of a certain length that a node have on the wireless ad-hoc and sensor network. We review the results to find this measure of congestion in a Bernoulli random graph and we use tools from random graph theory and random matrix theory to extend this measure of congestion on a Geometric random graph. |
@TechReport{SRD09a,
sorte = "Rapports",
author = {A. Silva and P. Reyes and M. Debbah},
title = {Congestion in Randomly Deployed Wireless Ad-Hoc and Sensor Networks},
institution = {INRIA},
type = {Research Report},
number = {RR-6854},
year = {2009},
month = mar,
url = {http://hal.inria.fr/inria-00364370},
pdf = {http://hal.inria.fr/docs/00/36/43/70/PDF/RR-6854.pdf},
abstract = {Congestion in wireless ad-hoc and sensor networks not only causes packet loss, and increases queueing delay, but also leads to unnecessary energy consumption. In a wireless ad-hoc and sensor network, two types of congestion can occur: node-level congestion, which is caused by buffer overflow in the node, or link-level congestion, when wireless channels are shared by several nodes and collisions occur when multiple active nodes try to seize the channel at the same time. We study a measure of link-level congestion in a static wireless ad-hoc and sensor network randomly deployed over an area. The measure considered on this paper is the inverse of the greatest eigenvalue of the adjacency matrix of the random graph. This measure of congestion gives an approximation of the average quantity of wireless links of a certain length that a node have on the wireless ad-hoc and sensor network. We review the results to find this measure of congestion in a Bernoulli random graph and we use tools from random graph theory and random matrix theory to extend this measure of congestion on a Geometric random graph.},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
}
