-
L. Addario-Berry and B. Reed.
Horizons of Combinatorics,
volume 17 of Bolyai Society Mathematical Studies,
chapter Ballot Theorems, Old and New,
pages 9-35.
Springer,
2008.
@InBook{AdRe08,
author = {L. {Addario-Berry} and B. Reed},
ALTeditor = {},
title = {Horizons of Combinatorics},
chapter = {Ballot Theorems, Old and New},
publisher = {Springer},
year = {2008},
OPTkey = {},
volume = {17},
OPTnumber = {},
series = {Bolyai Society Mathematical Studies},
OPTtype = {},
OPTaddress = {},
OPTedition = {},
OPTmonth = {},
pages = {9-35},
OPTnote = {},
OPTannote = {},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
sorte = "livres-chap",
}
-
N. Nepomuceno,
P.R. Pinheiro,
and A.L.V. Coelho.
A Hybrid Optimization Framework for Cutting and Packing Problems: Case Study on Constrained 2D Non-guillotine Cutting.
In Recent Advances in Evolutionary Computation for Combinatorial Optimization,
volume 153 of Studies in Computational Intelligence,
chapter 6,
pages 87-99.
Springer,
2008.
[WWW
] [PDF
]
| Abstract: |
|
This work presents a hybrid optimization framework for tackling cutting and packing problems, which is based upon a particular combination scheme between heuristic and exact methods. A metaheuristic engine works as a generator of reduced instances for the original optimization problem, which are formulated as mathematical programming models. These instances, in turn, are solved by an exact optimization technique (solver), and the performance measures accomplished by the respective models are interpreted as score (fitness) values by the metaheuristic, thus guiding its search process. As a means to assess the potentialities behind the novel approach, we provide an instantiation of the framework for dealing specifically with the constrained two-dimensional non-guillotine cutting problem. Computational experiments performed over standard benchmark problems are reported and discussed here, evidencing the effectiveness of the novel approach. |
@incollection{NPC08,
author = {N. Nepomuceno and P.R. Pinheiro and A.L.V. Coelho},
title = {A Hybrid Optimization Framework for Cutting and Packing Problems: Case Study on Constrained {2D} Non-guillotine Cutting},
booktitle = {Recent Advances in Evolutionary Computation for Combinatorial Optimization},
series = {Studies in Computational Intelligence},
volume = {153},
year = {2008},
pages = {87-99},
publisher = {Springer},
chapter = {6},
abstract = {This work presents a hybrid optimization framework for tackling cutting and packing problems, which is based upon a particular combination scheme between heuristic and exact methods. A metaheuristic engine works as a generator of reduced instances for the original optimization problem, which are formulated as mathematical programming models. These instances, in turn, are solved by an exact optimization technique (solver), and the performance measures accomplished by the respective models are interpreted as score (fitness) values by the metaheuristic, thus guiding its search process. As a means to assess the potentialities behind the novel approach, we provide an instantiation of the framework for dealing specifically with the constrained two-dimensional non-guillotine cutting problem. Computational experiments performed over standard benchmark problems are reported and discussed here, evidencing the effectiveness of the novel approach.},
url = {http://dx.doi.org/10.1007/978-3-540-70807-0_6},
pdf = {ftp://ftp-sop.inria.fr/mascotte/Publications/NPC08.pdf},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
x-pays = {BR},
sorte = "livres-chap",
}
-
L. Addario-Berry,
M. Chudnovsky,
F. Havet,
B. Reed,
and P. Seymour.
Bisimplicial vertices in even-hole-free graphs.
Journal of Combinatorial Theory Ser. B,
98(6):1119--1164,
2008.
[PDF
]
| Abstract: |
|
A hole in a graph is an induced subgraph which is a cycle of length at least four. A hole is called even if it has an even number of vertices. An even-hole-free graph is a graph with no even holes. A vertex of a graph is bisimplicial if the set of its neighbours is the union of two cliques. In this paper we prove that every even-hole-free graph has a bisimplicial vertex, which was originally conjectured by Reed. |
@ARTICLE{ACH+08,
AUTHOR={L. Addario-Berry and M. Chudnovsky and F. Havet and B. Reed and P. Seymour},
TITLE={Bisimplicial vertices in even-hole-free graphs},
JOURNAL = {Journal of Combinatorial Theory Ser. B},
VOLUME = {98},
NUMBER = {6},
YEAR = {2008},
PAGES = {1119--1164},
pdf = {ftp://ftp-sop.inria.fr/mascotte/Publications/ACH+08.pdf},
abstract = {A hole in a graph is an induced subgraph which is a cycle of length at least four. A hole is called even if it has an even number of vertices. An even-hole-free graph is a graph with no even holes. A vertex of a graph is bisimplicial if the set of its neighbours is the union of two cliques. In this paper we prove that every even-hole-free graph has a bisimplicial vertex, which was originally conjectured by Reed.},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
sorte = "rev-int",
}
-
L. Addario-Berry,
K. Dalal,
and B. Reed.
Degree-Constrained Subgraphs.
Discrete Applied Mathematics,
156:1168-1174,
2008.
@article{ADR08,
author = {L. {Addario-Berry} and K. Dalal and B. Reed},
title = {Degree-Constrained Subgraphs},
journal = {Discrete Applied Mathematics},
volume = {156},
year = {2008},
pages = {1168-1174},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
sorte = "rev-int",
}
-
N. Ben Ali,
B. Belghith,
J. Moulierac,
and M. Molnár.
QoS multicast aggregation under multiple additive constraints.
Computer Communications,
31(15):3564-3578,
September 2008.
[PDF
]
| Abstract: |
|
IP Multicast has been proposed in order to manage group communications over the Internet in a bandwidth efficient manner. Although such a proposition has been well studied, there are still some inherent problems for its widespread deployment. In this paper, we propose a new algorithm coined mQMA that deals with the two main problems of traditional IP multicast, i.e., multicast forwarding state scalability and multi-constrained QoS routing. The algorithm mQMA is a QoS multicast aggregation algorithm which handles multiple additive QoS constraints. It builds few trees and maintains few forwarding states for the groups thanks to the technique of multicast tree aggregation, which allows several groups to share the same delivery tree. Moreover, the algorithm mQMA builds trees satisfying multiple additive QoS constraints. We show via extensive simulations that mQMA reduces dramatically the number of trees to be maintained and reduces the utilization of the network resources, yet it leverages the same overall QoS performances as Mamcra which is the main known multi-constrained multicast routing algorithm. |
@Article{BBMM08,
author = {N. {Ben Ali} and B. Belghith and J. Moulierac and M. Moln\'ar},
title = {{QoS multicast aggregation under multiple additive constraints}},
journal = {Computer Communications},
year = {2008},
volume = {31},
number = {15},
pages = {3564-3578},
series= {Elsevier},
month = sep,
PDF={ftp://ftp-sop.inria.fr/mascotte/personnel/Joanna.Moulierac/pdf/benali08qos.pdf},
ABSTRACT={IP Multicast has been proposed in order to manage group communications over the Internet in a bandwidth efficient manner. Although such a proposition has been well studied, there are still some inherent problems for its widespread deployment. In this paper, we propose a new algorithm coined mQMA that deals with the two main problems of traditional IP multicast, i.e., multicast forwarding state scalability and multi-constrained QoS routing. The algorithm mQMA is a QoS multicast aggregation algorithm which handles multiple additive QoS constraints. It builds few trees and maintains few forwarding states for the groups thanks to the technique of multicast tree aggregation, which allows several groups to share the same delivery tree. Moreover, the algorithm mQMA builds trees satisfying multiple additive QoS constraints. We show via extensive simulations that mQMA reduces dramatically the number of trees to be maintained and reduces the utilization of the network resources, yet it leverages the same overall QoS performances as Mamcra which is the main known multi-constrained multicast routing algorithm.},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
sorte = "rev-int",
}
-
J-C. Bermond,
D. Coudert,
and B. Lévêque.
Approximations for All-to-all Uniform Traffic Grooming on Unidirectional Ring.
Journal of Interconnection Networks (JOIN),
9(4):471-486,
December 2008.
[WWW
] [PDF
]
| Abstract: |
|
Traffic grooming in a WDM network consists of assigning to each request (lightpath) a wavelength with the constraint that a given wavelength can carry at most C requests or equivalently a request uses at most 1/C of the bandwidth. C is known as the grooming ratio. A request (lightpath) need two SONET add-drop multiplexers (ADMs) at each end node~; using grooming different requests can share the same ADM. The so called traffic grooming problem consists of minimizing the total number of ADMs to be used (in order to reduce the overall cost of the network). Here we consider the traffic grooming problem in WDM unidirectional rings with all-to-all uniform unitary traffic. This problem has been optimally solved for specific values of the grooming ratio, namely C=2,3,4,5,6. In this paper we present various simple constructions for the grooming problem providing good approximation of the total number of ADMs. For that we use the fact that the problem corresponds to a partition of the edges of the complete graph into subgraphs, where each subgraph has at most C edges and where the total number of vertices has to be minimized. |
@Article{BCL08,
author = {J-C. Bermond and D. Coudert and B. L\'ev\^eque},
title = {Approximations for All-to-all Uniform Traffic Grooming on Unidirectional Ring},
journal = {Journal of Interconnection Networks (JOIN)},
year = {2008},
OPTkey = {},
volume = {9},
number = {4},
pages = {471-486},
month = dec,
OPTnote = {},
OPTannote = {},
abstract = {Traffic grooming in a WDM network consists of assigning to each request (lightpath) a wavelength with the constraint that a given wavelength can carry at most C requests or equivalently a request uses at most 1/C of the bandwidth. C is known as the grooming ratio. A request (lightpath) need two SONET add-drop multiplexers (ADMs) at each end node~; using grooming different requests can share the same ADM. The so called traffic grooming problem consists of minimizing the total number of ADMs to be used (in order to reduce the overall cost of the network). Here we consider the traffic grooming problem in WDM unidirectional rings with all-to-all uniform unitary traffic. This problem has been optimally solved for specific values of the grooming ratio, namely C=2,3,4,5,6. In this paper we present various simple constructions for the grooming problem providing good approximation of the total number of ADMs. For that we use the fact that the problem corresponds to a partition of the edges of the complete graph into subgraphs, where each subgraph has at most C edges and where the total number of vertices has to be minimized.},
pdf = {ftp://ftp-sop.inria.fr/mascotte/personnel/David.Coudert/Publication/BCL-JOIN08.pdf},
url = {http://dx.doi.org/10.1142/S0219265908002394},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
sorte = "rev-int",
}
-
L. Blin,
P. Fraigniaud,
N. Nisse,
and S. Vial.
Distributed chasing of network intruders.
Theoretical Computer Science,
399(1-2):12-37,
2008.
[WWW
] [PDF
]
| Abstract: |
|
Graph searching is one of the most popular tools for analyzing the chase for a powerful and hostile software agent (called the "intruder"), by a set of software agents (called the "searchers") in a network. The existing solutions for the graph searching problem suffer however from a serious drawback: they are mostly centralized and assume a global synchronization mechanism for the searchers. In particular: (1) the search strategy for every network is computed based on the knowledge of the entire topology of the network, and (2) the moves of the searchers are controlled by a centralized mechanism that decides at every step which searcher has to move, and what movement it has to perform. This paper addresses the graph searching problem in a distributed setting. We describe a distributed protocol that enables searchers with logarithmic size memory to clear any network, in a fully decentralized manner. The search strategy for the network in which the searchers are launched is computed online by the searchers themselves without knowing the topology of the network in advance. It performs in an asynchronous environment, i.e., it implements the necessary synchronization mechanism in a decentralized manner. In every network, our protocol performs a connected strategy using at most k+1 searchers, where k is the minimum number of searchers required to clear the network in a monotone connected way using a strategy computed in the centralized and synchronous setting. |
@article{BFNV08,
author = {L. Blin and P. Fraigniaud and N. Nisse and S. Vial},
title = {Distributed chasing of network intruders},
journal = {Theoretical Computer Science},
volume = {399},
number = {1-2},
year = {2008},
pages = {12-37},
abstract = {Graph searching is one of the most popular tools for analyzing the chase for a powerful and hostile software agent (called the "intruder"), by a set of software agents (called the "searchers") in a network. The existing solutions for the graph searching problem suffer however from a serious drawback: they are mostly centralized and assume a global synchronization mechanism for the searchers. In particular: (1) the search strategy for every network is computed based on the knowledge of the entire topology of the network, and (2) the moves of the searchers are controlled by a centralized mechanism that decides at every step which searcher has to move, and what movement it has to perform. This paper addresses the graph searching problem in a distributed setting. We describe a distributed protocol that enables searchers with logarithmic size memory to clear any network, in a fully decentralized manner. The search strategy for the network in which the searchers are launched is computed online by the searchers themselves without knowing the topology of the network in advance. It performs in an asynchronous environment, i.e., it implements the necessary synchronization mechanism in a decentralized manner. In every network, our protocol performs a connected strategy using at most k+1 searchers, where k is the minimum number of searchers required to clear the network in a monotone connected way using a strategy computed in the centralized and synchronous setting.},
url = {http://dx.doi.org/10.1016/j.tcs.2008.02.004},
pdf = {http://www-sop.inria.fr/members/Nicolas.Nisse/publications/Sirocco06VJ.ps},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
sorte = "rev-int",
}
-
M. Cerioli,
L. Faria,
T. Ferreira,
C. Martinhon,
F. Protti,
and B. Reed.
Partition into cliques for cubic graphs: Planar case, complexity and approximation.
Discrete Applied Mathematics,
156:2270-2278,
2008.
@article{CF+08,
author = {M. Cerioli and L. Faria and T. Ferreira and C. Martinhon and F. Protti and B. Reed},
title = {Partition into cliques for cubic graphs: Planar case, complexity and approximation},
journal = {Discrete Applied Mathematics},
volume = {156},
pages = {2270-2278},
year = {2008},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
sorte = "rev-int",
}
-
R. Chand,
M. Cosnard,
and L. Liquori.
Powerful resource discovery for Arigatoni overlay network.
Future Generation Computer Systems,
24:31--38,
2008.
[WWW
] [PDF
]
@Article{CCL07a,
author = {R. Chand and M. Cosnard and L. Liquori},
title = {{Powerful resource discovery for Arigatoni overlay network}},
journal = {Future Generation Computer Systems},
publisher = {Elsevier},
year = {2008},
volume = {24},
OPTnumero = {1},
pages = {31--38},
url={http://dx.doi.org/10.1016/j.future.2007.02.009e },
PDF = {http://www-sop.inria.fr/mascotte/Luigi.Liquori/PAPERS/fgcs-07.pdf},
sorte = "rev-int",
}
-
S. Fiorini,
N. Hardy,
B. Reed,
and A. Vetta.
Planar graph bipartization in linear time.
Discrete Applied Mathematics,
156:1175-1180,
2008.
| Abstract: |
|
For each constant k, we present a linear time algorithm that, given a planar graph G, either finds a minimum odd cycle vertex transversal in G or guarantees that there is no transversal of size at most k. |
@article{FHRV08,
author = {S. Fiorini and N. Hardy and B. Reed and A. Vetta},
title = {Planar graph bipartization in linear time},
journal = {Discrete Applied Mathematics},
volume = {156},
year = {2008},
pages = {1175-1180},
abstract = {For each constant k, we present a linear time algorithm that, given a planar graph G, either finds a minimum odd cycle vertex transversal in G or guarantees that there is no transversal of size at most k.},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
sorte = "rev-int",
}
-
M. Flammini,
R. Klasing,
A. Navarra,
and S. Pérennes.
Tightening the Upper Bound for the Minimum Energy Broadcasting problem.
Wireless Networks,
14(5):659--669,
October 2008.
Note: Special Issue associated to the 3rd International Symposium on Modelling and Optimization in Mobile, Ad Hoc and Wireless Networks (WiOpt 2005).
[WWW
]
@article{FKNP07b,
author={M. Flammini and R. Klasing and A. Navarra and S. P\'erennes},
title={Tightening the Upper Bound for the Minimum Energy Broadcasting problem},
year={2008},
month={October},
volume={14},
number={5},
pages={659--669},
journal={Wireless Networks},
note={Special Issue associated to the 3rd International Symposium on Modelling and Optimization in Mobile, Ad Hoc and Wireless Networks (WiOpt 2005)},
url = {http://www.springerlink.com/content/l4262574u4802253/},
sorte = "rev-int",
}
-
M. Flammini,
L. Moscardelli,
A. Navarra,
and S. Pérennes.
Asymptotically Optimal Solutions for Small World Graphs.
Theory of Computing Systems,
42(4):632-650,
May 2008.
[WWW
] [PDF
]
| Abstract: |
|
We consider the problem of determining constructions with an asymptotically optimal oblivious diameter in small world graphs under the Kleinbergâs model. In particular, we give the first general lower bound holding for any monotone distance distribution, that is induced by a monotone generating function. Namely, we prove that the expected oblivious diameter is Ω(logâ2 n) even on a path of n nodes. We then focus on deterministic constructions and after showing that the problem of minimizing the oblivious diameter is generally intractable, we give asymptotically optimal solutions, that is with a logarithmic oblivious diameter, for paths, trees and Cartesian products of graphs, including d-dimensional grids for any fixed value of d. |
@article{FMNP08,
author = "M. Flammini and L. Moscardelli and A. Navarra and S. P\'erennes",
title = {Asymptotically Optimal Solutions for Small World Graphs},
journal = "Theory of Computing Systems",
volume = {42},
number = {4},
pages = {632-650},
month = may,
year = {2008},
url = {http://www.springerlink.com/content/h42450h68063628g/},
pdf = {ftp://ftp-sop.inria.fr/mascotte/Publications/FNMP08.pdf},
abstract = {We consider the problem of determining constructions with an asymptotically optimal oblivious diameter in small world graphs under the Kleinbergâs model. In particular, we give the first general lower bound holding for any monotone distance distribution, that is induced by a monotone generating function. Namely, we prove that the expected oblivious diameter is Ω(logâ2 n) even on a path of n nodes. We then focus on deterministic constructions and after showing that the problem of minimizing the oblivious diameter is generally intractable, we give asymptotically optimal solutions, that is with a logarithmic oblivious diameter, for paths, trees and Cartesian products of graphs, including d-dimensional grids for any fixed value of d.},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
sorte = "rev-int",
}
-
N. Fountoulakis and B. Reed.
The evolution of the mixing rate of a simple random walk on the giant component of a random graph.
Random Structures and Algorithms,
33:68-86,
2008.
@article{FoRe08,
author = {N. Fountoulakis and B. Reed},
title = {The evolution of the mixing rate of a simple random walk on the giant component of a random graph},
journal = {Random Structures and Algorithms},
volume = {33},
year = {2008},
pages = {68-86},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
sorte = "rev-int",
}
-
P. Fraigniaud and N. Nisse.
Monotony Properties of Connected Visible Graph Searching.
Information and Computation,
206(12):1383-1393,
2008.
| Abstract: |
|
{Search games are attractive for their correspondence with classical width parameters. For instance, the \emph{invisible} search number (a.k.a. \emph{node} search number) of a graph is equal to its pathwidth plus~1, and the \emph{visible} search number of a graph is equal to its treewidth plus~1. The \emph{connected} variants of these games ask for search strategies that are connected, i.e., at every step of the strategy, the searched part of the graph induces a connected subgraph. We focus on \emph{monotone} search strategies, i.e., strategies for which every node is searched exactly once. The monotone connected visible search number of an $n$-node graph is at most $O(\log n)$ times its visible search number. First, we prove that this logarithmic bound is tight. Precisely, we prove that there is an infinite family of graphs for which the ratio monotone connected visible search number over visible search number is $\Omega(\log n)$. Second, we prove that, as opposed to the non-connected variant of visible graph searching, ``recontamination helps" for connected visible search. Precisely, we prove that, for any $k \geq 4$, there exists a graph with connected visible search number at most $k$, and monotone connected visible search number $>k$.}, url = {http://www.informatik.uni-trier.de/~ley/db/conf/wg/wg2006.shtml}, pdf = {http://www-sop.inria.fr/members/Nicolas.Nisse/publications/WG06_nisse.ps}, OPTx-editorial-board={yes}, OPTx-proceedings={yes}, OPTx-international-audience={yes}, sorte = "rev-int", |
@article{FrNi08,
author = {P. Fraigniaud and N. Nisse},
title = {Monotony Properties of Connected Visible Graph Searching},
journal = {Information and Computation},
volume = {206},
number = {12},
year = {2008},
pages = {1383-1393},
abstract = {Search games are attractive for their correspondence with classical width parameters. For instance, the \emph{invisible} search number (a.k.a. \emph{node} search number) of a graph is equal to its pathwidth plus~1, and the \emph{visible} search number of a graph is equal to its treewidth plus~1. The \emph{connected} variants of these games ask for search strategies that are connected, i.e., at every step of the strategy, the searched part of the graph induces a connected subgraph. We focus on \emph{monotone} search strategies, i.e., strategies for which every node is searched exactly once. The monotone connected visible search number of an $n$-node graph is at most $O(\log n)$ times its visible search number. First, we prove that this logarithmic bound is tight. Precisely, we prove that there is an infinite family of graphs for which the ratio monotone connected visible search number over visible search number is $\Omega(\log n)$. Second, we prove that, as opposed to the non-connected variant of visible graph searching, ``recontamination helps" for connected visible search. Precisely, we prove that, for any $k \geq 4$, there exists a graph with connected visible search number at most $k$, and monotone connected visible search number $>k$.}, url = {http://www.informatik.uni-trier.de/~ley/db/conf/wg/wg2006.shtml}, pdf = {http://www-sop.inria.fr/members/Nicolas.Nisse/publications/WG06_nisse.ps}, OPTx-editorial-board={yes}, OPTx-proceedings={yes}, OPTx-international-audience={yes}, sorte = "rev-int",
}
-
F. Havet,
J.-S. Sereni,
and R. Skrekovski.
3-facial colouring of plane graphs.
SIAM Journal on Discrete Mathematics,
22(1):231--247,
2008.
[WWW
] [PDF
]
| Abstract: |
|
A plane graph is \l-facially $k$-colourable if its vertices can be coloured with $k$ colours such that any two distinct vertices on a facial walk of length at most \l are coloured differently. We prove that every plane graph is $3$-facially $11$-colourable. As a consequence, we derive that every $2$-connected plane graph with maximum face-size at most $7$ is cyclically $11$-colourable. These two bounds are for one off from those that are proposed by the $(3\l+1)$-Conjecture and the Cyclic Conjecture. |
@article{HSS08,
author = {F. Havet and J.-S. Sereni and R. Skrekovski},
title = {3-facial colouring of plane graphs},
journal = {SIAM Journal on Discrete Mathematics},
volume={22},
number={1},
pages={231--247},
year = {2008},
URL={http://dx.doi.org/10.1137/060664124},
PDF = {http://kam.mff.cuni.cz/~sereni/Articles/HSS08.pdf},
abstract={A plane graph is \l-facially $k$-colourable if its vertices can be coloured with $k$ colours such that any two distinct vertices on a facial walk of length at most \l are coloured differently. We prove that every plane graph is $3$-facially $11$-colourable. As a consequence, we derive that every $2$-connected plane graph with maximum face-size at most $7$ is cyclically $11$-colourable. These two bounds are for one off from those that are proposed by the $(3\l+1)$-Conjecture and the Cyclic Conjecture.},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
sorte = "rev-int",
}
-
F. Havet,
S. Thomassé,
and A. Yeo.
Hoang-Reed conjecture for tournaments.
Discrete Mathematics,
308(15):3412--3415,
August 2008.
[PDF
]
| Abstract: |
|
Ho\`ang-Reed conjecture asserts that every digraph $D$ has a collection $\cal C$ of circuits $C_1,\dots,C_{\delta ^+}$, where $\delta ^+$ is the minimum outdegree of $D$, such that the circuits of $\cal C$ have a forest-like structure. Formally, $|V(C_i)\cap (V(C_1)\cup \dots \cup V(C_{i-1}))|\leq 1$, for all $i=2,\dots ,\delta^+$. We verify this conjecture for the class of tournaments. |
@ARTICLE{HTY08,
AUTHOR={F. Havet and S. Thomass\'e and A. Yeo},
TITLE={{H}oang-{R}eed conjecture for tournaments},
JOURNAL = {Discrete Mathematics},
VOLUME = {308},
NUMBER = {15},
MONTH = aug,
YEAR = {2008},
PAGES = {3412--3415},
pdf = {ftp://ftp-sop.inria.fr/mascotte/Publications/HTY08.pdf},
abstract={Ho\`ang-Reed conjecture asserts that every digraph $D$ has a collection $\cal C$ of circuits $C_1,\dots,C_{\delta ^+}$, where $\delta ^+$ is the minimum outdegree of $D$, such that the circuits of $\cal C$ have a forest-like structure. Formally, $|V(C_i)\cap (V(C_1)\cup \dots \cup V(C_{i-1}))|\leq 1$, for all $i=2,\dots ,\delta^+$. We verify this conjecture for the class of tournaments.},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
sorte = "rev-int",
}
-
F. Havet and M-L. Yu.
$(p,1)$-total labelling of graphs.
Discrete Mathematics,
308(4):496--513,
February 2008.
[PDF
]
| Abstract: |
|
A $(p,1)$-total labelling of a graph $G$ is an assignment of integers to $V(G)\cup E(G)$ such that: (i) any two adjacent vertices of $G$ receive distinct integers, (ii) any two adjacent edges of $G$ receive distinct integers, and (iii) a vertex and its incident edge receive integers that differ by at least $p$ in absolute value. The {\it span} of a $(p,1)$-total labelling is the maximum difference between two labels. The minimum span of a $(p,1)$-total labelling of $G$ is called the {\it $(p,1)$-total number} and denoted by $\lambda_p^T(G)$. We provide lower and upper bounds for the $(p,1)$-total number. In particular, generalizing the Total Colouring Conjecture, we conjecture that $\lambda_p^T\leq \Delta+ 2p - 1$ and give some evidences to support it. Finally, we determine the exact value of $\lambda^T_p(K_n)$, except for even $n$ in the interval $[p+5, 6p2-10p+4]$ for which we show that $\lambda_p^T(K_n) \in n+2p-3, n+2p-2$. |
@ARTICLE{HaYu08,
AUTHOR = "F. Havet and M-L. Yu",
TITLE = "$(p,1)$-total labelling of graphs",
JOURNAL = "Discrete Mathematics",
VOLUME = "308",
NUMBER = "4",
MONTH = feb,
YEAR = "2008",
PAGES = "496--513",
PDF = "ftp://ftp-sop.inria.fr/mascotte/Publications/HaYu08.pdf",
abstract={A $(p,1)$-total labelling of a graph $G$ is an assignment of integers to $V(G)\cup E(G)$ such that: (i) any two adjacent vertices of $G$ receive distinct integers, (ii) any two adjacent edges of $G$ receive distinct integers, and (iii) a vertex and its incident edge receive integers that differ by at least $p$ in absolute value. The {\it span} of a $(p,1)$-total labelling is the maximum difference between two labels. The minimum span of a $(p,1)$-total labelling of $G$ is called the {\it $(p,1)$-total number} and denoted by $\lambda_p^T(G)$. We provide lower and upper bounds for the $(p,1)$-total number. In particular, generalizing the Total Colouring Conjecture, we conjecture that $\lambda_p^T\leq \Delta+ 2p - 1$ and give some evidences to support it. Finally, we determine the exact value of $\lambda^T_p(K_n)$, except for even $n$ in the interval $[p+5, 6p2-10p+4]$ for which we show that $\lambda_p^T(K_n) \in n+2p-3, n+2p-2$.},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
sorte = "rev-int",
}
-
R. J. Kang,
T. Müller,
and J.-S. Sereni.
Improper colouring of (random) unit disk graphs.
Discrete Mathematics,
308:1438--1454,
April 2008.
Note: The Special Issue devoted to EuroComb 2005.
[PDF
]
@Article{KMS07,
author = {R. J. Kang and T. M\"uller and J.-S. Sereni},
title = {Improper colouring of (random) unit disk graphs},
year = {2008},
journal = {Discrete Mathematics},
volume={308},
OPTnumero= {8},
month = {April},
pages={1438--1454},
note={The {S}pecial {I}ssue devoted to {E}uro{C}omb 2005},
PDF={http://kam.mff.cuni.cz/~sereni/Articles/KMS07.pdf},
sorte = "rev-int",
}
-
K. Kawarabayashi,
O. Lee,
B. Reed,
and P. Wollan.
A weaker version of Lovasz' path removable conjecture.
Journal of Combinatorial Theory (Series B),
98:972-979,
2008.
@article{KLRW08,
author = {K. Kawarabayashi and O. Lee and B. Reed and P. Wollan},
title = {A weaker version of {L}ovasz' path removable conjecture},
journal = {Journal of Combinatorial Theory (Series B)},
volume = {98},
year = {2008},
pages = {972-979},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
sorte = "rev-int",
}
-
K. Kawarabayashi and B. Reed.
Fractional coloring and the odd Hadwiger's conjecture.
European Journal of Combinatorics,
29(2):411-417,
2008.
| Abstract: |
|
Gerards and Seymour (see [T.R. Jensen, B. Toft, Graph Coloring Problems, Wiley-Interscience, 1995], page 115) conjectured that if a graph has no odd complete minor of order p, then it is (p-1)-colorable. This is an analogue of the well known conjecture of Hadwiger, and in fact, this would immediately imply Hadwiger's conjecture. The current best known bound for the chromatic number of graphs without an odd complete minor of order p is O(plogp) by the recent result by Geelen et al. [J. Geelen, B. Gerards, B. Reed, P. Seymour, A. Vetta, On the odd variant of Hadwiger's conjecture (submitted for publication)], and by Kawarabayashi [K. Kawarabayashi, Note on coloring graphs without odd K"k-minors (submitted for publication)] (but later). But, it seems very hard to improve this bound since this would also improve the current best known bound for the chromatic number of graphs without a complete minor of order p. Motivated by this problem, we prove that the ''fractional chromatic number'' of a graph G without odd K"p-minor is at most 2p; that is, it is possible to assign a rational q(S)>=0 to every stable set SV(G) so that "S"vq(S)=1 for every vertex v, and "Sq(S)2p. This generalizes the result of Reed and Seymour [B. Reed, P.D. Seymour, Fractional chromatic number and Hadwiger's conjecture, J. Combin. Theory Ser. B 74 (1998) 147-152] who proved that the fractional chromatic number of a graph with no K"p"+"1-minor is at most 2p. |
@article{KaRe08a,
author = {K. Kawarabayashi and B. Reed},
title = {Fractional coloring and the odd {H}adwiger's conjecture},
journal = {European Journal of Combinatorics},
volume = {29},
number = {2},
year = {2008},
pages = {411-417},
abstract ={Gerards and Seymour (see [T.R. Jensen, B. Toft, Graph Coloring Problems, Wiley-Interscience, 1995], page 115) conjectured that if a graph has no odd complete minor of order p, then it is (p-1)-colorable. This is an analogue of the well known conjecture of Hadwiger, and in fact, this would immediately imply Hadwiger's conjecture. The current best known bound for the chromatic number of graphs without an odd complete minor of order p is O(plogp) by the recent result by Geelen et al. [J. Geelen, B. Gerards, B. Reed, P. Seymour, A. Vetta, On the odd variant of Hadwiger's conjecture (submitted for publication)], and by Kawarabayashi [K. Kawarabayashi, Note on coloring graphs without odd K"k-minors (submitted for publication)] (but later). But, it seems very hard to improve this bound since this would also improve the current best known bound for the chromatic number of graphs without a complete minor of order p. Motivated by this problem, we prove that the ''fractional chromatic number'' of a graph G without odd K"p-minor is at most 2p; that is, it is possible to assign a rational q(S)>=0 to every stable set SV(G) so that "S"vq(S)=1 for every vertex v, and "Sq(S)2p. This generalizes the result of Reed and Seymour [B. Reed, P.D. Seymour, Fractional chromatic number and Hadwiger's conjecture, J. Combin. Theory Ser. B 74 (1998) 147-152] who proved that the fractional chromatic number of a graph with no K"p"+"1-minor is at most 2p.},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
sorte = "rev-int",
}
-
R. Klasing,
N. Morales,
and S. Pérennes.
On the Complexity of Bandwidth Allocation in Radio Networks.
Theoretical Computer Science,
406(3):225-239,
October 2008.
[WWW
] [PDF
]
| Abstract: |
|
"We define and study an optimization problem that is motivated by bandwidth allocation in radio networks. Because radio transmissions are subject to interference constraints in radio networks, physical space is a common resource that the nodes have to share in such a way, that concurrent transmissions do not interfere. The bandwidth allocation problem we study under these constraints is the following. Given bandwidth (traffic) demands between the nodes of the network, the objective is to schedule the radio transmissions in such a way that the traffic demands are satisfied. The problem is similar to a multicommodity flow problem, where the capacity constraints are replaced by the more complex notion of non-interfering transmissions. We provide a formal specification of the problem that we call round weighting. By modeling non-interfering radio transmissions as independent sets, we relate the complexity of round weighting to the complexity of various independent set problems (e.g. maximum weight independent set, vertex coloring, fractional coloring). From this relation, we deduce that in general, round weighting is hard to approximate within n1âε (n being the size of the radio network). We also provide polynomial (exact or approximation) algorithms e.g. in the following two cases: (a) when the interference constraints are specific (for instance for a network whose vertices belong to the Euclidean space), or (b) when the traffic demands are directed towards a unique node in the network (also called gathering, analogous to single commodity flow)." |
@Article{KMP08,
author = "R. Klasing and N. Morales and S. P\'erennes",
title = "On the Complexity of Bandwidth Allocation in Radio Networks",
journal = "Theoretical Computer Science",
url = "http://dx.doi.org/10.1016/j.tcs.2008.06.048",
year = "2008",
month = oct,
pages = "225-239",
volume = "406",
number = "3",
abstract = "We define and study an optimization problem that is motivated by bandwidth allocation in radio networks. Because radio transmissions are subject to interference constraints in radio networks, physical space is a common resource that the nodes have to share in such a way, that concurrent transmissions do not interfere. The bandwidth allocation problem we study under these constraints is the following. Given bandwidth (traffic) demands between the nodes of the network, the objective is to schedule the radio transmissions in such a way that the traffic demands are satisfied. The problem is similar to a multicommodity flow problem, where the capacity constraints are replaced by the more complex notion of non-interfering transmissions. We provide a formal specification of the problem that we call round weighting. By modeling non-interfering radio transmissions as independent sets, we relate the complexity of round weighting to the complexity of various independent set problems (e.g. maximum weight independent set, vertex coloring, fractional coloring). From this relation, we deduce that in general, round weighting is hard to approximate within n1âε (n being the size of the radio network). We also provide polynomial (exact or approximation) algorithms e.g. in the following two cases: (a) when the interference constraints are specific (for instance for a network whose vertices belong to the Euclidean space), or (b) when the traffic demands are directed towards a unique node in the network (also called gathering, analogous to single commodity flow).",
pdf = "ftp://ftp-sop.inria.fr/mascotte/Publications/KMP08.pdf",
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
sorte = "rev-int",
}
-
C. Linhares-Sales,
F. Maffray,
and B. Reed.
On Planar Quasi-Parity Graphs.
SIAM Journal of Discrete Mathematics,
22:329-347,
2008.
@article{LMR08,
author = {C. {Linhares-Sales} and F. Maffray and B. Reed},
title = {On Planar Quasi-Parity Graphs},
journal = {SIAM Journal of Discrete Mathematics},
volume = {22},
year = {2008},
pages = {329-347},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
sorte = "rev-int",
}
-
F. Mazoit and N. Nisse.
Monotonicity of non-deterministic graph searching.
Theoretical Computer Science,
399(3):169-178,
2008.
[WWW
] [PDF
]
| Abstract: |
|
In graph searching, a team of searchers are aiming at capturing a fugitive moving in a graph. In the initial variant, called invisible graph searching, the searchers do not know the position of the fugitive until they catch it. In another variant, the searchers permanently know the position of the fugitive, i.e. the fugitive is visible. This latter variant is called visible graph searching. A search strategy that catches any fugitive in such a way that the part of the graph reachable by the fugitive never grows is called monotone. A priori, monotone strategies may require more searchers than general strategies to catch any fugitive. This is however not the case for visible and invisible graph searching. Two important consequences of the monotonicity of visible and invisible graph searching are: (1) the decision problem corresponding to the computation of the smallest number of searchers required to clear a graph is in NP, and (2) computing optimal search strate gies is simplified by taking into account that there exist some that never backtrack. Fomin et al. [F.V. Fomin, P. Fraigniaud, N. Nisse, Nondeterministic graph searching: From pathwidth to treewidth, in: Proceedings of the 30th International Symposium on Mathematical Foundations of Computer Science, MFCS 2005, pp. 364--375] introduced an important graph searching variant, called non-deterministic graph searching, that unifies visible and invisible graph searching. In this variant, the fugitive is invisible, and the searchers can query an oracle that permanently knows the current position of the fugitive. The question of the monotonicity of non-deterministic graph searching was however left open. In this paper, we prove that non-deterministic graph searching is monotone. In particular, this result is a unified proof of monotonicity for visible and invisible graph searching. As a consequence, the decision problem corresponding to non-deterministic graph searching belongs to NP. Moreover, the exact algorithms designed by Fomin et al. do compute optimal non-deterministic search strategies. |
@article{MaNi08,
author = {F. Mazoit and N. Nisse},
title = {Monotonicity of non-deterministic graph searching},
journal = {Theoretical Computer Science},
volume = {399},
number = {3},
year = {2008},
pages = {169-178},
abstract = {In graph searching, a team of searchers are aiming at capturing a fugitive moving in a graph. In the initial variant, called invisible graph searching, the searchers do not know the position of the fugitive until they catch it. In another variant, the searchers permanently know the position of the fugitive, i.e. the fugitive is visible. This latter variant is called visible graph searching. A search strategy that catches any fugitive in such a way that the part of the graph reachable by the fugitive never grows is called monotone. A priori, monotone strategies may require more searchers than general strategies to catch any fugitive. This is however not the case for visible and invisible graph searching. Two important consequences of the monotonicity of visible and invisible graph searching are: (1) the decision problem corresponding to the computation of the smallest number of searchers required to clear a graph is in NP, and (2) computing optimal search strate gies is simplified by taking into account that there exist some that never backtrack. Fomin et al. [F.V. Fomin, P. Fraigniaud, N. Nisse, Nondeterministic graph searching: From pathwidth to treewidth, in: Proceedings of the 30th International Symposium on Mathematical Foundations of Computer Science, MFCS 2005, pp. 364--375] introduced an important graph searching variant, called non-deterministic graph searching, that unifies visible and invisible graph searching. In this variant, the fugitive is invisible, and the searchers can query an oracle that permanently knows the current position of the fugitive. The question of the monotonicity of non-deterministic graph searching was however left open. In this paper, we prove that non-deterministic graph searching is monotone. In particular, this result is a unified proof of monotonicity for visible and invisible graph searching. As a consequence, the decision problem corresponding to non-deterministic graph searching belongs to NP. Moreover, the exact algorithms designed by Fomin et al. do compute optimal non-deterministic search strategies.},
url = {http://dx.doi.org/10.1016/j.tcs.2008.02.036},
pdf = {http://www-sop.inria.fr/members/Nicolas.Nisse/publications/Grasta06.pdf},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
sorte = "rev-int",
}
-
C. McDiarmid and B. Reed.
On the maximum degree of a random planar graph.
Combinatorics, Probability and Computing,
17:591-601,
2008.
@article{McRe08,
author = {C. McDiarmid and B. Reed},
title = {On the maximum degree of a random planar graph},
journal = {Combinatorics, Probability and Computing},
volume = {17},
year = {2008},
pages = {591-601},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
sorte = "rev-int",
}
-
C. Meagher and B. Reed.
Fractionally total colouring ${G}_{n,p}$.
Discrete Applied Mathematics,
156:1112-1124,
2008.
@article{MeRe08,
author = {C. Meagher and B. Reed},
title = {Fractionally total colouring ${G}_{n,p}$},
journal = {Discrete Applied Mathematics},
volume = {156},
year = {2008},
pages = {1112-1124 },
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
sorte = "rev-int",
}
-
B. Reed.
Skew Partitions in Perfect Graphs.
Discrete Applied Mathematics,
156:1150-1156,
2008.
@article{Ree08,
author = {B. Reed},
title = {Skew Partitions in Perfect Graphs},
journal = {Discrete Applied Mathematics},
volume = {156},
year = {2008},
pages = {1150-1156},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
sorte = "rev-int",
}
-
I. Sau and J. Zerovnik.
An Optimal Permutation Routing Algorithm on Full-Duplex Hexagonal Networks.
Discrete Mathematics and Theoretical Computer Science,
10(3):49-62,
2008.
[PDF
]
| Abstract: |
|
In the permutation routing problem, each processor is the origin of at most one packet and the destination of no more than one packet. The goal is to minimize the number of time steps required to route all packets to their respective destinations, under the constraint that each link can be crossed simultaneously by no more than one packet. We study this problem in a hexagonal network, i.e. a finite subgraph of a triangular grid, which is a widely used network in practical applications. We present an optimal distributed permutation routing algorithm for full-duplex hexagonal networks, using the addressing scheme described by F.G. Nocetti, I. Stojmenovi\'{c} and J. Zhang (IEEE TPDS 13(9): 962-971, 2002). Furthermore, we prove that this algorithm is oblivious and translation invariant. |
@ARTICLE{SaZe08,
AUTHOR = {I. Sau and J. {\v Z}erovnik},
TITLE = {An Optimal Permutation Routing Algorithm on Full-Duplex Hexagonal Networks},
JOURNAL = {Discrete Mathematics and Theoretical Computer Science},
YEAR = {2008},
volume = {10},
number = {3},
pages = {49-62},
abstract = {In the permutation routing problem, each processor is the origin of at most one packet and the destination of no more than one packet. The goal is to minimize the number of time steps required to route all packets to their respective destinations, under the constraint that each link can be crossed simultaneously by no more than one packet. We study this problem in a hexagonal network, i.e. a finite subgraph of a triangular grid, which is a widely used network in practical applications. We present an optimal distributed permutation routing algorithm for full-duplex hexagonal networks, using the addressing scheme described by F.G. Nocetti, I. Stojmenovi\'{c} and J. Zhang (IEEE TPDS 13(9): 962-971, 2002). Furthermore, we prove that this algorithm is oblivious and translation invariant.},
pdf = {ftp://ftp-sop.inria.fr/mascotte/Publications/SZ08.pdf},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
sorte = "rev-int",
}
-
L. Addario-Berry,
O. Amini,
J.-S. Sereni,
and S. Thomassé.
Guarding art galleries: the extra cost for sculptures is linear.
In Proceedings of the Scandinavian Workshop on Algorithm Theory (SWAT 2008),
volume 5124 of Lecture Notes in Computer Science,
pages 41-52,
July 2008.
Springer.
@inProceedings{AAST08,
author = {L. {Addario-Berry} and O. Amini and J.-S. Sereni and S. Thomass\'e},
title = {Guarding art galleries: the extra cost for sculptures is linear},
booktitle = {Proceedings of the Scandinavian Workshop on Algorithm Theory (SWAT 2008)},
year = {2008},
pages = {41-52},
series = {Lecture Notes in Computer Science},
volume = {5124},
publisher = {Springer},
month = jul,
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
sorte = "conf-int",
}
-
A. Aguiar,
P.R. Pinheiro,
A.L.V Coelho,
N. Nepomuceno,
A. Neto,
and R. Cunha.
Scalability Analysis of a Novel Integer Programming Model to Deal with Energy Consumption in Heterogeneous Wireless Sensor Networks.
In Modelling, Computation and Optimization in Information Systems and Management Sciences (MCO'08),
volume 14 of Communications in Computer and Information Science,
pages 11-20,
2008.
Springer.
[WWW
] [PDF
]
| Abstract: |
|
This paper presents a scalability analysis over a novel integer programming model devoted to optimize power consumption efficiency in heterogeneous wireless sensor networks. This model is based upon a schedule of sensor allocation plans in multiple time intervals subject to coverage and connectivity constraints. By turning off a specific set of redundant sensors in each time interval, it is possible to reduce the total energy consumption in the network and, at the same time, avoid partitioning the whole network by losing some strategic sensors too prematurely. Since the network is heterogeneous, sensors can sense different phenomena from different demand points, with different sample rates. As the problem instances grows the time spent to the execution turns impracticable. |
@inproceedings{APC+08,
author = {A. Aguiar and P.R. Pinheiro and A.L.V Coelho and N. Nepomuceno and A. Neto and R. Cunha},
title = {Scalability Analysis of a Novel Integer Programming Model to Deal with Energy Consumption in Heterogeneous Wireless Sensor Networks},
booktitle = {Modelling, Computation and Optimization in Information Systems and Management Sciences (MCO'08)},
series = {Communications in Computer and Information Science},
volume = {14},
year = {2008},
pages = {11-20},
publisher = {Springer},
abstract = {This paper presents a scalability analysis over a novel integer programming model devoted to optimize power consumption efficiency in heterogeneous wireless sensor networks. This model is based upon a schedule of sensor allocation plans in multiple time intervals subject to coverage and connectivity constraints. By turning off a specific set of redundant sensors in each time interval, it is possible to reduce the total energy consumption in the network and, at the same time, avoid partitioning the whole network by losing some strategic sensors too prematurely. Since the network is heterogeneous, sensors can sense different phenomena from different demand points, with different sample rates. As the problem instances grows the time spent to the execution turns impracticable.},
pdf = {ftp://ftp-sop.inria.fr/mascotte/Publications/APCNNC08.pdf},
url = {http://dx.doi.org/10.1007/978-3-540-87477-5_2},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
x-pays = {BR},
sorte = "conf-int",
}
-
O. Amini,
S. Griffiths,
and F. Huc.
4-cycles in mixing digraphs.
In Electronic Notes in Discrete MathematicsVolume 30, The IV Latin-American Algorithms, Graphs, and Optimization Symposium (LAGOS 07),
volume 30,
Puerto Varas, Chile,
pages 63--68,
February 2008.
[PDF
]
| Abstract: |
|
It is known that every simple graph with $n^{3/2}$ edges contains a 4-cycle. A similar statement for digraphs is not possible since no condition on the number of edges can guarantee an (oriented) 4-cycle. We find a condition which does guarantee the presence of a 4-cycle and our result is tight. Our condition, which we call $f$-mixing, can be seen as a quasirandomness condition on the orientation of the graph. We also investigate the notion of mixing in the case of regular and almost regular digraphs. In particular we determine how mixing a random orientation of a random graph is. |
@InProceedings{AGH08,
author = {O. Amini and S. Griffiths and F. Huc},
title = {4-cycles in mixing digraphs},
booktitle = {Electronic Notes in Discrete MathematicsVolume 30, The IV Latin-American Algorithms, Graphs, and Optimization Symposium (LAGOS 07)},
year = {2008},
address = {Puerto Varas, Chile},
month = feb,
pages={63--68},
volume = {30},
pdf = {ftp://ftp-sop.inria.fr/mascotte/Publications/AGH07.pdf},
abstract= {It is known that every simple graph with $n^{3/2}$ edges contains a 4-cycle. A similar statement for digraphs is not possible since no condition on the number of edges can guarantee an (oriented) 4-cycle. We find a condition which does guarantee the presence of a 4-cycle and our result is tight. Our condition, which we call $f$-mixing, can be seen as a quasirandomness condition on the orientation of the graph. We also investigate the notion of mixing in the case of regular and almost regular digraphs. In particular we determine how mixing a random orientation of a random graph is.},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
sorte = "conf-int",
}
-
O. Amini,
D. Peleg,
S. Pérennes,
I. Sau,
and S. Saurabh.
Degree-Constrained Subgraph Problems : Hardness and Approximation Results.
In 6th International Workshop on Approximation and Online Algorithms (ALGO-WAOA 2008),
volume 5426 of Lecture Notes in Computer Science,
Karlsruhe, Germany,
pages 29-42,
September 2008.
[PDF
]
| Abstract: |
|
A general instance of a \sc Degree-Constrained Subgraph problem consists of an edge-weighted or vertex-weighted graph $G$ and the objective is to find an optimal weighted subgraph, subject to certain degree constraints on the vertices of the subgraph. This class of combinatorial problems has been extensively studied due to its numerous applications in network design. If the input graph is bipartite, these problems are equivalent to classical transportation and assignment problems in operations research. This paper considers three natural \sc Degree-Constrained Subgraph problems and studies their behavior in terms of approximation algorithms. These problems take as input an undirected graph $G=(V,E)$, with $|V|=n$ and $|E|=m$. Our results, together with the definition of the three problems, are listed below. The Maximum Degree-Bounded Connected Subgraph (MDBCS$_d$) problem takes as input a weight function $\omega : E \rightarrow \mathbb R^+$ and an integer $d \geq 2$, and asks for a subset $E' \subseteq E$ such that the subgraph $G'=(V,E')$ is connected, has maximum degree at most $d$, and $\sum_e\in E' \omega(e)$ is maximized. This problem is one of the classical NP-hard problems listed by Garey and Johnson in (Computers and Intractability, W.H. Freeman, 1979), but there were no results in the literature except for $d=2$. We prove that MDBCS$_d$ is not in Apx for any $d\geq 2$ (this was known only for $d=2$) and we provide a $(\min m/ \log n,\ nd/(2 \log n))$-approximation algorithm for unweighted graphs, and a $(\min n/2,\ m/d)$-approximation algorithm for weighted graphs. We also prove that when $G$ accepts a low-degree spanning tree, in terms of $d$, then MDBCS$_d$ can be approximated within a small constant factor in unweighted graphs. The \sc Minimum Subgraph of Minimum Degree$_\geq d$ (MSMD$_d$) problem consists in finding a smallest subgraph of $G$ (in terms of number of vertices) with minimum degree at least $d$. We prove that MSMD$_d$ is not in Apx for any $d\geq 3$ and we provide an $\mathcal O(n/\log n)$-approximation algorithm for the classes of graphs excluding a fixed graph as a minor, using dynamic programming techniques and a known structural result on graph minors. In particular, this approximation algorithm applies to planar graphs and graphs of bounded genus. The \sc Dual Degree-Dense $k$-Subgraph (DDD$k$S) problem consists in finding a subgraph $H$ of $G$ such that $|V(H)| \leq k$ and $\delta_H$ is maximized, where $\delta_H$ is the minimum degree in $H$. We present a deterministic $\mathcal O(n^\delta)$-approximation algorithm in general graphs, for some universal constant $\delta < 1/3$. |
@inproceedings{APP+08a,
author = {O. Amini and D. Peleg and S. P\'erennes and I. Sau and S. {S}aurabh},
title = {Degree-Constrained Subgraph Problems : Hardness and Approximation Results},
booktitle = {6th International Workshop on Approximation and Online Algorithms (ALGO-WAOA 2008)},
year = {2008},
series = {Lecture Notes in Computer Science},
volume = {5426},
pages = {29-42},
month = sep,
address = {Karlsruhe, Germany},
pdf = {ftp://ftp-sop.inria.fr/mascotte/Publications/APP+08.pdf},
abstract = {A general instance of a \sc Degree-Constrained Subgraph problem consists of an edge-weighted or vertex-weighted graph $G$ and the objective is to find an optimal weighted subgraph, subject to certain degree constraints on the vertices of the subgraph. This class of combinatorial problems has been extensively studied due to its numerous applications in network design. If the input graph is bipartite, these problems are equivalent to classical transportation and assignment problems in operations research. This paper considers three natural \sc Degree-Constrained Subgraph problems and studies their behavior in terms of approximation algorithms. These problems take as input an undirected graph $G=(V,E)$, with $|V|=n$ and $|E|=m$. Our results, together with the definition of the three problems, are listed below. The Maximum Degree-Bounded Connected Subgraph (MDBCS$_d$) problem takes as input a weight function $\omega : E \rightarrow \mathbb R^+$ and an integer $d \geq 2$, and asks for a subset $E' \subseteq E$ such that the subgraph $G'=(V,E')$ is connected, has maximum degree at most $d$, and $\sum_e\in E' \omega(e)$ is maximized. This problem is one of the classical NP-hard problems listed by Garey and Johnson in (Computers and Intractability, W.H. Freeman, 1979), but there were no results in the literature except for $d=2$. We prove that MDBCS$_d$ is not in Apx for any $d\geq 2$ (this was known only for $d=2$) and we provide a $(\min m/ \log n,\ nd/(2 \log n))$-approximation algorithm for unweighted graphs, and a $(\min n/2,\ m/d)$-approximation algorithm for weighted graphs. We also prove that when $G$ accepts a low-degree spanning tree, in terms of $d$, then MDBCS$_d$ can be approximated within a small constant factor in unweighted graphs. The \sc Minimum Subgraph of Minimum Degree$_\geq d$ (MSMD$_d$) problem consists in finding a smallest subgraph of $G$ (in terms of number of vertices) with minimum degree at least $d$. We prove that MSMD$_d$ is not in Apx for any $d\geq 3$ and we provide an $\mathcal O(n/\log n)$-approximation algorithm for the classes of graphs excluding a fixed graph as a minor, using dynamic programming techniques and a known structural result on graph minors. In particular, this approximation algorithm applies to planar graphs and graphs of bounded genus. The \sc Dual Degree-Dense $k$-Subgraph (DDD$k$S) problem consists in finding a subgraph $H$ of $G$ such that $|V(H)| \leq k$ and $\delta_H$ is maximized, where $\delta_H$ is the minimum degree in $H$. We present a deterministic $\mathcal O(n^\delta)$-approximation algorithm in general graphs, for some universal constant $\delta < 1/3$.},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
sorte = "conf-int",
}
-
O. Amini,
I. Sau,
and S. Saurabh.
Parameterized Complexity of the Smallest Degree-Constrained Subgraph Problem.
In The International Workshop on Parameterized and Exact Computation (IWPEC 2008),
volume 5008 of Lecture Notes in Computer Science,
Victoria, Canada,
pages 13-29,
May 2008.
[PDF
]
| Abstract: |
|
{In this paper we study the problem of finding an induced subgraph of size at most $k$ with minimum degree at least $d$ for a given graph $G$, from the parameterized complexity perspective. We call this problem {\sc Minimum Subgraph of Minimum Degree $_{\geq d}$ ({\sc MSMD}$_d$)}. For $d=2$ it corresponds to finding a shortest cycle of the graph. Our main motivation to study this problem is its strong relation to \textsc{Dense $k$-Subgraph} and \textsc{Traffic Grooming} problems. First, we show that {\sc MSMS}$_d$ is fixed-parameter intractable (provided $FPT\neq W[1]$) for $d\geq 3$ in general graphs, by showing it to be $W[1]$-hard using a reduction from {\sc Multi-Color Clique}. In the second part of the paper we provide {\em explicit} fixed-parameter tractable (FPT) algorithms for the problem in graphs with bounded local tree-width and graphs with excluded minors, {\em faster} than those coming from the meta-theorem of Frick and Grohe [FrickG01] about problems definable in first order logic over ``locally tree-decomposable structures". In particular, this implies faster fixed-parameter tractable algorithms in planar graphs, graphs of bounded genus, and graphs with bounded maximum degree.}, OPTx-editorial-board={yes}, OPTx-proceedings={yes}, OPTx-international-audience={yes}, sorte = "conf-int", |
@InProceedings{ASS08,
AUTHOR = {O. Amini and I. Sau and S. {S}aurabh},
TITLE = {{Parameterized Complexity of the Smallest Degree-Constrained Subgraph Problem}},
booktitle = {The International Workshop on Parameterized and Exact Computation (IWPEC 2008)},
YEAR = {2008},
pages = {13-29},
series = {Lecture Notes in Computer Science},
volume = {5008},
month= may,
address = {Victoria, Canada},
pdf = {ftp://ftp-sop.inria.fr/mascotte/Publications/ASS08.pdf},
abstract = {In this paper we study the problem of finding an induced subgraph of size at most $k$ with minimum degree at least $d$ for a given graph $G$, from the parameterized complexity perspective. We call this problem {\sc Minimum Subgraph of Minimum Degree $_{\geq d}$ ({\sc MSMD}$_d$)}. For $d=2$ it corresponds to finding a shortest cycle of the graph. Our main motivation to study this problem is its strong relation to \textsc{Dense $k$-Subgraph} and \textsc{Traffic Grooming} problems. First, we show that {\sc MSMS}$_d$ is fixed-parameter intractable (provided $FPT\neq W[1]$) for $d\geq 3$ in general graphs, by showing it to be $W[1]$-hard using a reduction from {\sc Multi-Color Clique}. In the second part of the paper we provide {\em explicit} fixed-parameter tractable (FPT) algorithms for the problem in graphs with bounded local tree-width and graphs with excluded minors, {\em faster} than those coming from the meta-theorem of Frick and Grohe [FrickG01] about problems definable in first order logic over ``locally tree-decomposable structures". In particular, this implies faster fixed-parameter tractable algorithms in planar graphs, graphs of bounded genus, and graphs with bounded maximum degree.}, OPTx-editorial-board={yes}, OPTx-proceedings={yes}, OPTx-international-audience={yes}, sorte = "conf-int",
}
-
M. Asté,
F. Havet,
and C. Linhares-Sales.
Grundy number and lexicographic product of graphs.
In Proceedings of International Conference on Relations, Orders and Graphs and their Interaction with Computer Science (ROGICS 2008),
pages 9p,
May 2008.
[WWW
] [PDF
]
| Abstract: |
|
The {\em Grundy number} of a graph $G$, denoted by $\Gamma (G)$, is the largest $k$ such that $G$ has a {\em greedy} $k$-colouring, that is a colouring with $k$ colours obtained by applying the greedy algorithm according to some ordering of the vertices of $G$. In this paper, we study the Grundy number of the lexicographic product of two graphs in terms of the Grundy numbers of these graphs. We show that $\Gamma(G)\times\Gamma(H)\leq \Gamma(G[H])\leq 2^{\Gamma(G)-1}(\Gamma(H)-1)+\Gamma(G)-1$. In addition, we show that if $G$ is a tree or $\Gamma(G)=\Delta(G)+1$, then $\Gamma(G[H])=\Gamma(G)\times\Gamma(H)$. We then deduce that for every fixed $c\leq 1$, given a graph $G$, it is CoNP-Complete to decide if $\Gamma(G)\leq c\times \chi(G)$ and it is CoNP-Complete to decide if $\Gamma(G)\leq c\times \omega(G)$. |
@InProceedings{AHL08a,
author={M. Ast\'e and F. Havet and C. {Linhares-Sales}},
booktitle={Proceedings of International Conference on Relations, Orders and Graphs and their Interaction with Computer Science (ROGICS 2008)},
month=may,
title={Grundy number and lexicographic product of graphs},
pages = {9p},
year={2008},
URL={http://www.rogics.com/},
abstract={The {\em Grundy number} of a graph $G$, denoted by $\Gamma (G)$, is the largest $k$ such that $G$ has a {\em greedy} $k$-colouring, that is a colouring with $k$ colours obtained by applying the greedy algorithm according to some ordering of the vertices of $G$. In this paper, we study the Grundy number of the lexicographic product of two graphs in terms of the Grundy numbers of these graphs. We show that $\Gamma(G)\times\Gamma(H)\leq \Gamma(G[H])\leq 2^{\Gamma(G)-1}(\Gamma(H)-1)+\Gamma(G)-1$. In addition, we show that if $G$ is a tree or $\Gamma(G)=\Delta(G)+1$, then $\Gamma(G[H])=\Gamma(G)\times\Gamma(H)$. We then deduce that for every fixed $c\leq 1$, given a graph $G$, it is CoNP-Complete to decide if $\Gamma(G)\leq c\times \chi(G)$ and it is CoNP-Complete to decide if $\Gamma(G)\leq c\times \omega(G)$.},
pdf = {ftp://ftp-sop.inria.fr/mascotte/Publications/AHL08.pdf},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
sorte = "conf-int",
}
-
J-C. Bermond,
L. Gargano,
and A.A. Rescigno.
Gathering with minimum delay in tree sensor networks.
In SIROCCO 2008,
volume 5058 of Lecture Notes in Computer Science,
Villars-sur-Ollon, Switzerland,
pages 262-276,
June 2008.
Springer-Verlag.
[PDF
]
| Abstract: |
|
Data gathering is a fundamental operation in wireless sensor networks in which data packets generated at sensor nodes are to be collected at a base station. In this paper we suppose that each sensor is equipped with an half--duplex interface; hence, a node cannot receive and transmit at the same time. Moreover, each node is equipped with omnidirectional antennas allowing the transmission over distance R. The network is a multi-hop wireless network and the time is slotted so that one--hop transmission of one data item consumes one time slot. We model the network with a graph where the vertices represent the nodes and two nodes are connected if they are in the transmission/interference range of each other. Due to interferences a collision happens at a node if two or more of its neighbors try to transmit at the same time. Furthermore we suppose that an intermediate node should forward a message as soon as it receives it. We give an optimal collision free gathering schedule for tree networks whenever each node has at least one data packet to send. |
@inproceedings{BGR08,
author= { J-C. Bermond and L. Gargano and A.A. Rescigno },
title= {Gathering with minimum delay in tree sensor networks },
booktitle= { SIROCCO 2008 },
publisher= { Springer-Verlag },
series= {Lecture Notes in Computer Science},
address= {Villars-sur-Ollon, Switzerland },
volume= { 5058 },
pages = {262-276},
month=jun,
year= {2008},
PDF={http://www-sop.inria.fr/members/Jean-Claude.Bermond/PUBLIS/BGR08.pdf},
abstract={Data gathering is a fundamental operation in wireless sensor networks in which data packets generated at sensor nodes are to be collected at a base station. In this paper we suppose that each sensor is equipped with an half--duplex interface; hence, a node cannot receive and transmit at the same time. Moreover, each node is equipped with omnidirectional antennas allowing the transmission over distance R. The network is a multi-hop wireless network and the time is slotted so that one--hop transmission of one data item consumes one time slot. We model the network with a graph where the vertices represent the nodes and two nodes are connected if they are in the transmission/interference range of each other. Due to interferences a collision happens at a node if two or more of its neighbors try to transmit at the same time. Furthermore we suppose that an intermediate node should forward a message as soon as it receives it. We give an optimal collision free gathering schedule for tree networks whenever each node has at least one data packet to send.},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
sorte = "conf-int",
}
-
J-C. Bermond and M-L. Yu.
Optimal gathering algorithms in multi-hop radio tree networks with interferences.
In Proceedings of the 7th international conference on Ad Hoc Networks and Wireless (AdHoc-Now),
volume 5198 of Lecture Notes in Computer Science,
pages 204-217,
September 2008.
Springer.
[PDF
]
| Abstract: |
|
We study the problem of gathering information from the nodes of a multi-hop radio network into a pre-defined destination node under the interference constraints. In such a network, a message can only be properly received if there is no interference from another message being simultaneously transmitted. The network is modeled as a graph, where the vertices represent the nodes and the edges, the possible communications. The interference constraint is modeled by a fixed integer $d_I \geq 1$, which implies that nodes within distance $d_I$ in the graph from one sender cannot receive messages from another node. In this paper, we suppose that it takes one unit of time (slot) to transmit a unit-length message. A step (or round) consists of a set of non interfering (compatible) calls and uses one slot. We present optimal algorithms that give minimum number of steps (delay) for the gathering problem with buffering possibility, when the network is a tree, the root is the destination and $d_I =1$. In fact we study the equivalent personalized broadcasting problem instead. |
@inproceedings{BeYu08,
author= { J-C. Bermond and M-L. Yu },
title= {Optimal gathering algorithms in multi-hop radio tree networks with interferences },
booktitle= {Proceedings of the 7th international conference on Ad Hoc Networks and Wireless (AdHoc-Now) },
publisher= { Springer},
series= {Lecture Notes in Computer Science},
volume= { 5198 },
pages = {204-217},
year= {2008},
month=sep,
PDF={http://www-sop.inria.fr/members/Jean-Claude.Bermond/PUBLIS/BeYu08.pdf},
abstract={We study the problem of gathering information from the nodes of a multi-hop radio network into a pre-defined destination node under the interference constraints. In such a network, a message can only be properly received if there is no interference from another message being simultaneously transmitted. The network is modeled as a graph, where the vertices represent the nodes and the edges, the possible communications. The interference constraint is modeled by a fixed integer $d_I \geq 1$, which implies that nodes within distance $d_I$ in the graph from one sender cannot receive messages from another node. In this paper, we suppose that it takes one unit of time (slot) to transmit a unit-length message. A step (or round) consists of a set of non interfering (compatible) calls and uses one slot. We present optimal algorithms that give minimum number of steps (delay) for the gathering problem with buffering possibility, when the network is a tree, the root is the destination and $d_I =1$. In fact we study the equivalent personalized broadcasting problem instead.},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
sorte = "conf-int",
}
-
D. Coudert,
F. Huc,
and D. Mazauric.
Algorithme générique pour les jeux de capture dans les arbres.
In 10èmes Rencontres Francophones sur les Aspects Algorithmiques de Télécommunications (AlgoTel'08),
Saint-Malo,
pages 37--40,
May 2008.
[PDF
]
| Abstract: |
|
Nous pr\'esentons un algorithme distribu\'e simple calculant le process number des arbres en O(n.log(n)) \'etapes. De plus cet algorithme est facilement adaptable pour calculer d'autre param\`etres sur l'arbre, dont la pathwidth. Nous pr\'esentons \'egalement une condition n\'ecessaire et suffisante pour que la pathwidth d'un arbre soit \'egale \`a son process number. |
@inProceedings{CHM08a,
author = {D. Coudert and F. Huc and D. Mazauric},
title = {Algorithme g\'en\'erique pour les jeux de capture dans les arbres},
booktitle = {10\`emes Rencontres Francophones sur les Aspects Algorithmiques de T\'el\'ecommunications (AlgoTel'08)},
pages = {37--40},
year = {2008},
month = may,
address = {Saint-Malo},
abstract = {Nous pr\'esentons un algorithme distribu\'e simple calculant le process number des arbres en O(n.log(n)) \'etapes. De plus cet algorithme est facilement adaptable pour calculer d'autre param\`etres sur l'arbre, dont la pathwidth. Nous pr\'esentons \'egalement une condition n\'ecessaire et suffisante pour que la pathwidth d'un arbre soit \'egale \`a son process number.},
pdf = {ftp://ftp-sop.inria.fr/mascotte/personnel/David.Coudert/Publication/CHM-AlgoTel08.pdf},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={no},
sorte = "conf-nat",
}
-
D. Coudert,
F. Huc,
and D. Mazauric.
A distributed algorithm for computing and updating the process number of a forest (brief announcement).
In G. Taubenfeld, editor,
22nd International Symposium on Distributed Computing (DISC),
volume 5218 of Lecture Notes in Computer Science,
Arcachon, France,
pages 500-501,
September 2008.
Springer.
[PDF
]
| Abstract: |
|
In this paper, we present a distributed algorithm to compute various parameters of a tree such as the process number, the edge search number or the node search number and so the pathwidth. This algorithm requires n steps, an overall computation time of O(n log(n)), and n messages of size log_3(n)+3. We then propose a distributed algorithm to update the process number (or the node search number, or the edge search number) of each component of a forest after adding or deleting an edge. This second algorithm requires O(D) steps, an overall computation time of O(D log(n)), and O(D) messages of size log_3(n)+3, where D is the diameter of the modified connected component. Finally, we show how to extend our algorithms to trees and forests of unknown size using messages of less than 2a+4+e bits, where a is the parameter to be determined and e=1 for updates algorithms. |
@InProceedings{CHM08c,
author = {D. Coudert and F. Huc and D. Mazauric},
title = {A distributed algorithm for computing and updating the process number of a forest (brief announcement)},
booktitle = {22nd International Symposium on Distributed Computing (DISC)},
OPTcrossref = {},
OPTkey = {},
pages = {500-501},
year = {2008},
editor = {G. Taubenfeld},
volume = {5218},
OPTnumber = {},
series = {Lecture Notes in Computer Science},
address = {Arcachon, France},
month = sep,
OPTorganization = {},
publisher = {Springer},
OPTannote = {},
abstract = {In this paper, we present a distributed algorithm to compute various parameters of a tree such as the process number, the edge search number or the node search number and so the pathwidth. This algorithm requires n steps, an overall computation time of O(n log(n)), and n messages of size log_3(n)+3. We then propose a distributed algorithm to update the process number (or the node search number, or the edge search number) of each component of a forest after adding or deleting an edge. This second algorithm requires O(D) steps, an overall computation time of O(D log(n)), and O(D) messages of size log_3(n)+3, where D is the diameter of the modified connected component. Finally, we show how to extend our algorithms to trees and forests of unknown size using messages of less than 2a+4+e bits, where a is the parameter to be determined and e=1 for updates algorithms.},
pdf = {ftp://ftp-sop.inria.fr/mascotte/personnel/David.Coudert/Publication/CHM-DISC08.pdf},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
sorte = "conf-int",
}
-
D. Coudert,
F. Huc,
and D. Mazauric.
Computing and updating the process number in trees (short paper).
In T. Baker and S. Tixeuil, editors,
12th International Conference On Principles Of DIstributed Systems (OPODIS),
volume 5401 of Lecture Notes in Computer Science,
Luxor, Egypt,
pages 546-550,
December 2008.
Springer.
[WWW
] [PDF
]
| Abstract: |
|
The process number is the number of requests that have to be simultaneously disturbed during a routing reconfiguration phase of a connection oriented network. From a graph theory point of view, it is similar to the node search number, and thus to the pathwidth. However they are not always equal in general graphs. Determining these parameters is in general NP-complete. In this paper, we characterize the cases in which the process number and the node search number are equal in trees. We also present a distributed algorithm to compute these parameters as well as the edge search number. This algorithm can be executed in an asynchronous environment, requires $n$ steps, an overall computation time of $O(n\log{n})$, and $n$ messages of size $\log_3{n}+2$. We then propose a distributed algorithm to update the process number (or the node search number, or the edge search number) of each component of a forest after addition or deletion of any edge. This second algorithm requires $O(D)$ steps, an overall computation time of $O(D\log{n})$, and $O(D)$ messages of size $\log_3{n}+3$, where $D$ is the diameter of the modified connected component. Finally, we show how to extend our algorithms to trees and forests of unknown size using messages of less than $2\alpha+5$ bits, where $\alpha\leq\log_3{n}$ is the parameter to be determined. |
@InProceedings{CHM08d,
author = {D. Coudert and F. Huc and D. Mazauric},
title = {Computing and updating the process number in trees (short paper)},
booktitle = {12th International Conference On Principles Of DIstributed Systems (OPODIS)},
OPTcrossref = {},
OPTkey = {},
pages = {546-550},
year = {2008},
editor = {T. Baker and S. Tixeuil},
volume = {5401},
OPTnumber = {},
series = {Lecture Notes in Computer Science},
address = {Luxor, Egypt},
month = dec,
OPTorganization = {},
publisher = {Springer},
OPTnote = {},
OPTannote = {},
abstract = {The process number is the number of requests that have to be simultaneously disturbed during a routing reconfiguration phase of a connection oriented network. From a graph theory point of view, it is similar to the node search number, and thus to the pathwidth. However they are not always equal in general graphs. Determining these parameters is in general NP-complete. In this paper, we characterize the cases in which the process number and the node search number are equal in trees. We also present a distributed algorithm to compute these parameters as well as the edge search number. This algorithm can be executed in an asynchronous environment, requires $n$ steps, an overall computation time of $O(n\log{n})$, and $n$ messages of size $\log_3{n}+2$. We then propose a distributed algorithm to update the process number (or the node search number, or the edge search number) of each component of a forest after addition or deletion of any edge. This second algorithm requires $O(D)$ steps, an overall computation time of $O(D\log{n})$, and $O(D)$ messages of size $\log_3{n}+3$, where $D$ is the diameter of the modified connected component. Finally, we show how to extend our algorithms to trees and forests of unknown size using messages of less than $2\alpha+5$ bits, where $\alpha\leq\log_3{n}$ is the parameter to be determined.},
url= {https://hal.inria.fr/inria-00288304},
pdf = {ftp://ftp-sop.inria.fr/mascotte/Publications/CHM08d.pdf},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
sorte = "conf-int",
}
-
D. Coudert,
F. Huc,
F. Peix,
and M.-E. Voge.
Reliability of Connections in Multilayer Networks under Shared Risk Groups and Costs Constraints.
In IEEE ICC,
number ON01-6,
Beijing, China,
pages 5170 - 5174,
May 2008.
[WWW
] [PDF
]
| Abstract: |
|
The notion of Shared Risk Resource Groups (SRRG) has been introduced to capture survivability issues when a set of resources may fail simultaneously. Applied to Wavelength Division Multiplexing Network (WDM), it expresses that some links and nodes may fail simultaneously. The reliability of a connection therefore depends on the number of SRRGs through which it is routed. Consequently, this number has to be minimized. This problem has been proved NP-complete and hard to approximate in general, even when routing a single request. Some heuristics using shortest paths have already been designed, however the cost (the usual routing cost, not in term of SRRG) was not part of the objective. In this paper we study the problem of minimizing a linear combination of the average number of SRRG per paths and the cost of the routing. The main result of our work is a column generation formulation that allows to solve efficiently the problem of maximizing the reliability of a set of connection requests in MPLS/WDM mesh networks with SRRGs while keeping the cost of the routing low. |
@inproceedings{CHPV08,
author = {D. Coudert and F. Huc and F. Peix and M.-E. Voge},
title = {Reliability of Connections in Multilayer Networks under Shared Risk Groups and Costs Constraints},
booktitle = {IEEE ICC},
number = {ON01-6},
pages = {5170 - 5174},
year = {2008},
month = may,
address = {Beijing, China},
abstract = { The notion of Shared Risk Resource Groups (SRRG) has been introduced to capture survivability issues when a set of resources may fail simultaneously. Applied to Wavelength Division Multiplexing Network (WDM), it expresses that some links and nodes may fail simultaneously. The reliability of a connection therefore depends on the number of SRRGs through which it is routed. Consequently, this number has to be minimized. This problem has been proved NP-complete and hard to approximate in general, even when routing a single request. Some heuristics using shortest paths have already been designed, however the cost (the usual routing cost, not in term of SRRG) was not part of the objective. In this paper we study the problem of minimizing a linear combination of the average number of SRRG per paths and the cost of the routing. The main result of our work is a column generation formulation that allows to solve efficiently the problem of maximizing the reliability of a set of connection requests in MPLS/WDM mesh networks with SRRGs while keeping the cost of the routing low. },
pdf = {ftp://ftp-sop.inria.fr/mascotte/personnel/David.Coudert/Publication/CHPV07-inria-00175813.pdf},
url = {http://hal.inria.fr/inria-00175813/en/},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
sorte = "conf-int",
}
-
O. Dalle,
B.P. Zeigler,
and G.A. Wainer.
Extending DEVS to support multiple occurrence in component-based simulation.
In S. J. Mason,
R. R. Hill,
L. Moench,
and O. Rose, editors,
Proceedings of the 2008 Winter Simulation Conference,
pages 10p,
December 2008.
[PDF
]
| Abstract: |
|
This paper presents a new extension of the DEVS formalism that allowsmultiple occurrences of a given instance of a DEV Scomponent?. This paper is a follow-up to a previous short paper in which the issue of supporting a new construction called ashared component was raised, in the case of a DEVS model. In thispaper, we first demonstrate, formally, that the multi-occurrence extended definition,that includes the case of shared components, is valid because anymodel that is built using this extended definition accepts an equivalent modelbuilt using standard DEVS. Then we recall the benefits of sharingcomponents for modeling, and further extend this analysis to the simulation area, byinvestigating how shared components can help to design bettersimulation engines. Finally, we describe an existing implementation ofa simulation software that fully supports this shared componentfeature, both at the modeling and simulation levels. |
@INPROCEEDINGS{DZW08,
AUTHOR = { O. Dalle and B.P. Zeigler and G.A. Wainer },
TITLE = { Extending {DEVS} to support multiple occurrence in component-based simulation },
BOOKTITLE = { Proceedings of the 2008 Winter Simulation Conference },
OPTCROSSREF = { },
OPTKEY = { },
PAGES = {10p },
YEAR = { 2008 },
EDITOR = { S. J. Mason and R. R. Hill and L. Moench and O. Rose },
OPTVOLUME = { },
OPTNUMBER = { },
OPTSERIES = { },
OPTADDRESS = { },
MONTH = dec,
OPTORGANIZATION = { },
OPTPUBLISHER = { },
NOTE = { },
OPTANNOTE = { },
PDF = { ftp://ftp-sop.inria.fr/mascotte/Publications/DZW08.pdf },
ABSTRACT = { This paper presents a new extension of the DEVS formalism that allowsmultiple occurrences of a given instance of a DEV Scomponent?. This paper is a follow-up to a previous short paper in which the issue of supporting a new construction called ashared component was raised, in the case of a DEVS model. In thispaper, we first demonstrate, formally, that the multi-occurrence extended definition,that includes the case of shared components, is valid because anymodel that is built using this extended definition accepts an equivalent modelbuilt using standard DEVS. Then we recall the benefits of sharingcomponents for modeling, and further extend this analysis to the simulation area, byinvestigating how shared components can help to design bettersimulation engines. Finally, we describe an existing implementation ofa simulation software that fully supports this shared componentfeature, both at the modeling and simulation levels. },
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
sorte = "conf-int",
}
-
F. Giroire,
J. Chandrashekar,
G. Iannaccone,
D. Papagiannaki,
E. Schooler,
and N. Taft.
The Cubicle vs. The Coffee Shop: Behavioral Modes in Enterprise End-Users.
In Proceeding of the Passive and Active Monitoring conference (PAM08),
volume 4979 of Lecture Notes in Computer Science,
pages 202-211,
2008.
Springer.
[PDF
]
| Abstract: |
|
Traditionally, user traffic profiling is performed by analyzing traffic traces collected on behalf of the user at aggregation points located in the middle of the network. However, the modern enterprise network has a highly mobile population that frequently moves in and out of its physical perimeter. Thus an in-the-network monitor is unlikely to capture full user activity traces when users move outside the enterprise perimeter. The distinct environments, such as the cubicle and the coffee shop (among others), that users visit, may each pose different constraints and lead to varied behavioral modes. It is thus important to ask: is the profile of a user constructed in one environment representative of the same user in another environment? In this paper, we answer in the negative for the mobile population of an enterprise. Using real corporate traces collected at nearly 400 end-hosts for approximately 5 weeks, we study how end-host usage differs across three environments: inside the enterprise, outside the enterprise but using a VPN, and entirely outside the enterprise network. Within these environments, we examine three types of features: (i) environment lifetimes, (ii) relative usage statistics of network services, and (iii) outlier detection thresholds as used for anomaly detection. We find significant diversity in end-host behavior across environments for many features, thus indicating that profiles computed for a user in one environment yield inaccurate representations of the same user in a different environment. |
@inproceedings{GCI+08,
title = {The Cubicle vs. The Coffee Shop: Behavioral Modes in Enterprise End-Users},
author = {F. Giroire and J. {C}handrashekar and G. Iannaccone and D. Papagiannaki and E. Schooler and N. Taft},
booktitle = {Proceeding of the Passive and Active Monitoring conference (PAM08)},
series={Lecture Notes in Computer Science},
volume={4979},
year={2008},
publisher={Springer},
pages = {202-211},
pdf = {http://www-sop.inria.fr/members/Frederic.Giroire/publis/GCI08.pdf},
abstract = {Traditionally, user traffic profiling is performed by analyzing traffic traces collected on behalf of the user at aggregation points located in the middle of the network. However, the modern enterprise network has a highly mobile population that frequently moves in and out of its physical perimeter. Thus an in-the-network monitor is unlikely to capture full user activity traces when users move outside the enterprise perimeter. The distinct environments, such as the cubicle and the coffee shop (among others), that users visit, may each pose different constraints and lead to varied behavioral modes. It is thus important to ask: is the profile of a user constructed in one environment representative of the same user in another environment? In this paper, we answer in the negative for the mobile population of an enterprise. Using real corporate traces collected at nearly 400 end-hosts for approximately 5 weeks, we study how end-host usage differs across three environments: inside the enterprise, outside the enterprise but using a VPN, and entirely outside the enterprise network. Within these environments, we examine three types of features: (i) environment lifetimes, (ii) relative usage statistics of network services, and (iii) outlier detection thresholds as used for anomaly detection. We find significant diversity in end-host behavior across environments for many features, thus indicating that profiles computed for a user in one environment yield inaccurate representations of the same user in a different environment.},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
sorte = "conf-int",
}
-
C. Gomes,
G. Huiban,
and H. Rivano.
A Branch-and-Price Approach to the Bandwidth Allocation Problem in Wireless Networks.
In International Symposium on Combinatorial Optimization (CO),
pages 1p,
March 2008.
Note: Abstract.
[PDF
]
@INPROCEEDINGS{GHR08,
author = {C. Gomes and G. Huiban and H. Rivano},
title = {A Branch-and-Price Approach to the Bandwidth Allocation Problem in Wireless Networks},
BOOKTITLE = {International Symposium on Combinatorial Optimization (CO)},
SCHOOL = {University of Warwick, Coventry, UK},
note = {Abstract},
MONTH = mar,
YEAR = {2008},
PAGES = {1p},
PDF = {ftp://ftp-sop.inria.fr/mascotte/Publications/GHR08.pdf},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
sorte = "conf-sa",
}
-
C. Gomes,
C. Molle,
and P. Reyes.
Optimal Design of Wireless Mesh Networks.
In 9èmes Journées Doctorales en Informatique et Réseaux (JDIR 2008),
Villeneuve d'Ascq, France,
pages 10p,
January 2008.
[WWW
] [PDF
]
| Abstract: |
|
Wireless Mesh Networks (WMNs) are cost-effective and provide an appealing answer to connectivity issues of ubiquitous computing. Unfortunately, wireless networks are known for strong waste of capacity when their size in- creases. Thus, a key challenge for network operators is to provide guaranteed quality of service. Maximizing network capacity requires to optimize jointly the gateways placement, the routing and the link scheduling taking interferences into account. We present MILP models for computing an optimal 802.11a or 802.16 WMN design providing max-min bandwidth guarantee. |
@InProceedings{GMR08,
author = {C. Gomes and C. Molle and P. Reyes},
title = {Optimal Design of Wireless Mesh Networks},
booktitle = {9\`emes Journ\'ees Doctorales en Informatique et R\'eseaux (JDIR 2008)},
pages = {10p},
year = {2008},
month = jan,
address = {Villeneuve d'Ascq, France},
abstract = {Wireless Mesh Networks (WMNs) are cost-effective and provide an appealing answer to connectivity issues of ubiquitous computing. Unfortunately, wireless networks are known for strong waste of capacity when their size in- creases. Thus, a key challenge for network operators is to provide guaranteed quality of service. Maximizing network capacity requires to optimize jointly the gateways placement, the routing and the link scheduling taking interferences into account. We present MILP models for computing an optimal 802.11a or 802.16 WMN design providing max-min bandwidth guarantee.},
url = {http://www2.lifl.fr/JDIR2008/},
pdf={ftp://ftp-sop.inria.fr/mascotte/Publications/GMR08.pdf},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={no},
sorte = "conf-nat",
}
-
C. Gomes,
S. Pérennes,
P. Reyes,
and H. Rivano.
Bandwidth Allocation in Radio Grid Networks.
In 10èmes Rencontres Francophones sur les Aspects Algorithmiques de Télécommunications (AlgoTel'08),
pages 4p,
May 2008.
[WWW
] [PDF
]
| Abstract: |
|
In this paper we give exact or almost exact bounds for the continuous gathering problem on grids. Under very general hypothesis on the traffic demand, we mainly prove that the throughput is determined by the bottleneck around the base station. We deal with two cases: the base station located in the center and in the corner. We use dual lower bounds and describe a protocol which is optimal when the traffic is uniform. |
@InProceedings{GPRR08,
author = {C. Gomes and S. P\'erennes and P. Reyes and H. Rivano},
title = {Bandwidth Allocation in Radio Grid Networks},
booktitle = {10\`emes Rencontres Francophones sur les Aspects Algorithmiques de T\'el\'ecommunications (AlgoTel'08)},
year = {2008},
pages = {4p},
month = may,
url = {http://algotel2008.irisa.fr/index.php},
pdf = {ftp://ftp-sop.inria.fr/mascotte/Publications/GPRR08.pdf},
abstract = {In this paper we give exact or almost exact bounds for the continuous gathering problem on grids. Under very general hypothesis on the traffic demand, we mainly prove that the throughput is determined by the bottleneck around the base station. We deal with two cases: the base station located in the center and in the corner. We use dual lower bounds and describe a protocol which is optimal when the traffic is uniform.},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={no},
sorte = "conf-nat",
}
-
C. Gomes,
S. Pérennes,
and H. Rivano.
Bottleneck Analysis for Routing and Call Scheduling in Multi-hop Wireless Networks.
In 4th IEEE Workshop on Broadband Wireless Access (BWA),
New-Orleans, US,
pages 6p,
December 2008.
[PDF
]
| Abstract: |
|
In this paper, we address the routing and call scheduling problem in which one has to find a minimum-length schedule of selected links in a TDMA (Time Division Multiple Access) based wireless network. As we deal with multi-hop networks, these selected links represent a routing solution (paths) providing enough capacity to achieve the routers requirements of bandwidth. We present a cross-layer formulation of the problem that computes joint routing and scheduling. We use a branch-and-price algorithm to solve optimally the problem. A column generation algorithm is used to cope with the exponential set of rounds. The branch-and-bound algorithm provides mono-routing. We run experiments on networks from the literature, with different number of gateways. Experimental results as well as theoretical insights let us conjecture that the bottleneck region analysis is enough to find the optimal solution. The Integer Round-Up Property (IRUP) seems to hold for our problem. |
@INPROCEEDINGS{GPR08b,
author ={C. Gomes and S. P\'erennes and H. Rivano},
title = {Bottleneck Analysis for Routing and Call Scheduling in Multi-hop Wireless Networks},
booktitle ={4th IEEE Workshop on Broadband Wireless Access (BWA)},
month = dec,
pages = {6p},
year ={2008},
address = {New-Orleans, US},
pdf = {ftp://ftp-sop.inria.fr/mascotte/Publications/GPR08b.pdf},
abstract = {In this paper, we address the routing and call scheduling problem in which one has to find a minimum-length schedule of selected links in a TDMA (Time Division Multiple Access) based wireless network. As we deal with multi-hop networks, these selected links represent a routing solution (paths) providing enough capacity to achieve the routers requirements of bandwidth. We present a cross-layer formulation of the problem that computes joint routing and scheduling. We use a branch-and-price algorithm to solve optimally the problem. A column generation algorithm is used to cope with the exponential set of rounds. The branch-and-bound algorithm provides mono-routing. We run experiments on networks from the literature, with different number of gateways. Experimental results as well as theoretical insights let us conjecture that the bottleneck region analysis is enough to find the optimal solution. The Integer Round-Up Property (IRUP) seems to hold for our problem.},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
sorte = "conf-int",
}
-
F. Havet,
B. Reed,
and J.-S. Sereni.
L(2,1)-labelling of graphs.
In Proceedings of the ACM-SIAM Symposium on Discrete Algorithm (SODA 2008),
pages 621-630,
January 2008.
[WWW
] [PDF
]
| Abstract: |
|
An $L(2,1)$-labelling of a graph is a function $f$ from the vertex set to the positive integers such that $|f(x)-f(y)|\geq 2$ if $\dist(x,y)=1$ and $|f(x)-f(y)|\geq 1$ if $\dist(x,y)=2$, where $\dist(u,v)$ is the distance between the two vertices~$u$ and~$v$ in the graph $G$. The \emph{span} of an $L(2,1)$-labelling $f$ is the difference between the largest and the smallest labels used by $f$ plus $1$. In 1992, Griggs and Yeh conjectured that every graph with maximum degree $\Delta\geq 2$ has an $L(2,1)$-labelling with span at most $\D2+1$. We settle this conjecture for $\D$ sufficiently large. |
@InProceedings{HRS08a,
author={F. Havet and B. Reed and J.-S. Sereni},
booktitle={Proceedings of the ACM-SIAM Symposium on Discrete Algorithm (SODA 2008)},
month=jan,
title={L(2,1)-labelling of graphs},
pages = {621-630},
year={2008},
URL={http://www.siam.org/meetings/da08/},
pdf = {ftp://ftp-sop.inria.fr/mascotte/Publications/HRS08.pdf},
abstract={An $L(2,1)$-labelling of a graph is a function $f$ from the vertex set to the positive integers such that $|f(x)-f(y)|\geq 2$ if $\dist(x,y)=1$ and $|f(x)-f(y)|\geq 1$ if $\dist(x,y)=2$, where $\dist(u,v)$ is the distance between the two vertices~$u$ and~$v$ in the graph $G$. The \emph{span} of an $L(2,1)$-labelling $f$ is the difference between the largest and the smallest labels used by $f$ plus $1$. In 1992, Griggs and Yeh conjectured that every graph with maximum degree $\Delta\geq 2$ has an $L(2,1)$-labelling with span at most $\D2+1$. We settle this conjecture for $\D$ sufficiently large.},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
sorte = "conf-int",
}
-
L. Hogie,
G. Danoy,
P. Bouvry,
and F. Guinand.
A Context-Aware Broadcast Protocol for DTNs.
In Modelling, Computation and Optimization in Information Systems and Management Sciences (MCO'08),
volume 14 of Communications in Computer and Information Science,
pages 507-519,
September 2008.
Springer.
[PDF
]
| Abstract: |
|
Delay Tolerant Networks (DTNs) are a sub-class of mobile ad hoc networks (MANETs). They are mobile wireless networks that feature inherent connection disruption. In particular such net- works are generally non-connected. In this paper we focus on defining a broadcast service which operate on DTNs. A number of protocols solving the problem of broadcasting across DTNs have been proposed in the past, but all of them exhibit a static behavior, i.e. they provide no control parameter. However, at the application level, flexible broadcasting schemes are desirable. In particular, it is important that the user (the source of the broadcast message) can control the way the message gets spread across the network. This paper introduces a new broadcasting protocol dedicated to DTNs, called Context-Aware Broadcasting Protocol (CABP), which adapts its greediness according to the "urgency" (priority) of the broadcast message. A formal presentation of its strategy is proposed and through preliminary experi- ments, the cost-effectiveness of CABP is enlightened. |
@INPROCEEDINGS{HDBG08,
OPTauthor = {L. Hogie and Gr{\'e}goire Danoy and Pascal Bouvry and and Fr{\'e}d{\'e}ric Guinand},
author = {L. Hogie and G. Danoy and P. Bouvry and F. Guinand},
title = {A Context-Aware Broadcast Protocol for {DTN}s},
booktitle = {Modelling, Computation and Optimization in Information Systems and Management Sciences (MCO'08)},
volume = {14},
series = {Communications in Computer and Information Science},
publisher = {Springer},
pages = {507-519},
year = {2008},
month = sep,
pdf = {ftp://ftp-sop.inria.fr/mascotte/Publications/HDBG08.pdf},
abstract = {Delay Tolerant Networks (DTNs) are a sub-class of mobile ad hoc networks (MANETs). They are mobile wireless networks that feature inherent connection disruption. In particular such net- works are generally non-connected. In this paper we focus on defining a broadcast service which operate on DTNs. A number of protocols solving the problem of broadcasting across DTNs have been proposed in the past, but all of them exhibit a static behavior, i.e. they provide no control parameter. However, at the application level, flexible broadcasting schemes are desirable. In particular, it is important that the user (the source of the broadcast message) can control the way the message gets spread across the network. This paper introduces a new broadcasting protocol dedicated to DTNs, called Context-Aware Broadcasting Protocol (CABP), which adapts its greediness according to the "urgency" (priority) of the broadcast message. A formal presentation of its strategy is proposed and through preliminary experi- ments, the cost-effectiveness of CABP is enlightened.},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
sorte = "conf-int",
}
-
C.-C. Huang,
T. Kavitha,
D. Michail,
and M. Nasre.
Bounded Unpopularity Matchings.
In 11th Scandinavian Workshop on Algorithm Theory (SWAT).,
volume 5124 of Lecture Notes in Computer Science,
pages 127-137,
July 2008.
| Abstract: |
|
We investigate the following problem: given a set of jobs and a set of people with preferences over the jobs, what is the optimal way of matching people to jobs? Here we consider the notion of popularity. A matching M is popular if there is no matching M' such that more people prefer M' to M than the other way around. Determining whether a given instance admits a popular matching and, if so, finding one, was studied in Abraham et al. . If there is no popular matching, a reasonable substitute is a matching whose unpopularity is bounded. We consider two measures of unpopularity - unpopularity factor denoted by u(M) and unpopularity margin denoted by g(M). McCutchen recently showed that computing a matching M with the minimum value of u(M) or g(M) is NP-hard, and that if G does not admit a popular matching, then we have Your browser may not support display of this image. for all matchings M in G. Here we show that a matching M that achieves u(M) = 2 can be computed in Your browser may not support display of this image.time (where m is the number of edges in G and n is the number of nodes) provided a certain graph H admits a matching that matches all people. We also describe a sequence of graphs: H = H2, H3,...,Hk such that if Hk admits a matching that matches all people, then we can compute in Your browser may not support display of this image.time a matching M such that Your browser may not support display of this image.and Your browser may not support display of this image.. Simulation results suggest that our algorithm finds a matching with low unpopularity. |
@InProceedings{HKMN08,
author = {C.-C. Huang and T. Kavitha and D. Michail and M. Nasre},
title = {Bounded Unpopularity Matchings},
booktitle = {11th Scandinavian Workshop on Algorithm Theory (SWAT).},
pages = {127-137},
volume = {5124},
series = {Lecture Notes in Computer Science},
month = jul,
year = {2008},
optpdf = {},
opturl = {},
abstract = {We investigate the following problem: given a set of jobs and a set of people with preferences over the jobs, what is the optimal way of matching people to jobs? Here we consider the notion of popularity. A matching M is popular if there is no matching M' such that more people prefer M' to M than the other way around. Determining whether a given instance admits a popular matching and, if so, finding one, was studied in Abraham et al. . If there is no popular matching, a reasonable substitute is a matching whose unpopularity is bounded. We consider two measures of unpopularity - unpopularity factor denoted by u(M) and unpopularity margin denoted by g(M). McCutchen recently showed that computing a matching M with the minimum value of u(M) or g(M) is NP-hard, and that if G does not admit a popular matching, then we have Your browser may not support display of this image. for all matchings M in G. Here we show that a matching M that achieves u(M) = 2 can be computed in Your browser may not support display of this image.time (where m is the number of edges in G and n is the number of nodes) provided a certain graph H admits a matching that matches all people. We also describe a sequence of graphs: H = H2, H3,...,Hk such that if Hk admits a matching that matches all people, then we can compute in Your browser may not support display of this image.time a matching M such that Your browser may not support display of this image.and Your browser may not support display of this image.. Simulation results suggest that our algorithm finds a matching with low unpopularity. },
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
sorte = "conf-int",
}
-
F. Huc,
C. Linhares-Sales,
and H. Rivano.
The Proportional Colouring Problem: Optimizing Buffers in Radio Mesh Networks.
In IV Latin-American Algorithms, Graphs, and Optimization Symposium (LAGOS 07),
volume 30 of Electronic Notes in Discrete Mathematics,
Puerto Varas, Chile,
pages 141--146,
February 2008.
Elsevier.
[PDF
]
| Abstract: |
|
In this paper, we consider a new edge colouring problem: the proportional edge-colouring. Given a graph $G$ with positive weights associated to its edges, we want to find a colouring which preserves the proportion given by the weights associated to each edge. If such colouring exists, we want to find one using a minimum number of colours. We proved that deciding if a weighted graph admits a proportional colouring is polynomial while determining its proportional chromatic index is NP-hard. In addition, we give a lower bound and an upper bound for this parameter that can be computed in polynomial time. We finally show a class of graphs and a class of weighted graphs for which we can exactly determine the proportional chromatic index. |
@InProceedings{HLR08,
author = {F. Huc and C. {Linhares-Sales} and H. Rivano},
title = {The Proportional Colouring Problem: Optimizing Buffers in Radio Mesh Networks},
OPTcrossref = {},
OPTkey = {},
booktitle = {IV Latin-American Algorithms, Graphs, and Optimization Symposium (LAGOS 07)},
pages = {141--146},
year = {2008},
OPTeditor = {},
volume = {30},
OPTnumber = {},
series = {Electronic Notes in Discrete Mathematics},
address = {Puerto Varas, Chile},
month = feb,
OPTorganization = {},
publisher = {Elsevier},
OPTnote = {},
OPTannote = {},
pdf = {ftp://ftp-sop.inria.fr/mascotte/Publications/HLR07.pdf},
abstract= {In this paper, we consider a new edge colouring problem: the proportional edge-colouring. Given a graph $G$ with positive weights associated to its edges, we want to find a colouring which preserves the proportion given by the weights associated to each edge. If such colouring exists, we want to find one using a minimum number of colours. We proved that deciding if a weighted graph admits a proportional colouring is polynomial while determining its proportional chromatic index is NP-hard. In addition, we give a lower bound and an upper bound for this parameter that can be computed in polynomial time. We finally show a class of graphs and a class of weighted graphs for which we can exactly determine the proportional chromatic index.},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
sorte = "conf-int",
}
-
D. Ilcinkas,
N. Nisse,
and D. Soguet.
Le cout de la monotonie dans les stratégies d'encerclement réparti.
In 10èmes Rencontres Francophones sur les Aspects Algorithmiques de Télécommunications (AlgoTel'08),
pages 4p,
2008.
[WWW
] [PDF
]
| Abstract: |
|
L'encerclement dans les r\'eseaux vise \`a r\'ealiser le nettoyage, par une \'equipe d'agents mobiles, d'un r\'eseau contamin\'e. La strat\'egie d'encerclement est calcul\'ee en temps r\'eel, par les agents eux mêmes, et doit v\'erifier les trois propri\'et\'es suivantes: (1)~{\it connexit\'e} : la zone nettoy\'ee doit toujours être connexe de fa\c{c}on \`a assurer des communications s\'ecuris\'ees entre les agents, (2)~{\it monotonie} : la zone nettoy\'ee ne doit jamais être recontamin\'ee, ce qui permet un temps de nettoyage polynomial en la taille du r\'eseau, et (3)~{\it optimalit\'e} : le nombre d'agents utilis\'es doit être le plus petit possible afin de minimiser la taille des ressources utilis\'ees. Etant donn\'e un graphe $G$, le plus petit nombre d'agents n\'ecessaire pour nettoyer $G$ de façon monotone connexe dans un contexte centralis\'e est not\'e $\mcs(G)$. Plusieurs protocoles r\'epartis ont \'et\'e propos\'e pour r\'esoudre le probl\`eme de l'encerclement dans les r\'eseaux. Blin {\it et al.} ont propos\'e un algorithme distribu\'e permettant \`a $\mcs(G)$ agents de d\'eterminer et de r\'ealiser une strat\'egie d'encerclement dans tout graphe inconnu $G$ (inconnu signifie que les agents n'ont aucune connaissance {\it a priori} concernant le graphe) [AlgoTel'06]. Cependant, la strat\'egie r\'ealis\'ee n'est pas monotone et peut prendre un temps exponentiel. Nisse et Soguet ont prouv\'e que, pour r\'esoudre le probl\`eme de l'encerclement dans les r\'eseaux, il est n\'ecessaire et suffisant de fournir $\Theta(n \log n)$ bits d'information aux agents par le biais d'un \'etiquetage des sommets du graphe [AlgoTel'07]. Ainsi, pour nettoyer un graphe inconnu de fa\c{c}on monotone et connexe, il est necessaire d'utiliser plus d'agents que l'optimal. Dans cet article, nous \'etudions la proportion d'agents suppl\'ementaires qui sont n\'ecessaires et suffisants pour nettoyer de façon monotone connexe r\'eparti tout graphe inconnu. Nous montrons que la contrainte de monotonie implique une augmentation drastique de ce nombre d'agents. Nous prouvons que tout protocole distribu\'e ayant pour but de nettoyer tout graphe inconnu de $n$ sommets de façon monotone connexe r\'eparti a un ratio comp\'etitif de $\Theta(\frac{n}{\log n})$. Plus pr\'ecis\'ement, nous prouvons que pour tout protocole distribu\'e $\cal P$, il existe une constante $c$ tel que pour tout $n$ suffisamment grand, il existe un graphe $G$ de $n$ sommets tel que $\cal P$ requiert au moins $c\frac{n}{\log n}\, \mcs(G)$ agents pour nettoyer $G$. De plus, nous proposons un protocole distribu\'e qui permet \`a $O(\frac{n}{\log n})\, \mcs(G)$ agents de nettoyer tout graphe inconnu $G$ de $n$ sommets, de façon monotone connexe r\'eparti. |
@InProceedings{INS08,
author = {D. Ilcinkas and N. Nisse and D. Soguet},
title = {Le cout de la monotonie dans les strat\'egies d'encerclement r\'eparti},
booktitle = {10\`emes Rencontres Francophones sur les Aspects Algorithmiques de T\'el\'ecommunications (AlgoTel'08)},
year = {2008},
pages = {4p},
url = {http://algotel2008.irisa.fr/index.php},
pdf = {http://www-sop.inria.fr/members/Nicolas.Nisse/publications/Algotel08.pdf},
abstract = {L'encerclement dans les r\'eseaux vise \`a r\'ealiser le nettoyage, par une \'equipe d'agents mobiles, d'un r\'eseau contamin\'e. La strat\'egie d'encerclement est calcul\'ee en temps r\'eel, par les agents eux mêmes, et doit v\'erifier les trois propri\'et\'es suivantes: (1)~{\it connexit\'e} : la zone nettoy\'ee doit toujours être connexe de fa\c{c}on \`a assurer des communications s\'ecuris\'ees entre les agents, (2)~{\it monotonie} : la zone nettoy\'ee ne doit jamais être recontamin\'ee, ce qui permet un temps de nettoyage polynomial en la taille du r\'eseau, et (3)~{\it optimalit\'e} : le nombre d'agents utilis\'es doit être le plus petit possible afin de minimiser la taille des ressources utilis\'ees. Etant donn\'e un graphe $G$, le plus petit nombre d'agents n\'ecessaire pour nettoyer $G$ de façon monotone connexe dans un contexte centralis\'e est not\'e $\mcs(G)$. Plusieurs protocoles r\'epartis ont \'et\'e propos\'e pour r\'esoudre le probl\`eme de l'encerclement dans les r\'eseaux. Blin {\it et al.} ont propos\'e un algorithme distribu\'e permettant \`a $\mcs(G)$ agents de d\'eterminer et de r\'ealiser une strat\'egie d'encerclement dans tout graphe inconnu $G$ (inconnu signifie que les agents n'ont aucune connaissance {\it a priori} concernant le graphe) [AlgoTel'06]. Cependant, la strat\'egie r\'ealis\'ee n'est pas monotone et peut prendre un temps exponentiel. Nisse et Soguet ont prouv\'e que, pour r\'esoudre le probl\`eme de l'encerclement dans les r\'eseaux, il est n\'ecessaire et suffisant de fournir $\Theta(n \log n)$ bits d'information aux agents par le biais d'un \'etiquetage des sommets du graphe [AlgoTel'07]. Ainsi, pour nettoyer un graphe inconnu de fa\c{c}on monotone et connexe, il est necessaire d'utiliser plus d'agents que l'optimal. Dans cet article, nous \'etudions la proportion d'agents suppl\'ementaires qui sont n\'ecessaires et suffisants pour nettoyer de façon monotone connexe r\'eparti tout graphe inconnu. Nous montrons que la contrainte de monotonie implique une augmentation drastique de ce nombre d'agents. Nous prouvons que tout protocole distribu\'e ayant pour but de nettoyer tout graphe inconnu de $n$ sommets de façon monotone connexe r\'eparti a un ratio comp\'etitif de $\Theta(\frac{n}{\log n})$. Plus pr\'ecis\'ement, nous prouvons que pour tout protocole distribu\'e $\cal P$, il existe une constante $c$ tel que pour tout $n$ suffisamment grand, il existe un graphe $G$ de $n$ sommets tel que $\cal P$ requiert au moins $c\frac{n}{\log n}\, \mcs(G)$ agents pour nettoyer $G$. De plus, nous proposons un protocole distribu\'e qui permet \`a $O(\frac{n}{\log n})\, \mcs(G)$ agents de nettoyer tout graphe inconnu $G$ de $n$ sommets, de façon monotone connexe r\'eparti.},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={no},
sorte = "conf-nat",
}
-
K. Kawarabayashi and B. Reed.
A nearly linear time algorithm for the half integral disjoint paths packing.
In Proceedings of the ACM-SIAM Symposium on Discrete Algorithm (SODA 2008),
pages 446-454,
2008.
[PDF
]
| Abstract: |
|
We consider the following problem, which is called the half integral k disjoint paths packing. Input: A graph G, k pair of vertices (s1, t1), (s2, t2),\cdots, (sk, tk) in G (which are sometimes called terminals). Output: Paths P1, \cdots, Pk in G such that Pi joins si and ti for i = 1,2,\cdots, k, and in addition, each vertex is on at most two of these paths. We present an O(n log n) time algorithm for this problem for fixed k. This improves a result by Kleinberg who gave an O(n3) algorithm for this problem. In fact, we also have algorithms running in O(n(1+\varepsilon)) time for any \varepsilon > 0 for these problems, if k is up to o((log log n)2/5) for general graphs, up to o((log n/(log log n))1/4) for planar graphs, and up to o((log n/g/(log log n/g))1/4) for graphs on the surface, where g is the Euler genus. Furthermore, if k is fixed, then we have linear time algorithms for the planar case and for the bounded genus case. We also obtain O(n log n) algorithms for several optimization problems related to the bounded unsplittable flow problem when the number of terminal pairs is bounded. These results can all carry over to problems involving edge capacities. |
@inproceedings{KaRe08b,
author = {K. Kawarabayashi and B. Reed},
title = {A nearly linear time algorithm for the half integral disjoint paths packing},
booktitle = {Proceedings of the ACM-SIAM Symposium on Discrete Algorithm (SODA 2008)},
year = {2008},
pages = {446-454},
abstract ={We consider the following problem, which is called the half integral k disjoint paths packing. Input: A graph G, k pair of vertices (s1, t1), (s2, t2),\cdots, (sk, tk) in G (which are sometimes called terminals). Output: Paths P1, \cdots, Pk in G such that Pi joins si and ti for i = 1,2,\cdots, k, and in addition, each vertex is on at most two of these paths. We present an O(n log n) time algorithm for this problem for fixed k. This improves a result by Kleinberg who gave an O(n3) algorithm for this problem. In fact, we also have algorithms running in O(n(1+\varepsilon)) time for any \varepsilon > 0 for these problems, if k is up to o((log log n)2/5) for general graphs, up to o((log n/(log log n))1/4) for planar graphs, and up to o((log n/g/(log log n/g))1/4) for graphs on the surface, where g is the Euler genus. Furthermore, if k is fixed, then we have linear time algorithms for the planar case and for the bounded genus case. We also obtain O(n log n) algorithms for several optimization problems related to the bounded unsplittable flow problem when the number of terminal pairs is bounded. These results can all carry over to problems involving edge capacities.},
pdf = {ftp://ftp-sop.inria.fr/mascotte/Publications/KaRe08b.pdf},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
sorte = "conf-int",
}
-
Z. Li and B. Reed.
Optimization and Recognition for ${K}_5$-minor Free Graphs in Linear Time.
In Proceedings of LATIN,
pages 206-215,
2008.
@inproceedings{LiRe08,
author = {Z. Li and B. Reed},
title = {Optimization and Recognition for ${K}_5$-minor Free Graphs in Linear Time},
booktitle = {Proceedings of LATIN},
year = {2008},
pages = {206-215},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
sorte = "conf-int",
}
-
C. Molle,
F. Peix,
S. Pérennes,
and H. Rivano.
Formulation en Coupe/Rounds pour le Routage dans les réseaux radio maillés.
In 10èmes Rencontres Francophones sur les Aspects Algorithmiques de Télécommunications (AlgoTel'08),
pages 4p,
May 2008.
[WWW
] [PDF
]
| Abstract: |
|
Un des probl\`emes au c\oe ur de l'optimisation des r\'eseaux radio maill\'es est le routage et l'ordonnancement d'appels. Dans cet article, nous \'etudions une relaxation classique de ce probl\`eme qui consiste \`a r\'epartir la capacit\'e entre les ensembles d'appels simultan\'es de mani\`ere \`a garantir un d\'ebit suffisant \`a chaque routeur du r\'eseau. Nous introduisons une nouvelle formulation s'affranchissant du routage pour se concentrer sur la capacit\'e de transport disponible sur les coupes du r\'eseau. Nous prouvons son \'equivalence avec les formulations existantes et pr\'esentons un processus efficace de r\'esolution par g\'en\'eration crois\'ee de lignes et de colonnes. |
@InProceedings{MPPR08a,
author = {C. Molle and F. Peix and S. P\'erennes and H. Rivano},
title = {Formulation en Coupe/Rounds pour le Routage dans les r\'eseaux radio maill\'es},
booktitle = {10\`emes Rencontres Francophones sur les Aspects Algorithmiques de T\'el\'ecommunications (AlgoTel'08)},
year = {2008},
pages = {4p},
month = may,
url = {http://algotel2008.irisa.fr/index.php},
pdf = {ftp://ftp-sop.inria.fr/mascotte/Publications/MPPR08.pdf},
abstract = {Un des probl\`emes au c\oe ur de l'optimisation des r\'eseaux radio maill\'es est le routage et l'ordonnancement d'appels. Dans cet article, nous \'etudions une relaxation classique de ce probl\`eme qui consiste \`a r\'epartir la capacit\'e entre les ensembles d'appels simultan\'es de mani\`ere \`a garantir un d\'ebit suffisant \`a chaque routeur du r\'eseau. Nous introduisons une nouvelle formulation s'affranchissant du routage pour se concentrer sur la capacit\'e de transport disponible sur les coupes du r\'eseau. Nous prouvons son \'equivalence avec les formulations existantes et pr\'esentons un processus efficace de r\'esolution par g\'en\'eration crois\'ee de lignes et de colonnes.},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={no},
sorte = "conf-nat",
}
-
C. Molle,
F. Peix,
S. Pérennes,
and H. Rivano.
Optimal Routing and Call Scheduling in Wireless Mesh Networks with Localized Information.
In C. Kaklamanis and F. Nielson, editors,
the fourth Symposium on Trustworthy Global Computing (TGC 2008),
volume 5474 of Lecture Notes in Computer Science,
Barcelona, Spain,
pages 171-185,
November 2008.
[WWW
] [PDF
]
| Abstract: |
|
Wireless mesh network performance issues have been modeled by the Joint Routing and Scheduling Problem (JRSP) in which a maximum per-flow throughput is computed. A classical relaxation of JRSP, denoted as the Round Weighting Problem (RWP), consists in assigning enough weight to sets of compatible simultaneous transmissions (rounds), while minimizing the sum of them, thus maximizing the relative weight of each round, which model the throughput. In this work, we present a new linear formulation of RWP focused on the transport capacity over the network cuts, thus eliminating the routing. We prove its equivalence with existing formulations with flows and formalize a primal-dual algorithm that quickly solves this problem using a cross line and column generations process. An asset of this formulation is to point out a bounded region, a "bottleneck" of the network, that is enough to optimize in order to get the optimal RWP of the whole network. The size and location of this area is experimentally made through simulations, highlighting a few hop distant neighborhood of the mesh gateways. One would then apply approximated methods outside this zone to route the traffic without degrading the achieved capacity. |
@inProceedings{MPPR08b,
author = {C. Molle and F. Peix and S. P\'erennes and H. Rivano},
title = {Optimal Routing and Call Scheduling in Wireless Mesh Networks with Localized Information},
booktitle = {the fourth Symposium on Trustworthy Global Computing (TGC 2008)},
year = {2008},
month = nov,
pages = {171-185},
editor = {C. Kaklamanis and F. Nielson},
volume = {5474},
series = {Lecture Notes in Computer Science},
address = {Barcelona, Spain},
url = {http://albcom.lsi.upc.edu/tgc2008/},
abstract = {Wireless mesh network performance issues have been modeled by the Joint Routing and Scheduling Problem (JRSP) in which a maximum per-flow throughput is computed. A classical relaxation of JRSP, denoted as the Round Weighting Problem (RWP), consists in assigning enough weight to sets of compatible simultaneous transmissions (rounds), while minimizing the sum of them, thus maximizing the relative weight of each round, which model the throughput. In this work, we present a new linear formulation of RWP focused on the transport capacity over the network cuts, thus eliminating the routing. We prove its equivalence with existing formulations with flows and formalize a primal-dual algorithm that quickly solves this problem using a cross line and column generations process. An asset of this formulation is to point out a bounded region, a "bottleneck" of the network, that is enough to optimize in order to get the optimal RWP of the whole network. The size and location of this area is experimentally made through simulations, highlighting a few hop distant neighborhood of the mesh gateways. One would then apply approximated methods outside this zone to route the traffic without degrading the achieved capacity.},
pdf = {ftp://ftp-sop.inria.fr/mascotte/Publications/MPPR08b.pdf},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
sorte = "conf-int",
}
-
C. Molle,
F. Peix,
and H. Rivano.
Génération de colonnes pour le routage et l'ordonnancement dans les réseaux radio maillés.
In Colloque francophone sur l'ingénierie des protocoles (CFIP 2008),
pages 12p,
March 2008.
Note: Best student paper award.
[WWW
] [PDF
]
| Abstract: |
|
Dans cet article, nous \'etudions la capacit\'e des r\'eseaux radio maill\'es d\'edi\'es à l'acc\`es à Internet. Nous nous pla\c ons dans l'hypoth\`ese d'un r\'eseau synchrone fonctionnant en r\'egime permanent o\`u les transmissions partagent un m\^eme canal radio. Le routage et l'ordonnancement des transmissions ont un impact majeur sur la capacit\'e fournie aux clients. Une optimisation jointe de ces deux probl\`emes permet de prendre en compte dans le routage les contentions dues aux interf\'erences radio. Nous en d\'eveloppons des formulations exactes en programmation lin\'eaire. Nous pr\'esentons ensuite un processus de g\'en\'eration de colonnes r\'esolvant une relaxation du probl\`eme. Ainsi, nous contournons l'\'ecueil de la combinatoire des transmissions r\'ealisables simultan\'ement pour permettre de calculer des solutions sur des r\'eseaux de grande taille. Des simulations sont effectu\'ees sur des topologies al\'eatoires. L'\'evolution de la capacit\'e d'un r\'eseau maill\'e avec ses param\`etres, ainsi que la complexit\'e algorithmique du probl\`eme sont discut\'ees. |
@InProceedings{MPR08a,
author = {C. Molle and F. Peix and H. Rivano},
title = {G\'en\'eration de colonnes pour le routage et l'ordonnancement dans les r\'eseaux radio maill\'es},
booktitle = {Colloque francophone sur l'ing\'enierie des protocoles ({CFIP} 2008)},
pages = {12p},
month = mar,
year = {2008},
pdf = {ftp://ftp-sop.inria.fr/mascotte/Publications/MPR08.pdf},
url = {http://cfip2008.imag.fr/wp/},
note = {Best student paper award},
abstract = {Dans cet article, nous \'etudions la capacit\'e des r\'eseaux radio maill\'es d\'edi\'es à l'acc\`es à Internet. Nous nous pla\c ons dans l'hypoth\`ese d'un r\'eseau synchrone fonctionnant en r\'egime permanent o\`u les transmissions partagent un m\^eme canal radio. Le routage et l'ordonnancement des transmissions ont un impact majeur sur la capacit\'e fournie aux clients. Une optimisation jointe de ces deux probl\`emes permet de prendre en compte dans le routage les contentions dues aux interf\'erences radio. Nous en d\'eveloppons des formulations exactes en programmation lin\'eaire. Nous pr\'esentons ensuite un processus de g\'en\'eration de colonnes r\'esolvant une relaxation du probl\`eme. Ainsi, nous contournons l'\'ecueil de la combinatoire des transmissions r\'ealisables simultan\'ement pour permettre de calculer des solutions sur des r\'eseaux de grande taille. Des simulations sont effectu\'ees sur des topologies al\'eatoires. L'\'evolution de la capacit\'e d'un r\'eseau maill\'e avec ses param\`etres, ainsi que la complexit\'e algorithmique du probl\`eme sont discut\'ees.},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={no},
sorte = "conf-nat",
}
-
C. Molle,
F. Peix,
and H. Rivano.
An optimization framework for the joint routing and scheduling in wireless mesh networks.
In Proc. 19th IEEE International Symposium on Personal, Indoor and Mobile Radio Communications (PIMRC'08),
Cannes, France,
September 2008.
[WWW
] [PDF
]
| Abstract: |
|
In this paper, we address the problem of computing the transport capacity of Wireless Mesh Networks dedicated to Internet access. Routing and transmission scheduling have a major impact on the capacity provided to the clients. A cross- layer optimization of these problems allows the routing to take into account contentions due to radio interferences. We develop exact linear programs and provide an efficient column generation process computing a relaxation of the problem. It allows to work around the combinatoric of simultaneously achievable transmissions, hence computing solutions on large networks. Our approach is validated through extensive simulations. Evolution of the capacity of a mesh network with its parameters, as well as the algorithmic complexity are then discussed. We conjecture that the problem can be solved in polynomial time and that the gateway placement problem is only subject to localized constraints. |
@INPROCEEDINGS{MPR08b,
author = {C. Molle and F. Peix and H. Rivano},
TITLE = {An optimization framework for the joint routing and scheduling in wireless mesh networks},
BOOKTITLE = { Proc. 19th IEEE International Symposium on Personal, Indoor and Mobile Radio Communications (PIMRC'08) },
MONTH = sep,
YEAR = { 2008 },
ADDRESS = { Cannes, France },
URL = { http://www.pimrc2008.org },
pdf = {ftp://ftp-sop.inria.fr/mascotte/Publications/MPR08b.pdf},
abstract = {In this paper, we address the problem of computing the transport capacity of Wireless Mesh Networks dedicated to Internet access. Routing and transmission scheduling have a major impact on the capacity provided to the clients. A cross- layer optimization of these problems allows the routing to take into account contentions due to radio interferences. We develop exact linear programs and provide an efficient column generation process computing a relaxation of the problem. It allows to work around the combinatoric of simultaneously achievable transmissions, hence computing solutions on large networks. Our approach is validated through extensive simulations. Evolution of the capacity of a mesh network with its parameters, as well as the algorithmic complexity are then discussed. We conjecture that the problem can be solved in polynomial time and that the gateway placement problem is only subject to localized constraints.},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
sorte = "conf-int",
}
-
C. Molle and M.-E. Voge.
Influence des acquittements sur la capacité des réseaux radio maillés.
In 10èmes Rencontres Francophones sur les Aspects Algorithmiques de Télécommunications (AlgoTel'08),
pages 4p,
May 2008.
[WWW
] [PDF
]
| Abstract: |
|
A la veille du d\'eploiement de l'informatique ubiquitaire, la performance des r\'eseaux radio est un enjeu \'economique majeur. Parmi les indicateurs de performance, la {\it capacit\'e}, ou volume maximal de trafic que peut \'ecouler le r\'eseau en un temps fix\'e, est essentielle. Dans cet article nous \'evaluons le gain en capacit\'e induit par la suppression des acquittements au niveau MAC en r\'esolvant un mod\`ele lin\'eaire par g\'en\'eration de colonnes. |
@InProceedings{MoVo08,
author = {C. Molle and M.-E. Voge},
title = {Influence des acquittements sur la capacit\'e des r\'eseaux radio maill\'es},
booktitle = {10\`emes Rencontres Francophones sur les Aspects Algorithmiques de T\'el\'ecommunications (AlgoTel'08)},
year = {2008},
pages = {4p},
month = may,
url = {http://algotel2008.irisa.fr/index.php},
pdf = {ftp://ftp-sop.inria.fr/mascotte/Publications/MoVo08.pdf},
abstract = {A la veille du d\'eploiement de l'informatique ubiquitaire, la performance des r\'eseaux radio est un enjeu \'economique majeur. Parmi les indicateurs de performance, la {\it capacit\'e}, ou volume maximal de trafic que peut \'ecouler le r\'eseau en un temps fix\'e, est essentielle. Dans cet article nous \'evaluons le gain en capacit\'e induit par la suppression des acquittements au niveau MAC en r\'esolvant un mod\`ele lin\'eaire par g\'en\'eration de colonnes.},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={no},
sorte = "conf-nat",
}
-
J. Monteiro.
The use of Evolving Graph Combinatorial Model in Routing Protocols for Dynamic Networks.
In Proceedings of the XV Concurso Latinoamericano de Tesis de Maestrìa (CLEI'08),
Santa Fe, Argentina,
pages 41--57,
September 2008.
Note: Third prize in the CLEI'08 Master's Thesis Contests.
[PDF
]
| Abstract: |
|
The assessment of routing protocols for ad hoc networks is a difficult task, due to the networksâ highly dynamic behavior and the absence of benchmarks. Recently, a graph theoretic model â the evolving graphs â was proposed to help capture the network topology changes during time, with predictable dynamics at least. The algorithms and insights obtained through this model are theoretically very effcient and intriguing. However, there is no study about the use of such theoretical results into practical situations. We used the NS2 network simulator to first implement an evolving graph based routing protocol, and then used it as a benchmark when comparing four ma jor ad-hoc routing pro- tocols. Interestingly, our experiments showed that evolving graphs have the potential to be an effective and powerful tool. In order to make this model widely applicable, however, some practical issues still have to be addressed and incorporated into the model. |
@inproceedings{Mon08,
Author = {J. Monteiro},
title = {The use of Evolving Graph Combinatorial Model in Routing Protocols for Dynamic Networks},
booktitle = {Proceedings of the XV Concurso Latinoamericano de Tesis de Maestr\'ia ({CLEI}'08)},
month = sep,
year = {2008},
pages = {41--57},
address = {Santa Fe, Argentina},
note = {Third prize in the CLEI'08 Master's Thesis Contests},
abstract = { The assessment of routing protocols for ad hoc networks is a difficult task, due to the networksâ highly dynamic behavior and the absence of benchmarks. Recently, a graph theoretic model â the evolving graphs â was proposed to help capture the network topology changes during time, with predictable dynamics at least. The algorithms and insights obtained through this model are theoretically very effcient and intriguing. However, there is no study about the use of such theoretical results into practical situations. We used the NS2 network simulator to first implement an evolving graph based routing protocol, and then used it as a benchmark when comparing four ma jor ad-hoc routing pro- tocols. Interestingly, our experiments showed that evolving graphs have the potential to be an effective and powerful tool. In order to make this model widely applicable, however, some practical issues still have to be addressed and incorporated into the model.},
pdf = {ftp://ftp-sop.inria.fr/mascotte/Publications/Mon08.pdf},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
sorte = "conf-int",
}
-
X. Muñoz and I. Sau.
Traffic Grooming in Unidirectional WDM Rings with Bounded-Degree Request Graph.
In 34th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2008),
volume 5344 of Lecture Notes in Computer Science,
pages 300-311,
June 2008.
[PDF
]
| Abstract: |
|
Traffic grooming is a major issue in optical networks. It refers to grouping low rate signals into higher speed streams, in order to reduce the equipment cost. In SONET WDM networks, this cost is mostly given by the number of electronic terminations, namely ADMs. We consider the case when the topology is a unidirectional ring. In graph-theoretical terms, the traffic grooming problem in this case consists in partitioning the edges of a request graph into subgraphs with a maximum number of edges, while minimizing the total number of vertices of the decomposition. We consider the case when the request graph has bounded maximum degree $\Delta$, and our aim is to design a network being able to support any request graph satisfying the degree constraints. The existing theoretical models in the literature are much more rigid, and do not allow such adaptability. We formalize the problem, and solve the cases $\Delta=2$ (for all values of $C$) and $\Delta = 3$ (except the case $C=4$). We also provide lower and upper bounds for the general case. |
@INPROCEEDINGS{MuSa08b,
title = {Traffic Grooming in Unidirectional {WDM} Rings with Bounded-Degree Request Graph},
author = {X. Mu{\~n}oz and I. Sau},
booktitle = {34th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2008)},
year = {2008},
series = {Lecture Notes in Computer Science},
volume = {5344},
pages = {300-311},
month = jun,
location = {Durham University, U.K.},
abstract = {Traffic grooming is a major issue in optical networks. It refers to grouping low rate signals into higher speed streams, in order to reduce the equipment cost. In SONET WDM networks, this cost is mostly given by the number of electronic terminations, namely ADMs. We consider the case when the topology is a unidirectional ring. In graph-theoretical terms, the traffic grooming problem in this case consists in partitioning the edges of a request graph into subgraphs with a maximum number of edges, while minimizing the total number of vertices of the decomposition. We consider the case when the request graph has bounded maximum degree $\Delta$, and our aim is to design a network being able to support any request graph satisfying the degree constraints. The existing theoretical models in the literature are much more rigid, and do not allow such adaptability. We formalize the problem, and solve the cases $\Delta=2$ (for all values of $C$) and $\Delta = 3$ (except the case $C=4$). We also provide lower and upper bounds for the general case.},
pdf = {http://www-sop.inria.fr/members/Ignasi.Sauvalls/Pubs/MuSa08.pdf},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
sorte = "conf-int",
}
-
N. Nisse and K. Suchan.
Voleur véloce dans un réseau planaire.
In 10èmes Rencontres Francophones sur les Aspects Algorithmiques de Télécommunications (AlgoTel'08),
pages 4p,
2008.
[WWW
] [PDF
]
| Abstract: |
|
D\'efini par Nowakowski et Winkler et, ind\'ependament, par Quilliot (1983), le jeu des gendarmes et du voleur impliquent deux joueurs qui jouent \`a tour de r\^ole dans un graphe. Le premier d\'eplace les gendarmes le long des ar\^etes du graphe, puis c'est au tour du second qui d\'eplace le voleur. Le but des gendarmes est d'attraper le voleur, tandis que ce dernier essaie d'\'eviter la capture ind\'efiniment. Le probl\`eme dans ce contexte est de minimiser le nombre de gendarmes n\'ecessaires pour capturer le voleur. Ce nombre s'appelle {\it l'indice d'\'evasion} du graphe ({\it cop-number} en anglais). Si les gendarmes et le voleur ont la m\^eme vitesse, Schr\"oder (2001) a prouv\'e que $3+\frac{3}{2}g$ gendarmes suffisent \`a capturer tout voleur dans un graphe de {\it genre} born\'e $g$. En particulier, cela signifie que la capture d'un voleur dans un graphe {\it planaire} est facile puisque $3$ gendarmes suffisent (en fait deux gendarmes sont suffisants dans toute grille). Dans ce travail, nous aidons le voleur en lui permettant de ce d\'eplacer plus vite que les gendarmes. Nous montrons que cela conduit \`a une augmentation drastique du nombre de gendarmes. Plus pr\'ecisement, nous prouvons que $\Omega(\sqrt{\log n})$ gendarmes sont n\'ecessaires pour capturer un voleur v\'eloce dans une grille carr\'ee de c\^ot\'e $n$. La preuve que nous proposons consiste en une \'el\'egante et simple strat\'egie d'\'evasion pour le voleur. Il est alors int\'eressant de savoir si le fait qu'un graphe planaire $H$ ait un indice d'\'evasion \'elev\'e est li\'e au fait que $H$ ``contient'' une large grille $G$. Nous montrons que ce n'est pas la cas lorsque la notion de contenance correspond \`a la notion de minoration topologique (c'est \`a dire si $G$ peut \^etre obtenu de $H$ en rempla\c{c}ant des chemins dont les sommets internes sont de degr\'e deux, par des ar\^etes). Cependant, nous prouvons que si $H$ planaire contient une large grille comme sous-graphe induit, alors son indice d'\'evasion est \'elev\'e. Notons que ce dernier r\'esultat n'est pas vrai dans le cas d'un graphe $H$ non planaire. |
@InProceedings{NiSu08b,
author = {N. Nisse and K. Suchan},
title = {Voleur v\'eloce dans un r\'eseau planaire},
booktitle = {10\`emes Rencontres Francophones sur les Aspects Algorithmiques de T\'el\'ecommunications (AlgoTel'08)},
year = {2008},
pages = {4p},
url = {http://algotel2008.irisa.fr/index.php},
pdf = {http://www-sop.inria.fr/members/Nicolas.Nisse/publications/Algotel08a.pdf},
abstract = {D\'efini par Nowakowski et Winkler et, ind\'ependament, par Quilliot (1983), le jeu des gendarmes et du voleur impliquent deux joueurs qui jouent \`a tour de r\^ole dans un graphe. Le premier d\'eplace les gendarmes le long des ar\^etes du graphe, puis c'est au tour du second qui d\'eplace le voleur. Le but des gendarmes est d'attraper le voleur, tandis que ce dernier essaie d'\'eviter la capture ind\'efiniment. Le probl\`eme dans ce contexte est de minimiser le nombre de gendarmes n\'ecessaires pour capturer le voleur. Ce nombre s'appelle {\it l'indice d'\'evasion} du graphe ({\it cop-number} en anglais). Si les gendarmes et le voleur ont la m\^eme vitesse, Schr\"oder (2001) a prouv\'e que $3+\frac{3}{2}g$ gendarmes suffisent \`a capturer tout voleur dans un graphe de {\it genre} born\'e $g$. En particulier, cela signifie que la capture d'un voleur dans un graphe {\it planaire} est facile puisque $3$ gendarmes suffisent (en fait deux gendarmes sont suffisants dans toute grille). Dans ce travail, nous aidons le voleur en lui permettant de ce d\'eplacer plus vite que les gendarmes. Nous montrons que cela conduit \`a une augmentation drastique du nombre de gendarmes. Plus pr\'ecisement, nous prouvons que $\Omega(\sqrt{\log n})$ gendarmes sont n\'ecessaires pour capturer un voleur v\'eloce dans une grille carr\'ee de c\^ot\'e $n$. La preuve que nous proposons consiste en une \'el\'egante et simple strat\'egie d'\'evasion pour le voleur. Il est alors int\'eressant de savoir si le fait qu'un graphe planaire $H$ ait un indice d'\'evasion \'elev\'e est li\'e au fait que $H$ ``contient'' une large grille $G$. Nous montrons que ce n'est pas la cas lorsque la notion de contenance correspond \`a la notion de minoration topologique (c'est \`a dire si $G$ peut \^etre obtenu de $H$ en rempla\c{c}ant des chemins dont les sommets internes sont de degr\'e deux, par des ar\^etes). Cependant, nous prouvons que si $H$ planaire contient une large grille comme sous-graphe induit, alors son indice d'\'evasion est \'elev\'e. Notons que ce dernier r\'esultat n'est pas vrai dans le cas d'un graphe $H$ non planaire.},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={no},
sorte = "conf-nat",
}
-
N. Nisse and K. Suchan.
Fast Robber in Planar Graphs.
In Proceedings of the 34th International Workshop on Graph-Theoretic Concepts in Computer Science (WG),
volume 5344 of Lecture Notes in Computer Science,
pages 33-44,
2008.
[WWW
] [PDF
]
| Abstract: |
|
In the {\it cops and robber game}, two players play alternately by moving their tokens along the edges of a graph. The first one plays with the {\it cops} and the second one with one {\it robber}. The cops aim at capturing the robber, while the robber tries to infinitely evade the cops. The main problem consists in minimizing the number of cops used to capture the robber in a graph. This minimum number is called the {\it cop-number} of the graph. If the cops and the robber have the same velocity, $3+\frac{3}{2}g$ cops are sufficient to capture one robber in any graph with genus $g$ (Schr\"oder, 2001). In the particular case of a grid, $2$ cops are sufficient. We investigate the game in which the robber is slightly faster than the cops. In this setting, we prove that the cop-number of planar graphs becomes unbounded. More precisely, we prove that $\Omega(\sqrt{\log n})$ cops are necessary to capture a fast robber in the $n \times n$ square-grid. This proof consists in designing an elegant evasion-strategy for the robber. Then, it is interesting to ask whether a high value of the cop-number of a planar graph $H$ is related to a large grid $G$ somehow contained in $H$. We prove that it is not the case when the notion of containment is related to the classical transformations of edge removal, vertex removal, and edge contraction. For instance, we prove that there are graphs with cop-number at most $2$ and that are subdivisions of arbitrary large grid. On the positive side, we prove that, if $H$ planar contains a large grid as an induced subgraph, then $H$ has large cop-number. Note that, generally, the cop-number of a graph $H$ is not closed by taking induced subgraphs $G$, even if $H$ is planar and $G$ is an distance-hereditary induced-subgraph. |
@inproceedings{NiSu08a,
author = {N. Nisse and K. Suchan},
title = {Fast Robber in Planar Graphs},
booktitle = {Proceedings of the 34th International Workshop on Graph-Theoretic Concepts in Computer Science (WG)},
year = {2008},
pages = {33-44},
series = {Lecture Notes in Computer Science},
volume = {5344},
abstract = {In the {\it cops and robber game}, two players play alternately by moving their tokens along the edges of a graph. The first one plays with the {\it cops} and the second one with one {\it robber}. The cops aim at capturing the robber, while the robber tries to infinitely evade the cops. The main problem consists in minimizing the number of cops used to capture the robber in a graph. This minimum number is called the {\it cop-number} of the graph. If the cops and the robber have the same velocity, $3+\frac{3}{2}g$ cops are sufficient to capture one robber in any graph with genus $g$ (Schr\"oder, 2001). In the particular case of a grid, $2$ cops are sufficient. We investigate the game in which the robber is slightly faster than the cops. In this setting, we prove that the cop-number of planar graphs becomes unbounded. More precisely, we prove that $\Omega(\sqrt{\log n})$ cops are necessary to capture a fast robber in the $n \times n$ square-grid. This proof consists in designing an elegant evasion-strategy for the robber. Then, it is interesting to ask whether a high value of the cop-number of a planar graph $H$ is related to a large grid $G$ somehow contained in $H$. We prove that it is not the case when the notion of containment is related to the classical transformations of edge removal, vertex removal, and edge contraction. For instance, we prove that there are graphs with cop-number at most $2$ and that are subdivisions of arbitrary large grid. On the positive side, we prove that, if $H$ planar contains a large grid as an induced subgraph, then $H$ has large cop-number. Note that, generally, the cop-number of a graph $H$ is not closed by taking induced subgraphs $G$, even if $H$ is planar and $G$ is an distance-hereditary induced-subgraph.},
url = {http://www.dur.ac.uk/wg.2008/},
pdf = {http://www-sop.inria.fr/members/Nicolas.Nisse/publications/wg08.pdf},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
sorte = "conf-int",
}
-
J. Ribault and O. Dalle.
Enabling advanced simulation scenarios with new software engineering techniques.
In 20th European Modeling and Simulation Symposium (EMSS 2008),
Briatico, Italy,
pages 6p,
2008.
[PDF
]
| Abstract: |
|
In this paper, we introduce new techniques in the field of simulationto help in the process of building advanced simulation scenarios usingpreexisting simulation components. The first technique consists in using the Aspect Oriented Programming? paradigm to capture some of the private data of anexisting model component. The second one is an Architecture Description Language (ADL) designed for the Fractal component model, that offers definition overloading and extension mechanisms similar to those found in traditional Object Oriented languages.The benefits of using both techniques are illustrated by simple usecases of network security studies. |
@INPROCEEDINGS{RiDa08,
AUTHOR = { J. Ribault and O. Dalle},
TITLE = { Enabling advanced simulation scenarios with new software engineering techniques },
BOOKTITLE = { 20th European Modeling and Simulation Symposium (EMSS 2008) },
OPTCROSSREF = { },
OPTKEY = { },
PAGES = {6p},
YEAR = { 2008 },
OPTEDITOR = { },
OPTVOLUME = { },
OPTNUMBER = { },
OPTSERIES = { },
ADDRESS = { Briatico, Italy },
OPTMONTH = { },
OPTORGANIZATION = { },
OPTPUBLISHER = { },
OPTANNOTE = { },
PDF = { ftp://ftp-sop.inria.fr/mascotte/Publications/RiDa08.pdf },
ABSTRACT = { In this paper, we introduce new techniques in the field of simulationto help in the process of building advanced simulation scenarios usingpreexisting simulation components. The first technique consists in using the Aspect Oriented Programming? paradigm to capture some of the private data of anexisting model component. The second one is an Architecture Description Language (ADL) designed for the Fractal component model, that offers definition overloading and extension mechanisms similar to those found in traditional Object Oriented languages.The benefits of using both techniques are illustrated by simple usecases of network security studies. },
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
sorte = "conf-int",
}
-
E. Altman,
P. Nain,
and J-C. Bermond.
Distributed Storage Management of Evolving Files in Delay Tolerant Ad Hoc Networks.
Research Report RR-6645,
INRIA,
September 2008.
[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 single source which at some points in time makes available a new version of a 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 (static) and state-dependent (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 q. 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. |
@TechReport{ANB08,
author = {E. Altman and P. Nain and J-C. Bermond},
title = {Distributed Storage Management of Evolving Files in Delay Tolerant Ad Hoc Networks},
institution = {INRIA},
type = {Research Report},
number = {RR-6645},
year = {2008},
month = sep,
url = {http://hal.inria.fr/inria-00321641/fr/},
pdf = {http://hal.inria.fr/action/open_file.php?url=http://hal.inria.fr/docs/00/32/16/41/PDF/RR-6645.pdf&docid=321641},
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 single source which at some points in time makes available a new version of a 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 (static) and state-dependent (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 q. 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 = "Rapports",
}
-
O. Amini,
F. Huc,
I. Sau,
and J. Zerovnik.
$(\ell,k)$-Routing on Plane Grids.
Research Report 6480,
INRIA,
March 2008.
[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$-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. |
@TechReport{AHSZ08,
author = {O. Amini and F. Huc and I. Sau and J. Zerovnik},
title = {$(\ell,k)$-Routing on Plane Grids},
year = {2008},
month = mar,
institution = {INRIA},
number = {6480},
type = {Research Report},
url= {https://hal.inria.fr/inria-00265297},
pdf = {https://hal.inria.fr/docs/00/26/52/97/PDF/RR_AHSZ08_JOIN.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.},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
sorte = "Rapports",
}
-
O. Amini,
D. Peleg,
S. Pérennes,
I. Sau,
and S. Saurabh.
Degree-Constrained Subgraph Problems: Hardness and Approximation Results.
Research Report RR-6690,
INRIA,
October 2008.
[WWW
] [PDF
]
| Abstract: |
|
A general instance of a Degree-Constrained Subgraph problem consists of an edge-weighted or vertex-weighted graph G and the objective is to find an optimal weighted subgraph, subject to certain degree constraints on the vertices of the subgraph. This paper considers three natural Degree-Constrained Subgraph problems and studies their behavior in terms of approximation algorithms. These problems take as input an undirected graph G=(V,E), with |V|=n and |E|=m. Our results, together with the definition of the three problems, are listed below. 1- The Maximum Degree-Bounded Connected Subgraph (MDBCS_d) problem takes as input a weight function w: E -> R+ and an integer d>1, and asks for a subset of edges E' such that the subgraph G'=(V,E') is connected, has maximum degree at most d, and the total edge-weight is maximized. We prove that MDBCS_d is not in APX for any d>1 (this was known only for d=2) and we provide a min{m/log n, nd/2log n}-approximation algorithm for unweighted graphs, and a min{n/2,m/d}-approximation algorithm for weighted graphs. 2- The Minimum Subgraph of Minimum Degree d (MSMD_d) problem consists in finding a smallest subgraph of G (in terms of number of vertices) with minimum degree at least d. For d=2 it corresponds to finding a shortest cycle of the graph. We prove that MSMD_d is not in APX for any d>2 and we provide an n/logn-approximation algorithm for the classes of graphs excluding a fixed graph as a minor, using dynamic programming techniques and a known structural result on graph minors. 3- The Dual Degree-Dense k-Subgraph (DDDkS) problem consists in finding a subgraph H of G such that |V(H)| |
@TechReport{APP+08b,
author = {O. Amini and D. Peleg and S. P\'erennes and I. Sau and S. {S}aurabh},
title = {{Degree-Constrained Subgraph Problems: Hardness and Approximation Results}},
year = {2008},
month = oct,
institution = {INRIA},
number = {RR-6690},
type = {Research Report},
url= {http://hal.inria.fr/inria-00331747},
pdf = {http://www-sop.inria.fr/members/Ignasi.Sauvalls/Pubs/RR_APP+08.pdf},
abstract = {A general instance of a Degree-Constrained Subgraph problem consists of an edge-weighted or vertex-weighted graph G and the objective is to find an optimal weighted subgraph, subject to certain degree constraints on the vertices of the subgraph. This paper considers three natural Degree-Constrained Subgraph problems and studies their behavior in terms of approximation algorithms. These problems take as input an undirected graph G=(V,E), with |V|=n and |E|=m. Our results, together with the definition of the three problems, are listed below. 1- The Maximum Degree-Bounded Connected Subgraph (MDBCS_d) problem takes as input a weight function w: E -> R+ and an integer d>1, and asks for a subset of edges E' such that the subgraph G'=(V,E') is connected, has maximum degree at most d, and the total edge-weight is maximized. We prove that MDBCS_d is not in APX for any d>1 (this was known only for d=2) and we provide a min{m/log n, nd/2log n}-approximation algorithm for unweighted graphs, and a min{n/2,m/d}-approximation algorithm for weighted graphs. 2- The Minimum Subgraph of Minimum Degree d (MSMD_d) problem consists in finding a smallest subgraph of G (in terms of number of vertices) with minimum degree at least d. For d=2 it corresponds to finding a shortest cycle of the graph. We prove that MSMD_d is not in APX for any d>2 and we provide an n/logn-approximation algorithm for the classes of graphs excluding a fixed graph as a minor, using dynamic programming techniques and a known structural result on graph minors. 3- The Dual Degree-Dense k-Subgraph (DDDkS) problem consists in finding a subgraph H of G such that |V(H)|
-
M. Asté,
F. Havet,
and C. Linhares-Sales.
Grundy number and products of graphs.
Research Report RR-6672,
INRIA,
October 2008.
[PDF
]
| Abstract: |
|
The {\em Grundy number} of a graph $G$, denoted by $\Gamma (G)$, is the largest $k$ such that $G$ has a {\em greedy} $k$-colouring, that is a colouring with $k$ colours obtained by applying the greedy algorithm according to some ordering of the vertices of $G$. In this paper, we study the Grundy number of the lexicographic, cartesian and direct products of two graphs in terms of the Grundy numbers of these graphs. Regarding the lexicographic product, we show that $\Gamma(G)\times\Gamma(H)\leq \Gamma(G[H])\leq 2^{\Gamma(G)-1}(\Gamma(H)-1)+\Gamma(G)-1$. In addition, we show that if $G$ is a tree or $\Gamma(G)=\Delta(G)+1$, then $\Gamma(G[H])=\Gamma(G)\times\Gamma(H)$. We then deduce that for every fixed $c\leq 1$, given a graph $G$, it is CoNP-Complete to decide if $\Gamma(G)\leq c\times \chi(G)$ and it is CoNP-Complete to decide if $\Gamma(G)\leq c\times \omega(G)$. Regarding the cartesian product, we show that there is no upper bound of $\Gamma(G\square H)$ as a function of $\Gamma(G)$ and $\Gamma(H)$. Nevertheless, we prove that for any fixed graph $G$, there is a function $h_G$ such that, for any graph $H$, $\Gamma(G\square H)\leq h_G(\Gamma(H))$. Regarding the direct product, we show that $\Gamma(G\times H)\geq \Gamma(G) +\Gamma(H)-2$ and construct for any $k$ some graph $G_k$ such that $\Gamma(G_k)=2k+1$ and $\Gamma(G_k\times K_2)=3k+1$. |
@TechReport{AHL08b,
author = {M. Ast\'e and F. Havet and C. Linhares-Sales},
title = {Grundy number and products of graphs},
year = {2008},
month = oct,
institution = {INRIA},
number = {RR-6672},
type = {Research Report},
pdf = {ftp://ftp-sop.inria.fr/mascotte/Publications/AHL08b.pdf},
abstract = {The {\em Grundy number} of a graph $G$, denoted by $\Gamma (G)$, is the largest $k$ such that $G$ has a {\em greedy} $k$-colouring, that is a colouring with $k$ colours obtained by applying the greedy algorithm according to some ordering of the vertices of $G$. In this paper, we study the Grundy number of the lexicographic, cartesian and direct products of two graphs in terms of the Grundy numbers of these graphs. Regarding the lexicographic product, we show that $\Gamma(G)\times\Gamma(H)\leq \Gamma(G[H])\leq 2^{\Gamma(G)-1}(\Gamma(H)-1)+\Gamma(G)-1$. In addition, we show that if $G$ is a tree or $\Gamma(G)=\Delta(G)+1$, then $\Gamma(G[H])=\Gamma(G)\times\Gamma(H)$. We then deduce that for every fixed $c\leq 1$, given a graph $G$, it is CoNP-Complete to decide if $\Gamma(G)\leq c\times \chi(G)$ and it is CoNP-Complete to decide if $\Gamma(G)\leq c\times \omega(G)$. Regarding the cartesian product, we show that there is no upper bound of $\Gamma(G\square H)$ as a function of $\Gamma(G)$ and $\Gamma(H)$. Nevertheless, we prove that for any fixed graph $G$, there is a function $h_G$ such that, for any graph $H$, $\Gamma(G\square H)\leq h_G(\Gamma(H))$. Regarding the direct product, we show that $\Gamma(G\times H)\geq \Gamma(G) +\Gamma(H)-2$ and construct for any $k$ some graph $G_k$ such that $\Gamma(G_k)=2k+1$ and $\Gamma(G_k\times K_2)=3k+1$.},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
sorte = "Rapports",
}
-
J-C. Bermond,
I. Caragiannis,
D. Coudert,
F. Diedrich,
L. Hogie,
F. Huc,
C. Molle,
J. Monteiro,
P. Leone,
H. Rivano,
and I. Sau.
Algorithmic solutions for critical resource sharing: third year.
Technical report Deliverable 2.2.3,
IST FET AEOLUS, Integrated Project IST-015964,
2008.
[PDF
]
@TechReport{BCC+08,
author = {J-C. Bermond and I. Caragiannis and D. Coudert and F. Diedrich and L. Hogie and F. Huc and C. Molle and J. Monteiro and P. Leone and H. Rivano and I. Sau},
title = {Algorithmic solutions for critical resource sharing: third year},
institution = {IST FET AEOLUS, Integrated Project IST-015964},
year = {2008},
number = {Deliverable 2.2.3},
pdf = {http://aeolus.ceid.upatras.gr/sub-projects/deliverables/D223.pdf},
sorte = "Rapports",
}
-
J-C. Bermond,
R. Correa,
and M-L. Yu.
Optimal Gathering Protocols on Paths under Interference Constraints.
Technical report inria-00168162,
HAL,
August 2008.
[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 simultaneously transmitted. 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 \geq 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. The protocols are shown to be optimal for any $d$ in the first case, and for $1 \leq d \leq 4$, in the second case. |
@TechReport{BCY08a,
author = {J-C. Bermond and R. Correa and M-L. Yu},
title = {Optimal Gathering Protocols on Paths under Interference Constraints},
institution = {HAL},
year = {2008},
OPTkey = {},
OPTtype = {},
number = {inria-00168162},
OPTaddress = {},
month = aug,
OPTnote = {},
OPTannote = {},
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 simultaneously transmitted. 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 \geq 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. The protocols are shown to be optimal for any $d$ in the first case, and for $1 \leq d \leq 4$, in the second case.},
url = {http://hal.inria.fr/inria-00168162/},
PDF = {http://www-sop.inria.fr/members/Jean-Claude.Bermond/PUBLIS/BCY08.pdf},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
sorte = "Rapports",
}
-
J-C. Bermond,
D. Mazauric,
V. Misra,
and P. Nain.
Distributed Call Scheduling in Wireless Networks.
Technical report RR-6763,
INRIA,
December 2008.
[WWW
] [PDF
]
| Abstract: |
|
This work investigates distributed transmission scheduling in wireless networks. Due to interference constraints, "neighboring links" cannot be simultaneously activated, otherwise transmissions will fail. Here, we consider any binary model of interference. We follow the model described by Bui, Sanghavi, and Srikant in SBS07,SBS09. We suppose that time is slotted and during each slot we have two phases: one control phase which determines what links will be activated and send data during the second phase. We assume random arrivals on each link during each slot, therefore a queue is associated to each link. Since nodes do not have a global knowledge of the network, our aim (like in SBS07,SBS09) is to design for the control phase, a distributed algorithm which determines a set of non interfering links. To be efficient the control phase should be as short as possible; this is done by exchanging control messages during a constant number of mini-slots (constant overhead). In this article we design the first fully distributed local algorithm with the following properties: it works for any arbitrary binary interference model; it has a constant overhead (independent of the size of the network and the values of the queues); and it needs no knowledge. Indeed contrary to other existing algorithms, we do not need to know the values of the queues of the "neighboring links", which are difficult to obtain in a wireless network with interference. We prove that this algorithm gives a maximal set of active links (in each interference set, there is at least one active edge). We also give sufficient conditions for stability under Markovian assumptions. Finally the performance of our algorithm (throughput, stability) is investigated and compared via simulations to that of previously proposed schemes. |
@TechReport{BMMN08,
author = {J-C. Bermond and D. Mazauric and V. Misra and P. Nain},
title = {Distributed Call Scheduling in Wireless Networks},
institution = {INRIA},
year = {2008},
OPTkey = {},
OPTtype = {},
number = {RR-6763},
OPTaddress = {},
month = dec,
OPTnote = {},
OPTannote = {},
abstract = {This work investigates distributed transmission scheduling in wireless networks. Due to interference constraints, "neighboring links" cannot be simultaneously activated, otherwise transmissions will fail. Here, we consider any binary model of interference. We follow the model described by Bui, Sanghavi, and Srikant in SBS07,SBS09. We suppose that time is slotted and during each slot we have two phases: one control phase which determines what links will be activated and send data during the second phase. We assume random arrivals on each link during each slot, therefore a queue is associated to each link. Since nodes do not have a global knowledge of the network, our aim (like in SBS07,SBS09) is to design for the control phase, a distributed algorithm which determines a set of non interfering links. To be efficient the control phase should be as short as possible; this is done by exchanging control messages during a constant number of mini-slots (constant overhead). In this article we design the first fully distributed local algorithm with the following properties: it works for any arbitrary binary interference model; it has a constant overhead (independent of the size of the network and the values of the queues); and it needs no knowledge. Indeed contrary to other existing algorithms, we do not need to know the values of the queues of the "neighboring links", which are difficult to obtain in a wireless network with interference. We prove that this algorithm gives a maximal set of active links (in each interference set, there is at least one active edge). We also give sufficient conditions for stability under Markovian assumptions. Finally the performance of our algorithm (throughput, stability) is investigated and compared via simulations to that of previously proposed schemes.},
url = {http://hal.inria.fr/inria-00345669},
pdf = {ftp://ftp-sop.inria.fr/mascotte/Publications/RR-6763.pdf},
sorte = "Rapports",
}
-
J-C. Bermond,
V. Papadopoulou,
and E. Pitoura.
Subproject2: Resource Management Report on the activities of the third year.
Technical report Deliverable 2.O.3,
IST FET AEOLUS, Integrated Project IST-015964,
2008.
[PDF
]
@TechReport{BPP08,
author = {J-C. Bermond and V. Papadopoulou and E. Pitoura},
title = {Subproject2: Resource Management Report on the activities of the third year},
institution = {IST FET AEOLUS, Integrated Project IST-015964},
year = {2008},
number = {Deliverable 2.O.3},
pdf = {http://aeolus.ceid.upatras.gr/sub-projects/deliverables/D203.pdf},
sorte = "Rapports",
}
-
P. Berthomé and N. Nisse.
A unified FPT Algorithm for Width of Partition Functions.
Research Report RR-6646,
INRIA,
September 2008.
[WWW
] [PDF
]
| Abstract: |
|
During the last decades, several polynomial-time algorithms have been designed that decide if a graph has treewidth (resp., pathwidth, branchwidth, etc.) at most $k$, where $k$ is a fixed parameter. Amini {\it et al.} (to appear in SIAM J. Discrete Maths.) use the notions of partitioning-trees and partition functions as a generalized view of classical decompositions of graphs, namely tree-decomposition, path-decomposition, branch-decomposition, etc. In this paper, we propose a set of simple sufficient conditions on a partition function $\Phi$, that ensures the existence of a linear-time explicit algorithm deciding if a set $A$ has $\Phi$-width at most $k$ ($k$ fixed). In particular, the algorithm we propose unifies the existing algorithms for treewidth, pathwidth, linearwidth, branchwidth, carvingwidth and cutwidth. It also provides the first Fixed Parameter Tractable linear-time algorithm deciding if the $q$-branched treewidth, defined by Fomin {\it et al.} (Algo rithmica 2007), of a graph is at most $k$ ($k$ and $q$ are fixed). Our decision algorithm can be turned into a constructive one by following the ideas of Bodlaender and Kloks (J. of Alg. 1996). |
@TechReport{BeNi08,
author = {P. Berthom\'e and N. Nisse},
title = {A unified {FPT} Algorithm for Width of Partition Functions},
institution = {INRIA},
number = {RR-6646},
year = {2008},
type = {Research Report},
month = sep,
url = {https://hal.inria.fr/},
pdf = {http://www-sop.inria.fr/members/Nicolas.Nisse/publications/RR-6646.pdf},
abstract = {During the last decades, several polynomial-time algorithms have been designed that decide if a graph has treewidth (resp., pathwidth, branchwidth, etc.) at most $k$, where $k$ is a fixed parameter. Amini {\it et al.} (to appear in SIAM J. Discrete Maths.) use the notions of partitioning-trees and partition functions as a generalized view of classical decompositions of graphs, namely tree-decomposition, path-decomposition, branch-decomposition, etc. In this paper, we propose a set of simple sufficient conditions on a partition function $\Phi$, that ensures the existence of a linear-time explicit algorithm deciding if a set $A$ has $\Phi$-width at most $k$ ($k$ fixed). In particular, the algorithm we propose unifies the existing algorithms for treewidth, pathwidth, linearwidth, branchwidth, carvingwidth and cutwidth. It also provides the first Fixed Parameter Tractable linear-time algorithm deciding if the $q$-branched treewidth, defined by Fomin {\it et al.} (Algo rithmica 2007), of a graph is at most $k$ ($k$ and $q$ are fixed). Our decision algorithm can be turned into a constructive one by following the ideas of Bodlaender and Kloks (J. of Alg. 1996).},
sorte = "Rapports",
}
-
R. Correa,
F. Havet,
and J.-S. Sereni.
About a Brooks-type theorem for improper colouring.
Research Report RR-6432,
INRIA,
January 2008.
[WWW
] [PDF
]
| Abstract: |
|
A graph is k-improperly -colourable if its vertices can be partitioned into parts such that each part induces a subgraph of maximum degree at most k. A result of Lovasz a states that for any graph G, such a partition exists if l is at least (Delta(G)+1)/(k+1) . 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 has k-improper chromatic number at most (Delta+1)/(k+1) - 1? We show that the answer is no, unless P = N P , when Delta= (k + 1)l, k>0 and l+sqrt(l) < 2k + 4. We also show that, if G is planar, k = 1 or k = 2, Delta = 2k + 2, and l= 2, then the answer is still no, unless P = N P . These results answer some questions of Cowen et al. [Journal of Graph Theory 24(3):205-219, 1997]. |
@TechReport{CHS08,
author = {R. Correa and F. Havet and J.-S. Sereni},
title = {About a Brooks-type theorem for improper colouring},
year = {2008},
month = jan,
institution = {INRIA},
number = {RR-6432},
type = {Research Report},
url= {https://hal.inria.fr/inria-00223009},
pdf = {https://hal.inria.fr/action/open_file.php?url=https://hal.inria.fr/docs/00/26/53/83/PDF/RR-6432.pdf&docid=265383},
abstract = {A graph is k-improperly -colourable if its vertices can be partitioned into parts such that each part induces a subgraph of maximum degree at most k. A result of Lovasz a states that for any graph G, such a partition exists if l is at least (Delta(G)+1)/(k+1) . 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 has k-improper chromatic number at most (Delta+1)/(k+1) - 1? We show that the answer is no, unless P = N P , when Delta= (k + 1)l, k>0 and l+sqrt(l) < 2k + 4. We also show that, if G is planar, k = 1 or k = 2, Delta = 2k + 2, and l= 2, then the answer is still no, unless P = N P . These results answer some questions of Cowen et al. [Journal of Graph Theory 24(3):205-219, 1997].},
sorte = "Rapports",
}
-
D. Coudert,
F. Huc,
D. Mazauric,
N. Nisse,
and J-S. Sereni.
Routing Reconfiguration/Process Number: Coping wih Two Classes of Services.
Research Report RR-6698,
INRIA,
October 2008.
[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. |
@TechReport{CHM+08,
author = {D. Coudert and F. Huc and D. Mazauric and N. Nisse and J-S. Sereni},
title = {Routing Reconfiguration/Process Number: Coping wih Two Classes of Services},
institution = {INRIA},
year = {2008},
number = {RR-6698},
type = {Research Report},
month = oct,
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 = "Rapports",
}
-
D. Coudert,
F. Huc,
and D. Mazauric.
A distributed algorithm for computing and updating the process number of a forest.
Research Report RR-6560,
INRIA,
June 2008.
[WWW
]
| Abstract: |
|
In this paper, we present a distributed algorithm to compute various parameters of a tree such as the process number, the edge search number or the node search number and so the pathwidth. This algorithm requires n steps, an overall computation time of O(n log(n)), and n messages of size log_3(n)+3. We then propose a distributed algorithm to update the process number (or the node search number, or the edge search number) of each component of a forest after adding or deleting an edge. This second algorithm requires O(D) steps, an overall computation time of O(D log(n)), and O(D) messages of size log_3(n)+3, where D is the diameter of the modified connected component. Finally, we show how to extend our algorithms to trees and forests of unknown size using messages of less than 2a+4+e bits, where a is the parameter to be determined and e=1 for updates algorithms. |
@TechReport{CHM08b,
author = {D. Coudert and F. Huc and D. Mazauric},
title = {A distributed algorithm for computing and updating the process number of a forest},
year = {2008},
month = jun,
institution = {INRIA},
number = {RR-6560},
type = {Research Report},
url= {https://hal.inria.fr/inria-00288304},
abstract = {In this paper, we present a distributed algorithm to compute various parameters of a tree such as the process number, the edge search number or the node search number and so the pathwidth. This algorithm requires n steps, an overall computation time of O(n log(n)), and n messages of size log_3(n)+3. We then propose a distributed algorithm to update the process number (or the node search number, or the edge search number) of each component of a forest after adding or deleting an edge. This second algorithm requires O(D) steps, an overall computation time of O(D log(n)), and O(D) messages of size log_3(n)+3, where D is the diameter of the modified connected component. Finally, we show how to extend our algorithms to trees and forests of unknown size using messages of less than 2a+4+e bits, where a is the parameter to be determined and e=1 for updates algorithms.},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
sorte = "Rapports",
}
-
D. Coudert and D. Mazauric.
Network Reconfiguration using Cops-and-Robber Games.
Research Report RR-6694,
INRIA,
August 2008.
[WWW
]
| Abstract: |
|
The process number is the number of requests that have to be simultaneously disturbed during a routing reconfiguration phase of a connection oriented network. From a graph theory point of view, it is similar to the pathwidth. However they are not always equal in general graphs. Determining these parameters is in general NP-complete. In this paper, we propose a polynomial algorithm to compute an approximation of the process number of digraphs, improving the efficiency of the previous exponential algorithm. |
@TechReport{CoMa08,
author = {D. Coudert and D. Mazauric},
title = {Network Reconfiguration using Cops-and-Robber Games},
institution = {INRIA},
year = {2008},
type = {Research Report},
OPTkey = {},
OPTtype = {},
number = {RR-6694},
OPTaddress = {},
month = aug,
OPTnote = {},
OPTannote = {},
abstract = {The process number is the number of requests that have to be simultaneously disturbed during a routing reconfiguration phase of a connection oriented network. From a graph theory point of view, it is similar to the pathwidth. However they are not always equal in general graphs. Determining these parameters is in general NP-complete. In this paper, we propose a polynomial algorithm to compute an approximation of the process number of digraphs, improving the efficiency of the previous exponential algorithm.},
url = {http://hal.inria.fr/inria-00315568/},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
sorte = "Rapports",
}
-
D. Coudert,
N. Nepomuceno,
and H. Rivano.
Wireless Backhaul Networks: Minimizing Energy Consumption by Power Efficient Radio Links Configuration.
Technical report RR-6752,
INRIA,
December 2008.
[WWW
] [PDF
]
| Abstract: |
|
In this work, we investigate on minimizing the energy consumption of a wireless backhaul communication network through a joint optimization problem of data routing and radio configuration. The backhaul network is modeled by a digraph in which the nodes represent radio base stations and the arcs denote radio links. According to the scenario under consideration, 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 which minimize the total energy expenditure, 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 stepwise cost functions which is very hard to optimize. We then introduce a linear relaxation of the problem, which exploits the convexity of the energy cost as a function of the throughput on a radio link. This yields lower bounds on the energy consumption, and eventually a heuristic algorithm based on the fractional optimum is presented. Our models are validated through extensive experiments which are reported and discussed. The results of the simulations testify the potentialities behind this novel approach. In particular, our algorithm takes a good advantage of the convexity of the cost function, inducing a quite small integrity gap in practice. |
@TechReport{CNR08,
author = {D. Coudert and N. Nepomuceno and H. Rivano},
title = {Wireless Backhaul Networks: Minimizing Energy Consumption by Power Efficient Radio Links Configuration},
institution = {INRIA},
year = {2008},
OPTkey = {},
OPTtype = {},
number = {RR-6752},
OPTaddress = {},
month = dec,
OPTnote = {},
OPTannote = {},
url = {http://hal.inria.fr/inria-00344344/},
abstract = {In this work, we investigate on minimizing the energy consumption of a wireless backhaul communication network through a joint optimization problem of data routing and radio configuration. The backhaul network is modeled by a digraph in which the nodes represent radio base stations and the arcs denote radio links. According to the scenario under consideration, 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 which minimize the total energy expenditure, 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 stepwise cost functions which is very hard to optimize. We then introduce a linear relaxation of the problem, which exploits the convexity of the energy cost as a function of the throughput on a radio link. This yields lower bounds on the energy consumption, and eventually a heuristic algorithm based on the fractional optimum is presented. Our models are validated through extensive experiments which are reported and discussed. The results of the simulations testify the potentialities behind this novel approach. In particular, our algorithm takes a good advantage of the convexity of the cost function, inducing a quite small integrity gap in practice.},
pdf = {http://hal.inria.fr/docs/00/34/43/44/PDF/RR-6752.pdf},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
sorte = "Rapports",
}
-
O. Dalle,
F. Giroire,
J. Monteiro,
and S. Pérennes.
Analysis of Failure Correlation in Peer-to-Peer Storage Systems.
Technical report RR-6761,
INRIA,
December 2008.
[WWW
] [PDF
]
| Abstract: |
|
In this paper, we propose and study analytical models of self-repairing peer-to-peer storage systems subject to failures. The failures correspond to the simultaneous loss of multiple data blocks due to the definitive loss of a peer (or following a disk crash). In the system we consider that such failures happen continuously, hence the necessity of a self-repairing mechanism (data are written once for ever). We show that, whereas stochastic models of independent failures similar to those found in the literature give a correct approximation of the average behavior of real systems, they fail to capture their variations (e.g. in bandwidth needs). We propose to solve this problem using a new stochastic model based on a fluid approximation and we give a characterization of the behavior of the system according to this model (expectation and standard deviation). This new model is validated using comparisons between its theoretical behavior and computer simulations. |
@TECHREPORT{DGMP08,
author = {O. Dalle and F. Giroire and J. Monteiro and S. P\'erennes},
title = {Analysis of Failure Correlation in Peer-to-Peer Storage Systems},
institution = {INRIA},
year = {2008},
number = {RR-6761},
month = dec,
abstract = {In this paper, we propose and study analytical models of self-repairing peer-to-peer storage systems subject to failures. The failures correspond to the simultaneous loss of multiple data blocks due to the definitive loss of a peer (or following a disk crash). In the system we consider that such failures happen continuously, hence the necessity of a self-repairing mechanism (data are written once for ever). We show that, whereas stochastic models of independent failures similar to those found in the literature give a correct approximation of the average behavior of real systems, they fail to capture their variations (e.g. in bandwidth needs). We propose to solve this problem using a new stochastic model based on a fluid approximation and we give a characterization of the behavior of the system according to this model (expectation and standard deviation). This new model is validated using comparisons between its theoretical behavior and computer simulations.},
optx-editorial-board = {yes},
optx-international-audience = {yes},
optx-proceedings = {yes},
pdf = {http://hal.inria.fr/docs/00/34/68/57/PDF/RR-6671.pdf},
url = {http://hal.inria.fr/inria-00346857/},
sorte = "Rapports",
}
-
J. Galtier.
New algorithms to compute the strength of a graph.
Research Report RR-6592,
INRIA,
July 2008.
@TechReport{Gal08b,
author = {J. Galtier},
title = {New algorithms to compute the strength of a graph},
institution = {INRIA},
year = {2008},
type = {Research Report},
number = {RR-6592},
month = {jul},
OPTabstract = {We investigate the problem of computing the strength of a graph. We describe in this article the first polyhedral formulation for the weighted strength in polynomial size of the problem, that is O(mn), where n is the number of vertices and m the number of edges. Moreover, we describe a surprisingly simple FPTAS that gives the strength within 1+epsilon in time $O(m log^2(n) log(m/n)/epsilon^2)$ and space O(m), outperforming by a factor of roughly $\min(n\sqrt{m},n^5/3)$ the best known exact algorithm of Trubin associated with the Goldberg and Rao maxflow algorithm for that problem, and of roughly sigma(G) the FPTAS of Plotkin, Shmoys, and Tardos.},
OPTpdf = {http://hal.inria.fr/action/open_file.php?url=http://hal.inria.fr/docs/00/30/79/91/PDF/RR-6592.pdf&docid=307991},
OPTurl = {http://hal.inria.fr/index.php?halsid=kdg5el2lb2ukptftsk547uego4&view_this_doc=inria-00305560&version=1},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
sorte = "Rapports",
}
-
C. Gomes,
S. Pérennes,
and H. Rivano.
Bottleneck Analysis for Routing and Call Scheduling in Multi-hop Wireless Networks.
Technical report inria-00282200,
INRIA,
May 2008.
[WWW
] [PDF
]
| Abstract: |
|
In this paper, we address the routing and call scheduling problem in which one has to find a minimum-length schedule of selected links in a TDMA (Time Division Multiple Access) based wireless network. As we deal with a multi-hop networks, these selected links represent a routing solution (paths) providing enough capacity to achieve the routers requirements of bandwidth. We present a cross-layer formulation of the problem that computes joint routing and scheduling. We use a branch-and-price algorithm to solve optimally the problem. A column generation algorithm is used to cope with the exponential set of rounds. The branch-and-bound algorithm provides mono-routing. We run experiments on networks from the literature, with different number of gateways. Experimental results as well as theoretical insights let us conjecture that the bottleneck region analysis is enough to find the optimal solution. The bottleneck is usually the gateway considering almost uniform traffic. The integer round-up property (IRUP) seems to hold for our problem. |
@TechReport{GPR08a,
author = {C. Gomes and S. P\'erennes and H. Rivano},
title = {Bottleneck Analysis for Routing and Call Scheduling in Multi-hop Wireless Networks},
institution = {INRIA},
number = {inria-00282200},
url= {http://hal.inria.fr/inria-00282200/fr/},
pdf = {http://hal.inria.fr/action/open_file.php?url=http://hal.inria.fr/docs/00/28/22/00/PDF/INRIA_Report3.pdf&docid=282200},
month = may,
YEAR = {2008},
abstract = {In this paper, we address the routing and call scheduling problem in which one has to find a minimum-length schedule of selected links in a TDMA (Time Division Multiple Access) based wireless network. As we deal with a multi-hop networks, these selected links represent a routing solution (paths) providing enough capacity to achieve the routers requirements of bandwidth. We present a cross-layer formulation of the problem that computes joint routing and scheduling. We use a branch-and-price algorithm to solve optimally the problem. A column generation algorithm is used to cope with the exponential set of rounds. The branch-and-bound algorithm provides mono-routing. We run experiments on networks from the literature, with different number of gateways. Experimental results as well as theoretical insights let us conjecture that the bottleneck region analysis is enough to find the optimal solution. The bottleneck is usually the gateway considering almost uniform traffic. The integer round-up property (IRUP) seems to hold for our problem.},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
sorte = "Rapports",
}
-
F. Havet,
M. Klazar,
J. Kratochvil,
D. Kratsch,
and M. Liedloff.
Exact algorithms for $L(2,1)$-labelling.
Research Report RR-6587,
INRIA,
07 2008.
| Abstract: |
|
The notion of distance constrained graph labelings, motivated by the Frequency Assignment Problem, reads as follows: A mapping from the vertex set of a graph $G=(V,E)$ into an interval of integers $0, \dots ,k$ is an $L(2,1)$-labeling of $G$ of span $k$ if any two adjacent vertices are mapped onto integers that are at least 2 apart, and every two vertices with a common neighbor are mapped onto distinct integers. It is known that for any fixed $k\ge 4$, deciding the existence of such a labeling is an NP-complete problem. We present exact exponential time algorithms that are faster than the naive $O((k+1)^n)$ algorithm that would try all possible mappings. The improvement is best seen in the first NP-complete case of $k=4$ -- here the running time of our algorithm is $O(1.3006^n)$. $O(1.3161^n)$. Furthermore we show that dynamic programming can be used to establish an $O(3.8730^n)$ algorithm to compute an optimal $L(2,1)$-labeling. |
@TechReport{HKK+08,
author = {F. Havet and M. Klazar and J. Kratochvil and D. Kratsch and M. Liedloff},
title = {Exact algorithms for $L(2,1)$-labelling},
year = {2008},
month = {07},
institution = {INRIA},
number = {RR-6587},
type = {Research Report},
opturl = {http://hal.inria.fr/index.php?halsid=1hng08barus89qc4e98egl8fp0&view_this_doc=inria-00303330&version=1},
optpdf = {http://hal.inria.fr/action/open_file.php?url=http://hal.inria.fr/docs/00/30/33/30/PDF/RR-6587.pdf&docid=303330},
abstract = {The notion of distance constrained graph labelings, motivated by the Frequency Assignment Problem, reads as follows: A mapping from the vertex set of a graph $G=(V,E)$ into an interval of integers $0, \dots ,k$ is an $L(2,1)$-labeling of $G$ of span $k$ if any two adjacent vertices are mapped onto integers that are at least 2 apart, and every two vertices with a common neighbor are mapped onto distinct integers. It is known that for any fixed $k\ge 4$, deciding the existence of such a labeling is an NP-complete problem. We present exact exponential time algorithms that are faster than the naive $O((k+1)^n)$ algorithm that would try all possible mappings. The improvement is best seen in the first NP-complete case of $k=4$ -- here the running time of our algorithm is $O(1.3006^n)$. $O(1.3161^n)$. Furthermore we show that dynamic programming can be used to establish an $O(3.8730^n)$ algorithm to compute an optimal $L(2,1)$-labeling.},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
sorte = "Rapports",
}
-
F. Havet,
D. Král,
J.-S. Sereni,
and R. Skrekovski.
Facial coloring using Hall's Theorem.
Research Report 383,
ITI-series,
2008.
[PDF
]
| Abstract: |
|
A vertex coloring of a plane graph is $\ell$-facial if every two distinct vertices joined by a facial walk of length at most $\ell$ receive distinct colors. It has been conjectured that every plane graph has an $\ell$-facial coloring with at most $3\ell+1$ colors. We improve the currently best known bound and show that every plane graph has an $\ell$-facial coloring with at most $\lfloor 7\ell/2\rfloor+6$ colors. Our proof uses the standard discharging technique, however, in the reduction part we have successfully applied Hall's Theorem, which seems to be quite an innovative approach in this area. |
@TechReport{HKSS08,
author = {F. Havet and D. Kr\'al and J.-S. Sereni and R. {\v S}krekovski},
title = {Facial coloring using Hall's Theorem},
year = {2008},
institution = {ITI-series},
number = {383},
type = {Research Report},
pdf = {ftp://ftp-sop.inria.fr/mascotte/Publications/HKSS08.pdf},
abstract={A vertex coloring of a plane graph is $\ell$-facial if every two distinct vertices joined by a facial walk of length at most $\ell$ receive distinct colors. It has been conjectured that every plane graph has an $\ell$-facial coloring with at most $3\ell+1$ colors. We improve the currently best known bound and show that every plane graph has an $\ell$-facial coloring with at most $\lfloor 7\ell/2\rfloor+6$ colors. Our proof uses the standard discharging technique, however, in the reduction part we have successfully applied Hall's Theorem, which seems to be quite an innovative approach in this area.},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
sorte = "Rapports",
}
-
F. Havet,
B. Reed,
and J.-S. Sereni.
$L(p,1)$-labelling of graphs.
Research Report RR-6673,
INRIA,
October 2008.
[PDF
]
| Abstract: |
|
An $L(p,1)$-labelling of a graph is a function $f$ from the vertex set to the positive integers such that $|f(x)-f(y)|\geq p$ if $\dist(x,y)=1$ and $|f(x)-f(y)|\geq p$ if $\dist(x,y)=2$, where $\dist(x,y)$ is the distance between the two vertices~$x$ and~$y$ in the graph. The \emph{span} of an $L(p,1)$-labelling $f$ is the difference between the largest and the smallest labels used by $f$ plus $1$. In 1992, Griggs and Yeh conjectured that every graph with maximum degree $\Delta\geq 2$ has an $L(2,1)$-labelling with span at most $\D2+1$. We settle this conjecture for $\D$ sufficiently large. More generally, we show that for any positive integer $p$ there exists a constant $\Delta_p$ such that every graph with maximum degree $\Delta\geq \Delta_p$ has an $L(p,1)$-labelling with span at most $\D2+1$. This yields that, for each positive integer $p$, there is an integer $C_p$ such that every graph with maximum degree $\Delta$ has an $L(p,1)$-labelling with span at most $\Delta2+C_p$. |
@TechReport{HRS08b,
author = {F. Havet and B. Reed and J.-S. Sereni},
title = {$L(p,1)$-labelling of graphs},
year = {2008},
month = oct,
institution = {INRIA},
number = {RR-6673},
type = {Research Report},
pdf = {ftp://ftp-sop.inria.fr/mascotte/Publications/HRS08b.pdf},
abstract = {An $L(p,1)$-labelling of a graph is a function $f$ from the vertex set to the positive integers such that $|f(x)-f(y)|\geq p$ if $\dist(x,y)=1$ and $|f(x)-f(y)|\geq p$ if $\dist(x,y)=2$, where $\dist(x,y)$ is the distance between the two vertices~$x$ and~$y$ in the graph. The \emph{span} of an $L(p,1)$-labelling $f$ is the difference between the largest and the smallest labels used by $f$ plus $1$. In 1992, Griggs and Yeh conjectured that every graph with maximum degree $\Delta\geq 2$ has an $L(2,1)$-labelling with span at most $\D2+1$. We settle this conjecture for $\D$ sufficiently large. More generally, we show that for any positive integer $p$ there exists a constant $\Delta_p$ such that every graph with maximum degree $\Delta\geq \Delta_p$ has an $L(p,1)$-labelling with span at most $\D2+1$. This yields that, for each positive integer $p$, there is an integer $C_p$ such that every graph with maximum degree $\Delta$ has an $L(p,1)$-labelling with span at most $\Delta2+C_p$.},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
sorte = "Rapports",
}
-
F. Havet,
J. van den Heuvel,
C. McDiarmid,
and B. Reed.
List Colouring Squares of Planar Graphs.
Research Report RR-6586,
INRIA,
July 2008.
| Abstract: |
|
In 1977, Wegner conjectured that the chromatic number of the square of every planar graph~$G$ with maximum degree $\Delta\ge8$ is at most $\bigl\lfloor\frac32\,\Delta\bigr\rfloor+1$. We show that it is at most $\frac32\,\Delta\,(1+o(1))$, and indeed this is true for the list chromatic number and for more general classes of graphs. |
@TechReport{HHMR08,
author = {F. Havet and J. van den Heuvel and C. McDiarmid and B. Reed},
title = {List Colouring Squares of Planar Graphs},
year = {2008},
month = jul,
institution = {INRIA},
number = {RR-6586},
type = {Research Report},
opturl = {http://hal.inria.fr/index.php?halsid=1hng08barus89qc4e98egl8fp0&view_this_doc=inria-00303303&version=1},
optpdf = {http://hal.inria.fr/action/open_file.php?url=http://hal.inria.fr/docs/00/30/33/03/PDF/RR-6586.pdf&docid=303303},
abstract = {In 1977, Wegner conjectured that the chromatic number of the square of every planar graph~$G$ with maximum degree $\Delta\ge8$ is at most $\bigl\lfloor\frac32\,\Delta\bigr\rfloor+1$. We show that it is at most $\frac32\,\Delta\,(1+o(1))$, and indeed this is true for the list chromatic number and for more general classes of graphs. },
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
sorte = "Rapports",
}
-
X. Muñoz and I. Sau.
Traffic Grooming in Unidirectional WDM Rings with Bounded Degree Request Graph.
Research Report RR-6481,
INRIA,
March 2008.
[WWW
] [PDF
]
| Abstract: |
|
Traffic grooming is a major issue in optical networks. It refers to grouping low rate signals into higher speed streams, in order to reduce the equipment cost. In SONET WDM networks, this cost is mostly given by the number of electronic terminations, namely ADMs. We consider the case when the topology is a unidirectional ring. In graph-theoretical terms, the traffic grooming problem in this case consists in partitioning the edges of a request graph into subgraphs with a maximum number of edges, while minimizing the total number of vertices of the decomposition. We consider the case when the request graph has bounded maximum degree $\Delta$, and our aim is to design a network being able to support any request graph satisfying the degree constraints. The existing theoretical models in the literature are much more rigid, and do not allow such adaptability. We formalize the problem, and solve the cases $\Delta=2$ (for all values of $C$) and $\Delta = 3$ (except the case $C=4$). We also provide lower and upper bounds for the general case. |
@TechReport{MuSa08a,
author = {X. Mu{\~n}oz and I. Sau},
title = {{Traffic Grooming in Unidirectional WDM Rings with Bounded Degree Request Graph}},
year = {2008},
month = mar,
institution = {INRIA},
number = {RR-6481},
type = {Research Report},
url= {https://hal.inria.fr/inria-00265565},
pdf = {https://hal.inria.fr/action/open_file.php?url=https://hal.inria.fr/docs/00/26/57/49/PDF/RR-6481.pdf&docid=265749},
abstract = {Traffic grooming is a major issue in optical networks. It refers to grouping low rate signals into higher speed streams, in order to reduce the equipment cost. In SONET WDM networks, this cost is mostly given by the number of electronic terminations, namely ADMs. We consider the case when the topology is a unidirectional ring. In graph-theoretical terms, the traffic grooming problem in this case consists in partitioning the edges of a request graph into subgraphs with a maximum number of edges, while minimizing the total number of vertices of the decomposition. We consider the case when the request graph has bounded maximum degree $\Delta$, and our aim is to design a network being able to support any request graph satisfying the degree constraints. The existing theoretical models in the literature are much more rigid, and do not allow such adaptability. We formalize the problem, and solve the cases $\Delta=2$ (for all values of $C$) and $\Delta = 3$ (except the case $C=4$). We also provide lower and upper bounds for the general case.},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
sorte = "Rapports",
}
-
N. Nisse,
K. Suchan,
and I. Rapaport.
Distributed computing of efficient routing schemes in generalized chordal graphs.
Technical report CMM-B-08/10-220,
CMM,
October 2008.
[PDF
]
| Abstract: |
|
We propose a simple interval routing scheme for a graph $G$, based on a Maximal Neighborhood BFS-tree $T$ of $G$. In our scheme a message simply follows the source-destination path in $T$ but, in at most one step, it may take a shortcut. This shortcut is taken when the current node has a neighbor in $G$ which is an ancestor in $T$ of the destination. In the class of $k$-chordal graphs, this gives an additive stretch of at most $k-1$, and at most $1$ in the class of chordal graphs. Our routing tables use $O(\Delta\log n)$ bits per node, where $\Delta$ is the maximum degree. We propose a simple distributed algorithm to compute such tables in time $O(D)$ in any $n$-node graph with diameter $D$. |
@TechReport{NSR08,
author = {N. Nisse and K. Suchan and I. Rapaport},
title = {Distributed computing of efficient routing schemes in generalized chordal graphs},
institution = {CMM},
number = {CMM-B-08/10-220},
year = {2008},
month = {oct},
opturl = {http://www.dim.uchile.cl/index.php?option=articles&Itemid=7&topid=9},
pdf = {http://ftp-sop.inria.fr/mascotte/Publications/NSR08.pdf},
abstract = {We propose a simple interval routing scheme for a graph $G$, based on a Maximal Neighborhood BFS-tree $T$ of $G$. In our scheme a message simply follows the source-destination path in $T$ but, in at most one step, it may take a shortcut. This shortcut is taken when the current node has a neighbor in $G$ which is an ancestor in $T$ of the destination. In the class of $k$-chordal graphs, this gives an additive stretch of at most $k-1$, and at most $1$ in the class of chordal graphs. Our routing tables use $O(\Delta\log n)$ bits per node, where $\Delta$ is the maximum degree. We propose a simple distributed algorithm to compute such tables in time $O(D)$ in any $n$-node graph with diameter $D$.},
sorte = "Rapports",
}
-
S. Pérennes and I. Sau.
Sur la Conjecture des Jeux Uniques.
Research Report RR-6691,
INRIA,
October 2008.
[WWW
] [PDF
]
| Abstract: |
|
La plupart des problèmes d'optimisation combinatoire sont NP-difficiles, c'est-à -dire qu'ils ne peuvent être résolus en temps polynomial que si les classes P et NP sont identiques. Pour ces problèmes on peut espérer soit trouver des algorithmes d'approximation, soit prouver qu'ils ne peuvent pas être approximés de manière efficace. En 2002 S. Khot formula la Conjecture des Jeux Uniques (UGC), qui géneralise le théorème PCP et impliquerait d'importants résultats d'innaproximabilité pour plusieurs problèmes d'optimisation combinatoire (par exemple Max Cut ou Vertex Cover). Intuitivement, la UGC dit que, pour une certaine classe de jeux, appelés uniques, il est NP-dur de décider si l'on peut trouver une solution proche de l'optimale, ou si toutes les solutions sont loin de l'optimale. Cette conjecture est devenue un problème ouvert des plus importants dans la théorie de la complexité et de l'approximation. Dans cet article nous étudions un problème très relié à la UGC: Max-E$2$-Lin2 dans les graphes bipartis. Dans Max-E$2$-Lin2 on a un graphe $G$ ayant deux type d'arêtes, requérant soit la même soit différente couleur pour ses extrémités. Le but est de 2-colorer les sommets de $G$ en maximisant le nombre d'arêtes satisfaites. Nous prouvons que ce problème est APX-complet dans les graphes bipartis et, en utilisant le Théorème de Répétition Paralèlle, nous discutons les conséquences de ce résultat dans le cadre des jeux uniques et la UGC. |
@TechReport{PeSa08,
author = {S. P\'erennes and I. Sau},
title = {{Sur la Conjecture des Jeux Uniques}},
year = {2008},
month = oct,
institution = {INRIA},
number = {RR-6691},
type = {Research Report},
url= {http://hal.inria.fr/inria-00331248},
pdf = {http://www-sop.inria.fr/members/Ignasi.Sauvalls/Pubs/RR_PeSa08.pdf},
abstract = {La plupart des problèmes d'optimisation combinatoire sont NP-difficiles, c'est-à -dire qu'ils ne peuvent être résolus en temps polynomial que si les classes P et NP sont identiques. Pour ces problèmes on peut espérer soit trouver des algorithmes d'approximation, soit prouver qu'ils ne peuvent pas être approximés de manière efficace. En 2002 S. Khot formula la Conjecture des Jeux Uniques (UGC), qui géneralise le théorème PCP et impliquerait d'importants résultats d'innaproximabilité pour plusieurs problèmes d'optimisation combinatoire (par exemple Max Cut ou Vertex Cover). Intuitivement, la UGC dit que, pour une certaine classe de jeux, appelés uniques, il est NP-dur de décider si l'on peut trouver une solution proche de l'optimale, ou si toutes les solutions sont loin de l'optimale. Cette conjecture est devenue un problème ouvert des plus importants dans la théorie de la complexité et de l'approximation. Dans cet article nous étudions un problème très relié à la UGC: Max-E$2$-Lin2 dans les graphes bipartis. Dans Max-E$2$-Lin2 on a un graphe $G$ ayant deux type d'arêtes, requérant soit la même soit différente couleur pour ses extrémités. Le but est de 2-colorer les sommets de $G$ en maximisant le nombre d'arêtes satisfaites. Nous prouvons que ce problème est APX-complet dans les graphes bipartis et, en utilisant le Théorème de Répétition Paralèlle, nous discutons les conséquences de ce résultat dans le cadre des jeux uniques et la UGC.},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
sorte = "Rapports",
}
