-
F. Giroire,
D. Mazauric,
and J. Moulierac.
Energy Efficient Routing by Switching-Off Network Interfaces,
chapter 10 - Energy-Aware Systems and Networking for Sustainable Initiatives,
pages 207-236.
IGI Global,
june 2012.
[WWW
] [PDF
]
| Abstract: |
|
Several studies exhibit that the traffic load of the routers only has a small influence on their energy consumption.
Hence, the power consumption in networks is strongly related to the number of active network elements, such as interfaces, line cards, base chassis,...
The goal thus is to find a routing that minimizes the (weighted) number of active network elements used when routing.
In this paper, we consider a simplified architecture where a connection between two routers is represented as a link joining two network interfaces.
When a connection is not used, both network interfaces can be turned off.
Therefore, in order to reduce power consumption, the goal is to find the routing that minimizes the number of used links while satisfying all the demands.
We first define formally the problem and we model it as an integer linear program.
Then, we prove that this problem is not in APX, that is there is no polynomial-time constant-factor approximation algorithm.
We propose a heuristic algorithm for this problem and we also prove some negative results about basic greedy and probabilistic algorithms.
Thus we present a study on specific topologies, such as trees, grids and complete graphs, that provide bounds and results useful for real topologies.
We then exhibit the gain in terms of number of network interfaces (leading to a global reduction of approximately 33 MWh for a medium-sized backbone network) for a set of existing network topologies:
we see that for almost all topologies more than one third of the network interfaces can be spared for usual ranges of operation.
Finally, we discuss the impact of energy efficient routing on the stretch factor and on fault tolerance. |
@inbook{GMM12,
author = {Giroire, F. and Mazauric, D. and Moulierac, J.},
title = {Energy Efficient Routing by Switching-Off Network Interfaces},
chapter = {10 - Energy-Aware Systems and Networking for Sustainable Initiatives},
publisher = {IGI Global},
year = {2012},
month = {june},
pages = {207-236},
editor = {Naima Kaabouch and Wen-Chen Hu},
abstract = { Several studies exhibit that the traffic load of the routers only has a small influence on their energy consumption.
Hence, the power consumption in networks is strongly related to the number of active network elements, such as interfaces, line cards, base chassis,...
The goal thus is to find a routing that minimizes the (weighted) number of active network elements used when routing.
In this paper, we consider a simplified architecture where a connection between two routers is represented as a link joining two network interfaces.
When a connection is not used, both network interfaces can be turned off.
Therefore, in order to reduce power consumption, the goal is to find the routing that minimizes the number of used links while satisfying all the demands.
We first define formally the problem and we model it as an integer linear program.
Then, we prove that this problem is not in APX, that is there is no polynomial-time constant-factor approximation algorithm.
We propose a heuristic algorithm for this problem and we also prove some negative results about basic greedy and probabilistic algorithms.
Thus we present a study on specific topologies, such as trees, grids and complete graphs, that provide bounds and results useful for real topologies.
We then exhibit the gain in terms of number of network interfaces (leading to a global reduction of approximately 33 MWh for a medium-sized backbone network) for a set of existing network topologies:
we see that for almost all topologies more than one third of the network interfaces can be spared for usual ranges of operation.
Finally, we discuss the impact of energy efficient routing on the stretch factor and on fault tolerance.},
url = {http://www.igi-global.com/chapter/energy-efficient-routing-switching-off/67312},
pdf = {ftp://ftp-sop.inria.fr/mascotte/personnel/Joanna.Moulierac/pdf/RR-7234.pdf},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
x-pays={},
sorte = "livres-chap",
}
-
O. Amini,
D. Peleg,
S. Pérennes,
I. Sau,
and S. Saurabh.
On the approximability of some degree-constrained subgraph problems.
Discrete Applied Mathematics,
160(12):1661 - 1679,
2012.
[WWW
] [PDF
]
| Abstract: |
|
In this article we provide hardness results and approximation algorithms for the following three natural degree-constrained subgraph problems, which take as input an undirected graph {$G = (V, E )$}.
Let {$d \geq 2$} be a fixed integer.
The Maximum {$d$}âdegree-bounded Connected Subgraph ( MDBCS d ) problem takes as additional input a weight function {$\omega : E \right R^+$} , and asks for a subset {$E'\subseteq E$} such that the subgraph induced by {$E'$} is connected, has maximum degree at most d , and {$\sum_{e\in E'}\omeage(e)$} is maximized.
The Minimum Subgraph of Minimum Degree {$\geq d$} ( MSMD d ) problem involves finding a smallest subgraph of G with minimum degree at least d .
Finally, the Dual Degree-dense k -Subgraph ( DDD k S ) problem consists in finding a subgraph H of G such that {$| V ( H ) | \leq k$} and the minimum degree in H is maximized. |
@article{APP+12,
author = {Amini, O. and Peleg, D. and P\'erennes, S. and Sau, I. and Saurabh, S.},
title = {On the approximability of some degree-constrained subgraph problems},
journal = {Discrete Applied Mathematics},
year = {2012},
volume = {160},
number = {12},
pages = {1661 - 1679},
abstract = {In this article we provide hardness results and approximation algorithms for the following three natural degree-constrained subgraph problems, which take as input an undirected graph {$G = (V, E )$}.
Let {$d \geq 2$} be a fixed integer.
The Maximum {$d$}âdegree-bounded Connected Subgraph ( MDBCS d ) problem takes as additional input a weight function {$\omega : E \right R^+$} , and asks for a subset {$E'\subseteq E$} such that the subgraph induced by {$E'$} is connected, has maximum degree at most d , and {$\sum_{e\in E'}\omeage(e)$} is maximized.
The Minimum Subgraph of Minimum Degree {$\geq d$} ( MSMD d ) problem involves finding a smallest subgraph of G with minimum degree at least d .
Finally, the Dual Degree-dense k -Subgraph ( DDD k S ) problem consists in finding a subgraph H of G such that {$| V ( H ) | \leq k$} and the minimum degree in H is maximized.},
url = {http://www.sciencedirect.com/science/article/pii/S0166218X12001291},
pdf = {http://www.lirmm.fr/~sau/Pubs/DA8948R2.pdf},
x-editorial-board={yes},
x-proceedings={yes},
x-international-audience={yes},
x-pays={IL,IN},
sorte = "rev-int",
}
-
J. Araujo,
J-C. Bermond,
F. Giroire,
F. Havet,
D. Mazauric,
and R. Modrzejewski.
Weighted improper colouring.
Journal of Discrete Algorithms,
16:53-66,
2012.
Note: Selected papers from the 22nd International Workshop on Combinatorial Algorithms (IWOCA 2011).
[WWW
] [PDF
]
| Abstract: |
|
In this paper, we study a colouring problem motivated by a practical frequency assignment problem and, up to our best knowledge, new.
In wireless networks, a node interferes with other nodes, the level of interference depending on numerous parameters: distance between the nodes, geographical topography, obstacles, etc.
We model this with a weighted graph $(G,w)$ where the weight function $w$ on the edges of $G$ represents the noise (interference) between the two end-vertices.
The total interference in a node is then the sum of all the noises of the nodes emitting on the same frequency.
A weighted $t$-improper $k$-colouring of $(G,w)$ is a $k$-colouring of the nodes of $G$ (assignment of $k$ frequencies) such that the interference at each node does not exceed the threshold $t$.
We consider here the Weighted Improper Colouring problem which consists in determining the weighted $t$-improper chromatic number defined as the minimum integer $k$ such that $(G,w)$ admits a weighted $t$-improper $k$-colouring.
We also consider the dual problem, denoted the Threshold Improper Colouring problem, where, given a number $k$ of colours, we want to determine the minimum real $t$ such that $(G,w)$ admits a weighted $t$-improper $k$-colouring.
We show that both problems are NP-hard and first present general upper bounds for both problems;
in particular we show a generalisation of Lov\'asz's Theorem for the weighted $t$-improper chromatic number.
Motivated by the original application, we then study a special interference model on various grids (square, triangular, hexagonal) where a node produces a noise of intensity 1 for its neighbours and a noise of intensity 1/2 for the nodes at distance two.
We derive the weighted $t$-improper chromatic number for all values of $t$. |
@article{ABG+12,
title = {Weighted improper colouring},
author = {Araujo, J. and Bermond, J-C. and Giroire, F. and Havet, F. and Mazauric, D. and Modrzejewski, R.},
journal = {Journal of Discrete Algorithms},
year = {2012},
volume = {16},
pages = {53-66},
note = {Selected papers from the 22nd International Workshop on Combinatorial Algorithms (IWOCA 2011)},
abstract = {In this paper, we study a colouring problem motivated by a practical frequency assignment problem and, up to our best knowledge, new.
In wireless networks, a node interferes with other nodes, the level of interference depending on numerous parameters: distance between the nodes, geographical topography, obstacles, etc.
We model this with a weighted graph $(G,w)$ where the weight function $w$ on the edges of $G$ represents the noise (interference) between the two end-vertices.
The total interference in a node is then the sum of all the noises of the nodes emitting on the same frequency.
A weighted $t$-improper $k$-colouring of $(G,w)$ is a $k$-colouring of the nodes of $G$ (assignment of $k$ frequencies) such that the interference at each node does not exceed the threshold $t$.
We consider here the Weighted Improper Colouring problem which consists in determining the weighted $t$-improper chromatic number defined as the minimum integer $k$ such that $(G,w)$ admits a weighted $t$-improper $k$-colouring.
We also consider the dual problem, denoted the Threshold Improper Colouring problem, where, given a number $k$ of colours, we want to determine the minimum real $t$ such that $(G,w)$ admits a weighted $t$-improper $k$-colouring.
We show that both problems are NP-hard and first present general upper bounds for both problems;
in particular we show a generalisation of Lov\'asz's Theorem for the weighted $t$-improper chromatic number.
Motivated by the original application, we then study a special interference model on various grids (square, triangular, hexagonal) where a node produces a noise of intensity 1 for its neighbours and a noise of intensity 1/2 for the nodes at distance two.
We derive the weighted $t$-improper chromatic number for all values of $t$.},
doi = {10.1016/j.jda.2012.07.001},
url = {http://www.sciencedirect.com/science/article/pii/S1570866712001049},
pdf = {http://hal.archives-ouvertes.fr/docs/00/74/77/55/PDF/WIC-JDiscreteAlgo-Final.pdf},
OPTx-editorial-board={yes},
OPTx-proceedings={no},
OPTx-international-audience={yes},
x-pays = {BR},
sorte = "rev-int",
}
-
J. Araujo,
N. Cohen,
F. Giroire,
and F. Havet.
Good edge-labelling of graphs.
Discrete Applied Mathematics,
160(18):2501-2513,
2012.
[WWW
] [PDF
]
| Abstract: |
|
{A {\it good edge-labelling} of a graph $G$ is a labelling of its edges such that for any two distinct vertices $u$, $v$, there is at most one $(u,v)$-path with non-decreasing labels.
This notion was introduced in~\cite{BCP09} to solve wavelength assignment problems for specific categories of graphs.
In this paper, we aim at characterizing the class of graphs that admit a good edge-labelling.
First, we exhibit infinite families of graphs for which no such edge-labelling can be found. We then show that deciding if a graph admits a good edge-labelling is NP-complete.
Finally, we give
large classes of graphs admitting a good edge-labelling:
$C_3$-free outerplanar graphs, planar graphs of girth at least 6, subcubic $\{C_3,K_{2,3}\}$-free graphs.}
doi = {10.1016/j.dam.2011.07.021} |
@article{ACG+12,
author = {Araujo, J. and Cohen, N. and Giroire, F. and Havet, F.},
title = {Good edge-labelling of graphs},
journal = {Discrete Applied Mathematics},
year = {2012},
volume = {160},
number = {18},
pages = {2501-2513},
abstract={A {\it good edge-labelling} of a graph $G$ is a labelling of its edges such that for any two distinct vertices $u$, $v$, there is at most one $(u,v)$-path with non-decreasing labels.
This notion was introduced in~\cite{BCP09} to solve wavelength assignment problems for specific categories of graphs.
In this paper, we aim at characterizing the class of graphs that admit a good edge-labelling.
First, we exhibit infinite families of graphs for which no such edge-labelling can be found. We then show that deciding if a graph admits a good edge-labelling is NP-complete.
Finally, we give
large classes of graphs admitting a good edge-labelling:
$C_3$-free outerplanar graphs, planar graphs of girth at least 6, subcubic $\{C_3,K_{2,3}\}$-free graphs.}
doi = {10.1016/j.dam.2011.07.021},
url = {http://www.sciencedirect.com/science/article/pii/S0166218X11002824},
pdf = {http://hal.inria.fr/docs/00/38/48/23/PDF/RR-6934.pdf},
x-editorial-board={yes},
x-proceedings={no},
x-international-audience={yes},
x-pays = "BR",
sorte = "rev-int",
}
-
J. Araujo and C. Linhares Sales.
On the Grundy number of graphs with few P4's.
Discrete Applied Mathematics,
160(18):2514-2522,
2012.
Note: V Latin American Algorithms, Graphs, and Optimization Symposium -- Gramado, Brazil, 2009.
[WWW
] [PDF
]
| Abstract: |
|
"The Grundy number of a graph $G$ is the largest number of colors used by any execution of the greedy algorithm to color $G$. The problem of determining the Grundy number of $G$ is polynomial if $G$ is a $P_4$-free graph and NP-hard if $G$ is a $P_5$-free graph. In this article, we define a new class of graphs, the fat-extended $P_4$-laden graphs, and we show a polynomial time algorithm to determine the Grundy number of any graph in this class. Our class intersects the class of $P_5$-free graphs and strictly contains the class of $P_4$-free graphs. More precisely, our result implies that the Grundy number can be computed in polynomial time for any graph of the following classes: $P_4$-reducible, extended $P_4$-reducible, $P_4$-sparse, extended $P_4$-sparse, $P_4$-extendible, $P_4$-lite, $P_4$-tidy, $P_4$-laden and extended $P_4$-laden, which are all strictly contained in the fat-extended $P_4$-laden class." |
@article{ArLi12,
author = "Araujo, J. and Linhares Sales, C.",
title = "On the Grundy number of graphs with few P4's",
journal = "Discrete Applied Mathematics",
year = "2012",
volume = "160",
number = "18",
pages = "2514-2522",
note = "V Latin American Algorithms, Graphs, and Optimization Symposium -- Gramado, Brazil, 2009",
abstract = "The Grundy number of a graph $G$ is the largest number of colors used by any execution of the greedy algorithm to color $G$. The problem of determining the Grundy number of $G$ is polynomial if $G$ is a $P_4$-free graph and NP-hard if $G$ is a $P_5$-free graph. In this article, we define a new class of graphs, the fat-extended $P_4$-laden graphs, and we show a polynomial time algorithm to determine the Grundy number of any graph in this class. Our class intersects the class of $P_5$-free graphs and strictly contains the class of $P_4$-free graphs. More precisely, our result implies that the Grundy number can be computed in polynomial time for any graph of the following classes: $P_4$-reducible, extended $P_4$-reducible, $P_4$-sparse, extended $P_4$-sparse, $P_4$-extendible, $P_4$-lite, $P_4$-tidy, $P_4$-laden and extended $P_4$-laden, which are all strictly contained in the fat-extended $P_4$-laden class.",
doi = "10.1016/j.dam.2011.08.016",
url = "http://www.sciencedirect.com/science/article/pii/S0166218X11003258",
pdf = "http://hal.inria.fr/docs/00/63/90/08/PDF/grundy_p4-full-withmodifs.pdf",
x-editorial-board={yes},
x-proceedings={no},
x-international-audience={yes},
x-pays = {BR},
sorte = "rev-int",
}
-
J. Bang-Jensen,
F. Havet,
and N. Trotignon.
Finding an induced subdivision of a digraph.
Theoretical Computer Science,
443:10-24,
2012.
[WWW
] [PDF
]
| Abstract: |
|
We consider the following problem for oriented graphs and digraphs: Given an oriented graph (digraph) $G$, does it contain an induced subdivision of a prescribed digraph $D$?
The complexity of this problem depends on $D$ and on whether $H$ must be an oriented graph or is allowed to contain 2-cycles.
We give a number of examples of polynomial instances as well as several NP-completeness proofs. |
@article{BHT12,
author = {Bang-Jensen, J. and Havet, F. and Trotignon, N.},
title = {Finding an induced subdivision of a digraph},
JOURNAL = {Theoretical Computer Science},
YEAR = {2012},
VOLUME = {443},
PAGES = {10-24},
abstract = {We consider the following problem for oriented graphs and digraphs: Given an oriented graph (digraph) $G$, does it contain an induced subdivision of a prescribed digraph $D$?
The complexity of this problem depends on $D$ and on whether $H$ must be an oriented graph or is allowed to contain 2-cycles.
We give a number of examples of polynomial instances as well as several NP-completeness proofs.},
URL = {http://hal.inria.fr/inria-00527518/fr/},
PDF = {http://hal.inria.fr/docs/00/52/75/18/PDF/RR-7430.pdf},
x-editorial-board={yes},
x-proceedings={no},
x-international-audience={yes},
x-pays={DK},
sorte = "rev-int",
}
-
L. Barrière,
P. Flocchini,
F. Fomin,
P. Fraigniaud,
N. Nisse,
N. Santoro,
and D. Thilikos.
Connected Graph Searching.
Information and Computation,
219:1-16,
2012.
[WWW
] [PDF
]
| Abstract: |
|
In graph searching game the opponents are a set of searchers and a fugitive in a graph.
The searchers try to capture the fugitive by applying some sequence moves that include placement, removal, or sliding of a searcher along an edge.
The fugitive tries to avoid capture by moving along unguarded paths.
The search number of a graph is the minimum number of searchers required to guarantee the capture of the fugitive.
In this paper, we initiate the study of this game under the natural restriction of connectivity where we demand that in each step of the search the locations of the graph that are clean (i.e. non-accessible to the fugitive) remain connected.
We give evidence that many of the standard mathematical tools used so far in the classic graph searching fail under the connectivity requirement.
We also settle the question on ``the price of connectivity'' that is how many searchers more are required for searching a graph when the connectivity demand is imposed.
We make estimations of the price of connectivity on general graphs and we provide tight bounds for the case of trees.
In particular, for an $n$-vertex graph the ratio between the connected searching number and the non-connected one is $O(\log n)$ while for trees this ratio is always at most 2.
We also conjecture that this constant-ratio upper bound for trees holds also for all graphs.
Our combinatorial results imply a complete characterization of connected graph searching on trees.
It is based on a forbidden-graph characterization of the connected search number.
We prove that the connected search game is monotone for trees, i.e. restricting search strategies to only those where the clean territories increase monotonically does not require more searchers.
A consequence of our results is that the connected search number can be computed in polynomial time on trees, moreover, we show how to make this algorithm distributed.
Finally, we reveal connections of this parameter to other invariants on trees such as the Horton-Stralher number. |
@article{BFF+12,
author = {Barri{\`e}re, L. and Flocchini, P. and Fomin, F. and Fraigniaud, P. and Nisse, N. and Santoro, N. and Thilikos, D.},
title = {{C}onnected {G}raph {S}earching},
journal = {Information and Computation},
year = {2012},
volume = {219},
pages = {1-16},
abstract = {In graph searching game the opponents are a set of searchers and a fugitive in a graph.
The searchers try to capture the fugitive by applying some sequence moves that include placement, removal, or sliding of a searcher along an edge.
The fugitive tries to avoid capture by moving along unguarded paths.
The search number of a graph is the minimum number of searchers required to guarantee the capture of the fugitive.
In this paper, we initiate the study of this game under the natural restriction of connectivity where we demand that in each step of the search the locations of the graph that are clean (i.e. non-accessible to the fugitive) remain connected.
We give evidence that many of the standard mathematical tools used so far in the classic graph searching fail under the connectivity requirement.
We also settle the question on ``the price of connectivity'' that is how many searchers more are required for searching a graph when the connectivity demand is imposed.
We make estimations of the price of connectivity on general graphs and we provide tight bounds for the case of trees.
In particular, for an $n$-vertex graph the ratio between the connected searching number and the non-connected one is $O(\log n)$ while for trees this ratio is always at most 2.
We also conjecture that this constant-ratio upper bound for trees holds also for all graphs.
Our combinatorial results imply a complete characterization of connected graph searching on trees.
It is based on a forbidden-graph characterization of the connected search number.
We prove that the connected search game is monotone for trees, i.e. restricting search strategies to only those where the clean territories increase monotonically does not require more searchers.
A consequence of our results is that the connected search number can be computed in polynomial time on trees, moreover, we show how to make this algorithm distributed.
Finally, we reveal connections of this parameter to other invariants on trees such as the Horton-Stralher number.},
url = {http://dx.doi.org/10.1016/j.ic.2012.08.004},
pdf = {http://hal.inria.fr/docs/00/74/19/48/PDF/journalFinal.pdf},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
x-pays={ES,CA,NO,GR},
sorte = "rev-int",
}
-
S. Baruah,
V. Bonifaci,
G. D'Angelo,
H. Li,
A. Marchetti-Spaccamela,
N. Megow,
and L. Stougie.
Scheduling Real-time Mixed-criticality Jobs.
IEEE Transactions on Computers,
61(8):1140-1152,
2012.
[WWW
] [PDF
]
| Abstract: |
|
Many safety-critical embedded systems are subject to certification requirements;
some systems may be required to meet multiple sets of certification requirements, from different certification authorities.
Certification requirements in such "mixed-criticality" systems give rise to interesting scheduling problems, that cannot be satisfactorily addressed using techniques from conventional scheduling theory.
In this paper, we study a formal model for representing such mixed-criticality workloads.
We demonstrate first the intractability of determining whether a system specified in this model can be scheduled to meet all its certification requirements, even for systems subject to merely two sets of certification requirements.
Then we quantify, via the metric of processor speedup factor, the effectiveness of two techniques, reservation-based scheduling and priority-based scheduling, that are widely used in scheduling such mixed-criticality systems, showing that the latter of the two is superior to the former.
We also show that the speedup factors we obtain are tight for these two techniques. |
@article{BBD+12,
author = {Baruah, S. and Bonifaci, V. and D'Angelo, G. and Li, H. and Marchetti-Spaccamela, A. and Megow, N. and Stougie, L.},
title = {{Scheduling Real-time Mixed-criticality Jobs}},
journal = {IEEE Transactions on Computers},
year = {2012},
volume = {61},
number = {8},
pages = {1140-1152},
publisher = {IEEE},
abstract = {{Many safety-critical embedded systems are subject to certification requirements;
some systems may be required to meet multiple sets of certification requirements, from different certification authorities.
Certification requirements in such "mixed-criticality" systems give rise to interesting scheduling problems, that cannot be satisfactorily addressed using techniques from conventional scheduling theory.
In this paper, we study a formal model for representing such mixed-criticality workloads.
We demonstrate first the intractability of determining whether a system specified in this model can be scheduled to meet all its certification requirements, even for systems subject to merely two sets of certification requirements.
Then we quantify, via the metric of processor speedup factor, the effectiveness of two techniques, reservation-based scheduling and priority-based scheduling, that are widely used in scheduling such mixed-criticality systems, showing that the latter of the two is superior to the former.
We also show that the speedup factors we obtain are tight for these two techniques.}},
doi = {10.1109/TC.2011.142 },
url = {http://hal.inria.fr/hal-00643942},
pdf = {http://hal.inria.fr/hal-00643942/PDF/MixedCriticality-journal.pdf},
OPTx-editorial-board={yes},
OPTx-proceedings={no},
OPTx-international-audience={yes},
x-pays = {IT,IN,CN,DE,NL,US},
sorte = "rev-int",
}
-
R. Bauer,
G. D'Angelo,
D. Delling,
A. Schumm,
and D. Wagner.
The Shortcut Problem - Complexity and Algorithms.
Journal of Graph Algorithms and Applications,
16(2):447-481,
2012.
[WWW
] [PDF
]
| Abstract: |
|
We study a graph-augmentation problem arising from a technique applied in recent approaches for route planning.
Many such methods enhance the graph by inserting shortcuts, i.e., additional edges (u,v) such that the length of (u,v) is the distance from u to v.
Given a weighted, directed graph G and a number c in Z, the shortcut problem asks how to insert c shortcuts into G such that the expected number of edges that are contained in an edge-minimal shortest path from a random node s to a random node t is minimal.
In this work, we study the algorithmic complexity of the problem and give approximation algorithms for a special graph class.
Further, we state ILP-based exact approaches and show how to stochastically evaluate a given shortcut assignment on graphs that are too large to do so exactly. |
@article{BDD+12,
author = {Bauer, R. and D'Angelo, G. and Delling, D. and Schumm, A. and Wagner, D.},
title = {{The Shortcut Problem - Complexity and Algorithms}},
journal = {Journal of Graph Algorithms and Applications},
year = {2012},
volume = {16},
number = {2},
pages = {447-481},
publisher = {Journal of Graph Algorithms and Applications},
abstract = {{We study a graph-augmentation problem arising from a technique applied in recent approaches for route planning.
Many such methods enhance the graph by inserting shortcuts, i.e., additional edges (u,v) such that the length of (u,v) is the distance from u to v.
Given a weighted, directed graph G and a number c in Z, the shortcut problem asks how to insert c shortcuts into G such that the expected number of edges that are contained in an edge-minimal shortest path from a random node s to a random node t is minimal.
In this work, we study the algorithmic complexity of the problem and give approximation algorithms for a special graph class.
Further, we state ILP-based exact approaches and show how to stochastically evaluate a given shortcut assignment on graphs that are too large to do so exactly.}},
doi = {10.7155/jgaa.00270},
url = {http://hal.inria.fr/hal-00728877},
pdf = {http://hal.inria.fr/hal-00728877/PDF/02-IJGAA.pdf},
OPTx-editorial-board={yes},
OPTx-proceedings={no},
OPTx-international-audience={yes},
x-pays = {IT,DE},
sorte = "rev-int",
}
-
J-C. Bermond,
D. Coudert,
J. Moulierac,
S. Pérennes,
I. Sau,
and F. Solano Donado.
GMPLS Label Space Minimization through Hypergraph Layouts.
Theoretical Computer Science (TCS),
444:3-16,
July 2012.
[WWW
] [PDF
]
| Abstract: |
|
{A}ll-{O}ptical {L}abel {S}witching ({AOLS}) is a new technology that performs packet forwarding without any optical-electrical-optical conversions. {I}n this report, we study the problem of routing a set of requests in {AOLS} networks using {GMPLS} technology, with the aim of minimizing the number of labels required to ensure the forwarding. {W}e first formalize the problem by associating to each routing strategy a logical hypergraph, called a hypergraph layout, whose hyperarcs are dipaths of the physical graph, called tunnels in {GMPLS} terminology. {W}e define a cost function for the hypergraph layout, depending on its total length plus its total hop count. {M}inimizing the cost of the design of an {AOLS} network can then be expressed as finding a minimum cost hypergraph layout. {W}e prove hardness results for the problem, namely for general directed networks we prove that it is {NP}-hard to find a {C} log n-approximation, where {C} is a positive constant and n is the number of nodes of the
network. {F}or symmetric directed networks, we prove that the problem is {APX}-hard. {T}hese hardness results hold even if the traffic instance is a partial broadcast. {O}n the other hand, we provide approximation algorithms, in particular an {O}(log n)-approximation for symmetric directed networks. {F}inally, we focus on the case where the physical network is a directed path, providing a polynomial-time dynamic programming algorithm for a fixed number k of sources running in {O}(n^{k+2}) time. |
@article{BCM+11,
title = { {GMPLS} {L}abel {S}pace {M}inimization through {H}ypergraph {L}ayouts},
author = {Bermond, J-C. and Coudert, D. and Moulierac, J. and P\'erennes, S. and Sau, I. and Solano Donado, F.},
journal = {Theoretical Computer Science (TCS)},
volume = {444},
pages = {3-16},
month = jul,
x-pays = {ES,PL},
abstract = {{A}ll-{O}ptical {L}abel {S}witching ({AOLS}) is a new technology that performs packet forwarding without any optical-electrical-optical conversions. {I}n this report, we study the problem of routing a set of requests in {AOLS} networks using {GMPLS} technology, with the aim of minimizing the number of labels required to ensure the forwarding. {W}e first formalize the problem by associating to each routing strategy a logical hypergraph, called a hypergraph layout, whose hyperarcs are dipaths of the physical graph, called tunnels in {GMPLS} terminology. {W}e define a cost function for the hypergraph layout, depending on its total length plus its total hop count. {M}inimizing the cost of the design of an {AOLS} network can then be expressed as finding a minimum cost hypergraph layout. {W}e prove hardness results for the problem, namely for general directed networks we prove that it is {NP}-hard to find a {C} log n-approximation, where {C} is a positive constant and n is the number of nodes of the
network. {F}or symmetric directed networks, we prove that the problem is {APX}-hard. {T}hese hardness results hold even if the traffic instance is a partial broadcast. {O}n the other hand, we provide approximation algorithms, in particular an {O}(log n)-approximation for symmetric directed networks. {F}inally, we focus on the case where the physical network is a directed path, providing a polynomial-time dynamic programming algorithm for a fixed number k of sources running in {O}(n^{k+2}) time.},
OPTkeywords = {{GMPLS}; optical networks; label stacking; hypergraph layout; approximation algorithms; dynamic programming.},
language = {{A}nglais},
OPTaffiliation = {{MASCOTTE} - {INRIA} {S}ophia {A}ntipolis / {L}aboratoire {I}3{S} - {INRIA} - {U}niversit{\'e} de {N}ice {S}ophia-{A}ntipolis - {CNRS} : {UMR}6070 - {I}nstitute of {T}elecommunications - {W}arsaw {U}niversity of {T}echnology },
year = {2012},
URL = {http://dx.doi.org/10.1016/j.tcs.2012.01.033},
pdf = {ftp://ftp-sop.inria.fr/mascotte/personnel/Joanna.Moulierac/pdf/RR-7071.pdf},
OPTx-editorial-board={yes},
OPTx-proceedings={no},
OPTx-international-audience={yes},
sorte = "rev-int",
}
-
J-C. Bermond and J. Moulierac.
Internet et la théorie des graphes.
Revue TDC Textes et documents pour la Classe : la révolution Internet,
1042:32-33,
2012.
[WWW
] [PDF
]
| Abstract: |
|
La th{\'e}orie des graphes constitue un domaine des math{\'e}matiques qui s'est d{\'e}velopp{\'e} au sein de disciplines diverses telles que la chimie (mod{\'e}lisation de structures), la biologie (g{\'e}nome), les sciences sociales (mod{\'e}lisation des relations) et le transport (r{\'e}seaux routiers, {\'e}lectriques, etc.).
Le cycle eul{\'e}rien et le cycle hamiltonien R{\'e}seaux internet et graphes " petit-monde " Comment calculer un plus court chemin ? |
@article{BeMo12,
author = {Bermond, J-C. and Moulierac, J.},
title = {Internet et la th\'eorie des graphes},
journal = {Revue TDC Textes et documents pour la Classe : la r\'evolution Internet},
year = {2012},
volume = {1042},
pages = {32-33},
abstract = {{La th{\'e}orie des graphes constitue un domaine des math{\'e}matiques qui s'est d{\'e}velopp{\'e} au sein de disciplines diverses telles que la chimie (mod{\'e}lisation de structures), la biologie (g{\'e}nome), les sciences sociales (mod{\'e}lisation des relations) et le transport (r{\'e}seaux routiers, {\'e}lectriques, etc.).
Le cycle eul{\'e}rien et le cycle hamiltonien R{\'e}seaux internet et graphes " petit-monde " Comment calculer un plus court chemin ?}},
url = {http://hal.archives-ouvertes.fr/hal-00747752},
pdf = {http://hal.archives-ouvertes.fr/hal-00747752/PDF/TDCfinal.pdf},
OPTx-editorial-board={yes},
OPTx-proceedings={no},
OPTx-international-audience={no},
x-pays = {},
sorte = "rev-nat",
}
-
J-C. Bermond and J. Peters.
Optimal Gathering in Radio Grids with Interference.
Theoretical Computer Science,
457:10-26,
October 2012.
[WWW
] [PDF
]
| Abstract: |
|
We study the problem of gathering information from the nodes
of a
radio network into a central node. We model the network
of possible transmissions by a graph and consider a binary model of
interference in which two transmissions interfere if the distance in
the graph from the sender of one transmission to the receiver of the
other is $d_I$ or less. A {\em round} is a set of non-interfering
transmissions. In this paper, we determine the exact number of rounds
required to gather one piece of information from each node of a square
two-dimensional grid into the central node. If $d_I = 2k-1$ is odd,
then the number of rounds is $k(N-1)-c_k$ where $N$ is the number of
nodes and $c_k$ is a constant that depends on $k$. If $d_I = 2k$ is
even, then the number of rounds is $(k+\frac{1}{4})(N-1)-c'_k$ where
$c'_k$ is a constant that depends on $k$.
The even case uses a method based on linear programming duality to
prove the lower bound, and sophisticated algorithms using the symmetry
of the grid and non-shortest paths to establish the matching upper
bound. We then generalize our results to hexagonal grids. |
@Article{BePe12,
author = {Bermond, J-C. and Peters, J.},
title = {Optimal Gathering in Radio Grids with Interference},
journal = {Theoretical Computer Science},
year = {2012},
month = {October},
volume = {457},
pages = {10-26},
abstract = {We study the problem of gathering information from the nodes
of a
radio network into a central node. We model the network
of possible transmissions by a graph and consider a binary model of
interference in which two transmissions interfere if the distance in
the graph from the sender of one transmission to the receiver of the
other is $d_I$ or less. A {\em round} is a set of non-interfering
transmissions. In this paper, we determine the exact number of rounds
required to gather one piece of information from each node of a square
two-dimensional grid into the central node. If $d_I = 2k-1$ is odd,
then the number of rounds is $k(N-1)-c_k$ where $N$ is the number of
nodes and $c_k$ is a constant that depends on $k$. If $d_I = 2k$ is
even, then the number of rounds is $(k+\frac{1}{4})(N-1)-c'_k$ where
$c'_k$ is a constant that depends on $k$.
The even case uses a method based on linear programming duality to
prove the lower bound, and sophisticated algorithms using the symmetry
of the grid and non-shortest paths to establish the matching upper
bound. We then generalize our results to hexagonal grids.},
url = {http://hal.archives-ouvertes.fr/hal-00747751},
pdf = {http://hal.archives-ouvertes.fr/docs/00/74/77/51/PDF/bermond-peters-revised.pdf},
OPTx-editorial-board={yes},
OPTx-proceedings={no},
OPTx-international-audience={yes},
x-pays = {CA},
sorte = "rev-int",
}
-
S. Bhadra and A. Ferreira.
Computing multicast trees in dynamic networks and the complexity of connected components in evolving graphs.
J. Internet Services and Applications,
3(3):269-275,
2012.
[WWW
] [PDF
]
| Abstract: |
|
New technologies and the deployment of mobile and nomadic services are driving the emergence of complex communications networks, that have a highly dynamic behavior.
This naturally engenders new route-discovery problems under changing conditions over these networks.
Unfortunately, the temporal variations in the network topology are hard to be effectively captured in a classical graph model.
In this paper, we use and extend a recently proposed graph theoretic model, which helps capture the evolving characteristi- c of such networks, in order to compute multicast trees with minimum overall transmission time for a class of wireless mobile dynamic networks.
We first show that computing different types of strongly connected components in this model is NP-Complete, and then propose an algorithm to build all rooted directed minimum spanning trees in already identified strongly connected components. |
@article{BhFe12,
author = {Bhadra, S. and Ferreira, A.},
title = {Computing multicast trees in dynamic networks and the complexity of connected components in evolving graphs},
journal = {J. Internet Services and Applications},
volume = {3},
number = {3},
year = {2012},
pages = {269-275},
abstract = {New technologies and the deployment of mobile and nomadic services are driving the emergence of complex communications networks, that have a highly dynamic behavior.
This naturally engenders new route-discovery problems under changing conditions over these networks.
Unfortunately, the temporal variations in the network topology are hard to be effectively captured in a classical graph model.
In this paper, we use and extend a recently proposed graph theoretic model, which helps capture the evolving characteristi- c of such networks, in order to compute multicast trees with minimum overall transmission time for a class of wireless mobile dynamic networks.
We first show that computing different types of strongly connected components in this model is NP-Complete, and then propose an algorithm to build all rooted directed minimum spanning trees in already identified strongly connected components.},
doi = {http://dx.doi.org/10.1007/s13174-012-0073-z},
url = {http://hal.inria.fr/inria-00072057},
pdf = {http://hal.inria.fr/docs/00/07/20/57/PDF/RR-4531.pdf},
OPTx-editorial-board={yes},
OPTx-proceedings={no},
OPTx-international-audience={yes},
x-pays = {IN},
sorte = "rev-int",
}
-
V. Campos,
A. Gyárfás,
F. Havet,
C. Linhares Sales,
and F. Maffray.
New bounds on the Grundy number of products of graphs.
Journal of Graph Theory,
71(1):78-88,
2012.
[WWW
] [PDF
]
| Abstract: |
|
The Grundy number of a graph $G$ is the largest $k$ such that $G$ has a greedy $k$-colouring, that is, a colouring with $k$ colours obtained by applying the greedy algorithm according to some ordering of the vertices of $G$.
In this paper, we give new bounds on the Grundy number of the product of two graphs. |
@article{CGH+12,
author = {Campos, V. and Gy\'arf\'as, A. and Havet, F. and Linhares Sales, C. and Maffray, F.},
title = {New bounds on the Grundy number of products of graphs},
journal = {Journal of Graph Theory},
YEAR = {2012},
VOLUME = {71},
NUMBER= {1},
PAGES = {78-88},
abstract = {The Grundy number of a graph $G$ is the largest $k$ such that $G$ has a greedy $k$-colouring, that is, a colouring with $k$ colours obtained by applying the greedy algorithm according to some ordering of the vertices of $G$.
In this paper, we give new bounds on the Grundy number of the product of two graphs.},
URL={http://hal.archives-ouvertes.fr/inria-00470158/fr/},
PDF = {http://hal.archives-ouvertes.fr/docs/00/47/01/58/PDF/RR-7243.pdf },
x-editorial-board={yes},
x-proceedings={yes},
x-international-audience={yes},
x-pays = {BR, HU},
sorte = "rev-int",
}
-
Y. Chen,
E. Le Merrer,
Z. Li,
Y. Liu,
and G. Simon.
OAZE: A Network-Friendly Distributed Zapping System for Peer-to-Peer IPTV.
Computer Networks,
56(1):365-377,
2012.
[WWW
] [PDF
]
| Abstract: |
|
IPTV systems attracting millions of users are now commonly deployed on peer-to-peer (P2P) infrastructures. Each channel is associated with a P2P overlay network for\
med by the users who receive, watch and redistribute this channel. However, zapping from one P2P overlay to another requires a significant amount of time, and therefore the P2P\
IPTV experience is not as good as for a multicast-based IPTV. In order to speed up the switching process and to reduce the overall cross-domain traffic generated by the IPTV s\
ystem, we propose a distributed algorithm called OAZE for Overlay Augmentation for Zapping Experience. The main idea is that every peer maintains connections to other peers in \
a subset of all channels to which it is likely to zap, and collaborates with the other peers in its channel for the remaining channels. We present in this paper the OAZE mechan\
ism. We focus in particular on the channel assignment problem, which consists in determining the optimal distribution of the responsibility to maintain contact peers in other c\
hannels in a given overlay. We propose an approximate algorithm having guaranteed performances in comparison to the optimal one, and an algorithm that is simpler and more pract\
ical. Simulations show that OAZE leads to substantial improvements on the connections between peers, resulting in less switching delay and lower network cost. This approach is \
overlay independent and is an appealing add-on for existing P2P IPTV systems. |
@article{CLL+11,
author = {Y. Chen and E. Le Merrer and Z. Li and Y. Liu and G. Simon},
title = {{OAZE}: A Network-Friendly Distributed Zapping System for Peer-to-Peer {IPTV}},
journal = {Computer Networks},
year = {2012},
volume = {56},
number = {1},
pages = {365-377},
abstract = {IPTV systems attracting millions of users are now commonly deployed on peer-to-peer (P2P) infrastructures. Each channel is associated with a P2P overlay network for\
med by the users who receive, watch and redistribute this channel. However, zapping from one P2P overlay to another requires a significant amount of time, and therefore the P2P\
IPTV experience is not as good as for a multicast-based IPTV. In order to speed up the switching process and to reduce the overall cross-domain traffic generated by the IPTV s\
ystem, we propose a distributed algorithm called OAZE for Overlay Augmentation for Zapping Experience. The main idea is that every peer maintains connections to other peers in \
a subset of all channels to which it is likely to zap, and collaborates with the other peers in its channel for the remaining channels. We present in this paper the OAZE mechan\
ism. We focus in particular on the channel assignment problem, which consists in determining the optimal distribution of the responsibility to maintain contact peers in other c\
hannels in a given overlay. We propose an approximate algorithm having guaranteed performances in comparison to the optimal one, and an algorithm that is simpler and more pract\
ical. Simulations show that OAZE leads to substantial improvements on the connections between peers, resulting in less switching delay and lower network cost. This approach is \
overlay independent and is an appealing add-on for existing P2P IPTV systems.},
pdf = {ftp://ftp-sop.inria.fr/mascotte/Publications/CLL+11.pdf},
url = {http://dx.doi.org/10.1016/j.comnet.2011.09.002},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
x-pays = {},
sorte = "rev-int",
}
-
D. Coudert,
F. Huc,
and D. Mazauric.
A Distributed Algorithm for Computing the Node Search Number in Trees.
Algorithmica,
63(1-2):158-190,
2012.
[WWW
] [PDF
]
| Abstract: |
|
We present a distributed algorithm to compute the node search number
in trees. This algorithm extends the centralized algorithm proposed
by Ellis \emph{et al.} [EST94]. It can be executed in an
asynchronous environment, requires an overall computation time of
$O(n\log{n})$, and $n$ messages of $\log_3{n}+4$ bits each.
The main contribution of this work lies in the data structure
proposed to design our algorithm, called \emph{hierarchical
decomposition}. This simple and flexible data structure is used
for four operations: updating the node search number after addition
or deletion of any tree-edges in a distributed fashion; computing it
in a tree whose edges are added sequentially and in any order;
computing other graph invariants such as the process number and the
edge search number, by changing only initialization rules; extending
our algorithms for trees and forests of unknown size (using messages
of up to $2\log_3{n}+5$ bits). |
@article{CHM11,
author = {D. Coudert and F. Huc and D. Mazauric},
title = {A Distributed Algorithm for Computing the Node Search Number in Trees},
journal = {Algorithmica},
year = {2012},
volume = {63},
number = {1-2},
pages = {158-190},
abstract = { We present a distributed algorithm to compute the node search number
in trees. This algorithm extends the centralized algorithm proposed
by Ellis \emph{et al.} [EST94]. It can be executed in an
asynchronous environment, requires an overall computation time of
$O(n\log{n})$, and $n$ messages of $\log_3{n}+4$ bits each.
The main contribution of this work lies in the data structure
proposed to design our algorithm, called \emph{hierarchical
decomposition}. This simple and flexible data structure is used
for four operations: updating the node search number after addition
or deletion of any tree-edges in a distributed fashion; computing it
in a tree whose edges are added sequentially and in any order;
computing other graph invariants such as the process number and the
edge search number, by changing only initialization rules; extending
our algorithms for trees and forests of unknown size (using messages
of up to $2\log_3{n}+5$ bits).},
url = {http://dx.doi.org/10.1007/s00453-011-9524-3},
pdf = {http://hal.inria.fr/docs/00/58/78/19/PDF/bare_conf-noformat.pdf},
OPTx-editorial-board={yes},
OPTx-proceedings={no},
OPTx-international-audience={yes},
x-pays={CH},
sorte = "rev-int",
}
-
G. D'Angelo,
G. Di Stefano,
and A. Navarra.
Minimize the Maximum Duty in Multi-interface Networks.
Algorithmica,
63(1-2):274-295,
2012.
[WWW
] [PDF
]
| Abstract: |
|
We consider devices equipped with multiple wired or wireless interfaces.
By switching of various interfaces, each device might establish several connections.
A connection is established when the devices at its endpoints share at least one active interface.
Each interface is assumed to require an activation cost.
In this paper, we consider two basic networking problems in the field of multi-interface networks.
The first one, known as the Coverage problem, requires to establish the connections defined by a network.
The second one, known as Connectivity problem, requires to guarantee a connecting path between any pair of nodes of a network.
Both are subject to the constraint of keeping as low as possible the maximum cost set of active interfaces at each single node.
We study the problems of minimizing the maximum cost set of active interfaces among the nodes of the network in order to cover all the edges in the first case, or to ensure connectivity in the second case.
We prove that the Coverage problem is NP-hard for any fixed $\Delta$$\ge$5 and k$\ge$16, with $\Delta$ being the maximum degree, and k being the number of different interfaces among the network.
We also show that, unless P=NP, the problem cannot be approximated within a factor of $\eta$$\Delta$, for a certain constant $\eta$.
We then provide a general approximation algorithm which guarantees a factor of O((1+b)$\Delta$), with b being a parameter depending on the topology of the input graph.
Interestingly, b can be bounded by a constant for many graph classes. Other approximation and exact algorithms for special cases are presented.
Concerning the Connectivity problem, we prove that it is NP-hard for any fixed $\Delta$$\ge$3 and k$\ge$10.
Also for this problem, the inapproximability result holds, that is, unless P=NP, the problem cannot be approximated within a factor of $\eta$$\Delta$, for a certain constant $\eta$.
We then provide approximation and exact algorithms for the general problem and for special cases, respectively. |
@article{DDN12a,
author = {D'Angelo, G. and Di Stefano, G. and Navarra, A.},
title = {{Minimize the Maximum Duty in Multi-interface Networks}},
journal = {Algorithmica},
year = {2012},
volume = {63},
number = {1-2},
pages = {274-295},
publisher = {Springer},
abstract = {{We consider devices equipped with multiple wired or wireless interfaces.
By switching of various interfaces, each device might establish several connections.
A connection is established when the devices at its endpoints share at least one active interface.
Each interface is assumed to require an activation cost.
In this paper, we consider two basic networking problems in the field of multi-interface networks.
The first one, known as the Coverage problem, requires to establish the connections defined by a network.
The second one, known as Connectivity problem, requires to guarantee a connecting path between any pair of nodes of a network.
Both are subject to the constraint of keeping as low as possible the maximum cost set of active interfaces at each single node.
We study the problems of minimizing the maximum cost set of active interfaces among the nodes of the network in order to cover all the edges in the first case, or to ensure connectivity in the second case.
We prove that the Coverage problem is NP-hard for any fixed $\Delta$$\ge$5 and k$\ge$16, with $\Delta$ being the maximum degree, and k being the number of different interfaces among the network.
We also show that, unless P=NP, the problem cannot be approximated within a factor of $\eta$$\Delta$, for a certain constant $\eta$.
We then provide a general approximation algorithm which guarantees a factor of O((1+b)$\Delta$), with b being a parameter depending on the topology of the input graph.
Interestingly, b can be bounded by a constant for many graph classes. Other approximation and exact algorithms for special cases are presented.
Concerning the Connectivity problem, we prove that it is NP-hard for any fixed $\Delta$$\ge$3 and k$\ge$10.
Also for this problem, the inapproximability result holds, that is, unless P=NP, the problem cannot be approximated within a factor of $\eta$$\Delta$, for a certain constant $\eta$.
We then provide approximation and exact algorithms for the general problem and for special cases, respectively.}},
doi = {10.1007/s00453-011-9531-4},
url = {http://hal.inria.fr/hal-00643961},
pdf = {http://hal.inria.fr/hal-00643961/PDF/Min-Max-coverage.pdf},
OPTx-editorial-board={yes},
OPTx-proceedings={no},
OPTx-international-audience={yes},
x-pays = {IT},
sorte = "rev-int",
}
-
L. Esperet,
F. Kardos,
and D. Král'.
A superlinear bound on the number of perfect matchings in cubic bridgeless graphs.
European Journal of Combinatorics,
33(5):767-798,
2012.
[WWW
] [PDF
]
| Abstract: |
|
Lov{\'{a}}sz and Plummer conjectured in the 1970's that cubic bridgeless
graphs have exponentially many perfect matchings. This conjecture has
been verified for bipartite graphs by Voorhoeve in 1979, and for planar
graphs by Chudnovsky and Seymour in 2008, but in general only linear
bounds are known. In this paper, we provide the first superlinear bound
in the general case. |
@article{EKK12,
author = {Esperet, L. and Kardo{\v{s}}, F. and Kr{\'{a}}l', D. },
title = {A superlinear bound on the number of perfect matchings in cubic bridgeless graphs},
journal = {European Journal of Combinatorics},
volume = {33},
number = {5},
year = {2012},
pages = {767-798},
abstract = {Lov{\'{a}}sz and Plummer conjectured in the 1970's that cubic bridgeless
graphs have exponentially many perfect matchings. This conjecture has
been verified for bipartite graphs by Voorhoeve in 1979, and for planar
graphs by Chudnovsky and Seymour in 2008, but in general only linear
bounds are known. In this paper, we provide the first superlinear bound
in the general case.},
url = {http://dx.doi.org/10.1016/j.ejc.2011.09.027},
pdf = {ftp://ftp-sop.inria.fr/mascotte/Publications/EKK11.pdf},
x-editorial-board={yes},
x-proceedings={no},
x-international-audience={yes},
x-pays = {CZ, SK},
sorte = "rev-int",
}
-
A. Ferreira and A. Jarry.
Minimum-Energy Broadcast Routing in Dynamic Wireless Networks.
Journal of Green Engineering,
2(2):115-123,
2012.
[PDF
]
| Abstract: |
|
One of the new challenges facing research in wireless networks is the design of algorithms and protocols that are energy aware.
A good example is the minimum-energy broadcast routing problem for a static network in the plane, which attracted a great deal of attention these past years.
The problem is NP-hard and its approximation ratio complexity is a solution proved to be within a factor 6 of the optimal, based on finding a Minimum Spanning Tree of the static planar network.
In this paper, we use for the first time the evolving graph combinatorial model as a tool to prove an NP-Completeness result, namely that computing a Minimum Spanning Tree of a planar network in the presence of mobility is actually NP-Complete.
This result implies that the above approximation solution cannot be used in dynamic wireless networks.
On the positive side, we give a polynomial-time algorithm to build a rooted spanning tree of an on/off network, that minimizes the maximum energy used. |
@article{FJ12,
author = {Ferreira, A. and Jarry, A.},
title = {Minimum-Energy Broadcast Routing in Dynamic Wireless Networks},
journal = {Journal of Green Engineering},
year = {2012},
volume = {2},
number = {2},
pages = {115-123},
Abstract = {One of the new challenges facing research in wireless networks is the design of algorithms and protocols that are energy aware.
A good example is the minimum-energy broadcast routing problem for a static network in the plane, which attracted a great deal of attention these past years.
The problem is NP-hard and its approximation ratio complexity is a solution proved to be within a factor 6 of the optimal, based on finding a Minimum Spanning Tree of the static planar network.
In this paper, we use for the first time the evolving graph combinatorial model as a tool to prove an NP-Completeness result, namely that computing a Minimum Spanning Tree of a planar network in the presence of mobility is actually NP-Complete.
This result implies that the above approximation solution cannot be used in dynamic wireless networks.
On the positive side, we give a polynomial-time algorithm to build a rooted spanning tree of an on/off network, that minimizes the maximum energy used.},
PDF = {http://riverpublishers.com/journal/journal_articles/RP_Journal_1904-4720_222.pdf},
OPTx-editorial-board = {yes},
OPTx-proceedings = {no},
OPTx-international-audience = {yes},
x-pays = {CH},
sorte = "rev-int",
}
-
D. Gonçalves,
F. Havet,
A. Pinlou,
and S. Thomassé.
On spanning galaxies in digraphs.
Discrete Applied Mathematics,
160(6):744-754,
2012.
[WWW
] [PDF
]
| Abstract: |
|
In a directed graph, a {\it star} is an arborescence with at least one arc, in which the root dominates all the other vertices.
A {\it galaxy} is a vertex-disjoint union of stars.
In this paper, we consider the \textsc{Spanning Galaxy} problem of deciding whether a digraph $D$ has a spanning galaxy or not.
We show that although this problem is NP-complete (even when restricted to acyclic digraphs), it becomes polynomial-time solvable when restricted to strong digraphs.
In fact, we prove that restricted to this class, the \pb\ is equivalent to the problem of deciding if a strong digraph has a strong digraph with an even number of vertices.
We then show a polynomial-time algorithm to solve this problem.
We also consider some parameterized version of the \pb.
Finally, we improve some results concerning the notion of directed star arboricity of a digraph $D$, which is the minimum number of galaxies needed to cover all the arcs of $D$.
We show in particular that $dst(D)\leq \Delta(D)+1$ for every digraph $D$ and that $dst(D)\leq \Delta(D)$ for every acyclic digraph $D$. |
@ARTICLE{GHP+12,
AUTHOR={Gon\c{c}alves, D. and Havet, F. and Pinlou, A. and Thomass\'e, S.},
TITLE={On spanning galaxies in digraphs},
JOURNAL = {Discrete Applied Mathematics},
YEAR = {2012},
VOLUME = {160},
NUMBER = {6},
PAGES = {744-754},
abstract = { In a directed graph, a {\it star} is an arborescence with at least one arc, in which the root dominates all the other vertices.
A {\it galaxy} is a vertex-disjoint union of stars.
In this paper, we consider the \textsc{Spanning Galaxy} problem of deciding whether a digraph $D$ has a spanning galaxy or not.
We show that although this problem is NP-complete (even when restricted to acyclic digraphs), it becomes polynomial-time solvable when restricted to strong digraphs.
In fact, we prove that restricted to this class, the \pb\ is equivalent to the problem of deciding if a strong digraph has a strong digraph with an even number of vertices.
We then show a polynomial-time algorithm to solve this problem.
We also consider some parameterized version of the \pb.
Finally, we improve some results concerning the notion of directed star arboricity of a digraph $D$, which is the minimum number of galaxies needed to cover all the arcs of $D$.
We show in particular that $dst(D)\leq \Delta(D)+1$ for every digraph $D$ and that $dst(D)\leq \Delta(D)$ for every acyclic digraph $D$.},
pdf = {ftp://ftp-sop.inria.fr/mascotte/Publications/GHP+12b.pdf},
url = {http://dx.doi.org/10.1016/j.dam.2011.07.013},
x-editorial-board={yes},
x-proceedings={yes},
x-international-audience={yes},
x-pays={},
sorte = "rev-int",
}
-
F. Havet,
C. Linhares Sales,
and L. Sampaio.
b-coloring of tight graphs.
Discrete Applied Mathematics,
160(18):2709-2715,
2012.
[WWW
]
@article{HLS12,
author = {Havet, F. and Linhares Sales, C. and Sampaio, L.},
title = {b-coloring of tight graphs},
journal = {Discrete Applied Mathematics},
year = {2012},
volume = {160},
number = {18},
pages = {2709-2715},
doi = {10.1016/j.dam.2011.10.017},
url = {http://www.sciencedirect.com/science/article/pii/S0166218X11003921},
x-editorial-board={yes},
x-proceedings={no},
x-international-audience={yes},
x-pays={BR},
sorte = "rev-int",
}
-
F. Havet,
B. Reed,
and J.-S. Sereni.
Griggs and Yeh's conjecture and $L(p,1)$-labellings.
SIAM Journal on Discrete Mathematics,
26(1):145-168,
2012.
[WWW
] [PDF
]
| Abstract: |
|
An $L(p,1)$-labeling of a graph is a function $f$ from the vertex set to the positive integers such that $|f(x)-f(y)|\geqslant p$ if dist$(x,y)=1$ and $|f(x)-f(y)|\geqslant 1$ if dist$(x,y)=2$, where dist$(x,y)$ is the distance between the two vertices $x$ and $y$ in the graph.
The span of an $L(p,1)$-labeling $f$ is the difference between the largest and the smallest labels used by $f$. In 1992, Griggs and Yeh conjectured that every graph with maximum degree $\Delta\geqslant 2$ has an $L(2,1)$-labeling with span at most $\Delta^2$.
We settle this conjecture for $\Delta$ 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\geqslant \Delta_p$ has an $L(p,1)$-labeling with span at most $\Delta^2$.
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)$-labeling with span at most $\Delta^2+C_p$. |
@ARTICLE{HRS12,
AUTHOR={Havet, F. and Reed, B. and Sereni, J.-S.},
TITLE={Griggs and Yeh's conjecture and $L(p,1)$-labellings},
JOURNAL = {SIAM Journal on Discrete Mathematics},
VOLUME = {26},
NUMBER = {1},
YEAR = {2012},
PAGES = {145-168},
abstract = {An $L(p,1)$-labeling of a graph is a function $f$ from the vertex set to the positive integers such that $|f(x)-f(y)|\geqslant p$ if dist$(x,y)=1$ and $|f(x)-f(y)|\geqslant 1$ if dist$(x,y)=2$, where dist$(x,y)$ is the distance between the two vertices $x$ and $y$ in the graph.
The span of an $L(p,1)$-labeling $f$ is the difference between the largest and the smallest labels used by $f$. In 1992, Griggs and Yeh conjectured that every graph with maximum degree $\Delta\geqslant 2$ has an $L(2,1)$-labeling with span at most $\Delta^2$.
We settle this conjecture for $\Delta$ 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\geqslant \Delta_p$ has an $L(p,1)$-labeling with span at most $\Delta^2$.
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)$-labeling with span at most $\Delta^2+C_p$.},
pdf = {ftp://ftp-sop.inria.fr/mascotte/Publications/HRS12.pdf},
url = {http://dx.doi.org/10.1137/090763998},
x-editorial-board={yes},
x-proceedings={yes},
x-international-audience={yes},
x-pays={CA},
sorte = "rev-int",
}
-
N. Nisse,
I. Rapaport,
and K. Suchan.
Distributed computing of efficient routing schemes in generalized chordal graphs.
Theoretical Computer Science,
444(27):17-27,
2012.
[WWW
] [PDF
]
| Abstract: |
|
Efficient algorithms for computing routing tables should take advantage of the particular properties arising in large scale networks.
There are in fact at least two properties that any routing scheme must consider: low (logarithmic) diameter and high clustering coefficient.
High clustering coefficient implies the existence of few large induced cycles.
Therefore, we propose a routing scheme that computes short routes in the class of k-chordal graphs, i.e., graphs with no chordless cycles of length more than k.
We study the tradeoff between the length of routes and the time complexity for computing them.
In the class of k-chordal graphs, our routing scheme achieves an additive stretch of at most k-1, i.e., for all pairs of nodes, the length of the route never exceeds their distance plus k-1.
In order to compute the routing tables of any n-node graph with diameter D we propose a distributed algorithm which uses O(log n)-bit messages and takes O(D) time.
We then propose a slightly modified version of the algorithm for computing routing tables in time O(min{Delta.D, n}), where Delta is the the maximum degree of the graph.
Using these tables, our routing scheme achieves a better additive stretch of 1 in chordal graphs (notice that chordal graphs are 3-chordal graphs).
The routing scheme uses addresses of size log n bits and local memory of size 2(d-1) log n bits in a node of degree d. |
@article{NRS12,
author = {Nisse, N. and Rapaport, I. and Suchan, K.},
title = {Distributed computing of efficient routing schemes in generalized chordal graphs},
journal = {Theoretical Computer Science},
year = {2012},
volume = {444},
number = {27},
pages = {17-27},
abstract = {Efficient algorithms for computing routing tables should take advantage of the particular properties arising in large scale networks.
There are in fact at least two properties that any routing scheme must consider: low (logarithmic) diameter and high clustering coefficient.
High clustering coefficient implies the existence of few large induced cycles.
Therefore, we propose a routing scheme that computes short routes in the class of k-chordal graphs, i.e., graphs with no chordless cycles of length more than k.
We study the tradeoff between the length of routes and the time complexity for computing them.
In the class of k-chordal graphs, our routing scheme achieves an additive stretch of at most k-1, i.e., for all pairs of nodes, the length of the route never exceeds their distance plus k-1.
In order to compute the routing tables of any n-node graph with diameter D we propose a distributed algorithm which uses O(log n)-bit messages and takes O(D) time.
We then propose a slightly modified version of the algorithm for computing routing tables in time O(min{Delta.D, n}), where Delta is the the maximum degree of the graph.
Using these tables, our routing scheme achieves a better additive stretch of 1 in chordal graphs (notice that chordal graphs are 3-chordal graphs).
The routing scheme uses addresses of size log n bits and local memory of size 2(d-1) log n bits in a node of degree d.},
url = {http://www.sciencedirect.com/science/article/pii/S0304397512000333},
pdf = {http://hal.inria.fr/docs/00/74/19/70/PDF/SiroccoTCSFinal.pdf},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
x-pays = {CL},
sorte = "rev-int",
}
-
M. Ajmone-Marsan,
S. Buzzi,
L. Chiaraviglio,
M. Meo,
C. Guerrero,
F. Idzikowski,
Y. Ye,
and J. Lopez Vizcaino.
TREND: Toward Real Energy-efficient Network Design.
In SustainIT 2012 - The Second IFIP Conference on Sustainable Internet and ICT for Sustainability,
Pisa, Italy,
pages 1-6,
October 2012.
[PDF
]
| Abstract: |
|
This paper briefly describes the objectives of the TREND (Toward Real Energy-efficient Network Design) Network of Excellence of the European Commission 7th Framework Programme, and outlines some of the main results obtained so far within the project, looking at wireless access networks, core networks, and content distribution issues. |
@inproceedings{ABC+12,
author = {Ajmone-Marsan, M. and Buzzi, S. and Chiaraviglio, L. and Meo, M. and Guerrero, C. and Idzikowski, F. and Ye, Y. and Lopez Vizcaino, J.},
title = {{TREND: Toward Real Energy-efficient Network Design}},
abstract = {{This paper briefly describes the objectives of the TREND (Toward Real Energy-efficient Network Design) Network of Excellence of the European Commission 7th Framework Programme, and outlines some of the main results obtained so far within the project, looking at wireless access networks, core networks, and content distribution issues.}},
booktitle = {{SustainIT 2012 - The Second IFIP Conference on Sustainable Internet and ICT for Sustainability}},
address = {Pisa, Italy},
year = {2012},
pages = {1-6},
month = Oct,
pdf={http://www.telematica.polito.it/oldsite/chiaraviglio/papers/SustainIT2012.pdf},
x-pays={IT,ES,DE},
OPTx-editorial-board={no},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
sorte = "inv-conf"
}
-
S. Baruah,
V. Bonifaci,
G. D'Angelo,
H. Li,
A. Marchetti-Spaccamela,
S. Van Der Ster,
and L. Stougie.
The preemptive uniprocessor scheduling of mixed-criticality implicit-deadline sporadic task systems.
In 24th Euromicro Conference on Real-Time Systems (ECRTS12),
Pisa, Italy,
pages 145-154,
July 2012.
IEEE.
[WWW
] [PDF
]
| Abstract: |
|
Systems in many safety-critical application domains are subject to certification requirements.
For any given system, however, it may be the case that only a subset of its functionality is safety-critical and hence subject to certification;
the rest of the functionality is non safety critical and does not need to be certified, or is certified to a lower level of assurance.
An algorithm called EDF-VD (for Earliest Deadline First with Virtual Deadlines) is described for the scheduling of such mixed-criticality task systems.
Analyses of EDF-VD significantly superior to previously-known ones are presented, based on metrics such as processor speedup factor (EDF-VD is proved to be optimal with respect to this metric) and utilization bounds. |
@inproceedings{BBD+12a,
author = {Baruah, S. and Bonifaci, V. and D'Angelo, G. and Li, H. and Marchetti-Spaccamela, A. and Van Der Ster, S. and Stougie, L.},
title = {{The preemptive uniprocessor scheduling of mixed-criticality implicit-deadline sporadic task systems}},
url = {http://hal.inria.fr/hal-00728995},
abstract = {{Systems in many safety-critical application domains are subject to certification requirements.
For any given system, however, it may be the case that only a subset of its functionality is safety-critical and hence subject to certification;
the rest of the functionality is non safety critical and does not need to be certified, or is certified to a lower level of assurance.
An algorithm called EDF-VD (for Earliest Deadline First with Virtual Deadlines) is described for the scheduling of such mixed-criticality task systems.
Analyses of EDF-VD significantly superior to previously-known ones are presented, based on metrics such as processor speedup factor (EDF-VD is proved to be optimal with respect to this metric) and utilization bounds.}},
booktitle = {{24th Euromicro Conference on Real-Time Systems (ECRTS12)}},
publisher = {IEEE},
pages = {145-154},
address = {Pisa, Italy},
doi = {10.1109/ECRTS.2012.42 },
year = {2012},
month = Jul,
pdf = {http://hal.inria.fr/hal-00728995/PDF/14-ECRTS12.pdf},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
x-pays = {IT,IN,CN,NL,US},
sorte = "conf-int",
}
-
F. Becker,
A. Kosowski,
N. Nisse,
I. Rapaport,
and K. Suchan.
Interconnection network with a shared whiteboard: Impact of (a)synchronicity on computing power.
In 24th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA),
pages 11-17,
2012.
ACM.
[WWW
] [PDF
]
| Abstract: |
|
In this work we study the computational power of graph-based models of distributed computing in which each node additionally has access to a global whiteboard.
A node can read the contents of the whiteboard and, when activated, can write one message of $O(\log n)$ bits on it.
A message is only based on the local knowledge of the node and the current content of the whiteboard.
When the protocol terminates, each node computes the output based on the final contents of the whiteboard in order to answer some question on the network's topology.
We propose a framework to formally define several scenarios modelling how nodes access the whiteboard, in a synchronous way or not.
This extends the work of Becker {\it et al.} [IPDPS 2011] where nodes were imposed to create their messages only based on their local knowledge (i.e., with the whiteboard empty).
We prove that the four models studied have increasing power of computation: any problem that can be solved in the weakest one can be solved in the the second, and so on.
Moreover, we exhibit problems that {\it separate} models, i.e., that can be solved in one model but not in a weaker one.
These problems are related to Maximal Independent Set and detection of cycles.
Finally we investigate problems related to connectivity as the construction of spanning- or BFS-tree in our different models. |
@inproceedings{BKN+12,
author = {Becker, F. and Kosowski, A. and Nisse, N. and Rapaport, I. and Suchan, K.},
title = {Interconnection network with a shared whiteboard: Impact of (a)synchronicity on computing power},
booktitle = {24th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)},
year = {2012},
pages = {11-17},
publisher = {ACM},
abstract = {In this work we study the computational power of graph-based models of distributed computing in which each node additionally has access to a global whiteboard.
A node can read the contents of the whiteboard and, when activated, can write one message of $O(\log n)$ bits on it.
A message is only based on the local knowledge of the node and the current content of the whiteboard.
When the protocol terminates, each node computes the output based on the final contents of the whiteboard in order to answer some question on the network's topology.
We propose a framework to formally define several scenarios modelling how nodes access the whiteboard, in a synchronous way or not.
This extends the work of Becker {\it et al.} [IPDPS 2011] where nodes were imposed to create their messages only based on their local knowledge (i.e., with the whiteboard empty).
We prove that the four models studied have increasing power of computation: any problem that can be solved in the weakest one can be solved in the the second, and so on.
Moreover, we exhibit problems that {\it separate} models, i.e., that can be solved in one model but not in a weaker one.
These problems are related to Maximal Independent Set and detection of cycles.
Finally we investigate problems related to connectivity as the construction of spanning- or BFS-tree in our different models.},
url = {http://hal.inria.fr/inria-00627910/fr/},
pdf = {http://hal.inria.fr/inria-00627910/PDF/RR-7746.pdf},
x-editorial-board={yes},
x-proceedings={yes},
x-international-audience={yes},
x-pays = {CL},
sorte = "conf-int",
}
-
J-C. Bermond,
D. Coudert,
G. D'Angelo,
and F. Z. Moataz.
Diverse Routing in networks with star SRLGs.
In ACM International Conference on emerging Networking EXperiments and Technologies (CoNEXT) Student Workshop,
Nice, France,
pages 1-2,
December 2012.
[WWW
] [PDF
]
| Abstract: |
|
The notion of \emph{Shared Risk Link Group}, SRLG has been
introduced to capture multiple correlated failures in a network. A
SRLG is a set of links that fail simultaneously if a given event (risk)
occurs. In such multiple failures scenario, the problem of Diverse
Routing consists in finding two SRLG-disjoint paths between a pair
of nodes. We consider such problem for localized failures, when all
the links of a SRLG verify the star property i.e. when they are
incident to the same node. We prove that in this case the problem
is in general NP-complete and determine some polynomial cases. |
@InProceedings{BCD+12,
author = {Bermond, J-C. and Coudert, D. and D'Angelo, G. and Moataz, F. Z.},
title = {Diverse Routing in networks with star SRLGs},
booktitle = {ACM International Conference on emerging Networking EXperiments and Technologies (CoNEXT) Student Workshop},
year = {2012},
month = {December},
pages = {1-2},
address = {Nice, France},
abstract={The notion of \emph{Shared Risk Link Group}, SRLG has been
introduced to capture multiple correlated failures in a network. A
SRLG is a set of links that fail simultaneously if a given event (risk)
occurs. In such multiple failures scenario, the problem of Diverse
Routing consists in finding two SRLG-disjoint paths between a pair
of nodes. We consider such problem for localized failures, when all
the links of a SRLG verify the star property i.e. when they are
incident to the same node. We prove that in this case the problem
is in general NP-complete and determine some polynomial cases.},
url = {http://hal.archives-ouvertes.fr/hal-00747757},
pdf = {http://hal.archives-ouvertes.fr/hal-00747757/PDF/conext26102012.pdf},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
x-pays = {IT,MA},
sorte = "rev-int",
}
-
L. Blin,
J. Burman,
and N. Nisse.
Nettoyage perpétuel de réseaux.
In 14es Rencontres Francophones sur les Aspects Algorithmiques de Télécommunications (AlgoTel),
pages 31-34,
2012.
[WWW
] [PDF
]
| Abstract: |
|
Dans le cadre du {\it nettoyage de graphes contaminés} ({\it graph searching}), des agents mobiles se d\'eplacent successivement le long des ar\^etes du graphe afin de les {\it nettoyer}.
Le but g\'en\'eral est le nettoyage en utilisant le moins d'agents possible.
Nous placons notre étude dans le mod\`ele de calcul distribu\'e {\it CORDA minimaliste}.
Ce mod\`ele est muni d'hypoth\`eses tr\`es faibles : les n\oe{}uds du r\'eseau et les agents sont anonymes, n'ont pas de m\'emoire du pass\'e ni sens commun de l'orientation et agissent par \emph{cycles} {\it Voir-Calculer-Agir} de mani\`ere \emph{asynchrone}.
Un int\'er\^et de ce mod\`ele vient du fait que si le nettoyage peut \^etre fait \`a partir de positions arbitraires des agents (par exemple, apr\`es pannes ou recontamination), l'absence de m\'emoire implique un nettoyage perp\'etuel et donc fournit une premi\`ere approche de nettoyage de graphe {\it tol\'erant aux pannes}.
Les contraintes dues au mod\`ele {\it CORDA minimaliste} nous am\`enent \`a d\'efinir une nouvelle variante de nettoyage de graphes - le {\it nettoyage sans collision}, autrement dit, plusieurs agents ne peuvent occuper simultan\'ement un m\^eme sommet.
Nous montrons que, dans un contexte \emph{centralis\'e}, cette variante ne satisfait pas certaines propri\'et\'es classiques de nettoyage comme par exemple la monotonie.
Nous montrons qu'interdire les ``collisions'' peut augmenter le nombre d'agents n\'ecessaires d'un facteur au plus $\Delta$ le degr\'e maximum du graphe et nous illustrons cette borne.
De plus, nous caract\'erisons compl\`etement le nettoyage sans collision dans les arbres.
Dans le contexte \emph{distribu\'e}, la question qui se pose est la suivante.
Existe-t-il un algorithme qui, \'etant donn\'e un ensemble d'agents mobiles arbitrairement r\'epartis sur des sommets distincts d'un r\'eseau, permet aux agents de nettoyer perp\'etuellement le graphe?
Dans le cas des chemins, nous montrons que la r\'eponse est n\'egative si le nombre d'agents est pair dans un chemin d'ordre impair, ou si il y a au plus deux agents dans un chemin d'ordre au moins $3$.
Nous proposons un algorithme qui nettoie les chemins dans tous les cas restants, ainsi qu'un algorithme pour nettoyer les arbres lorsqu'un nombre suffisant d'agents est disponible initialement. |
@inproceedings{BBN12b,
author = {Blin, L. and Burman, J. and Nisse, N.},
title = {Nettoyage perp\'etuel de r\'eseaux},
booktitle = {14es Rencontres Francophones sur les Aspects Algorithmiques de T{\'e}l{\'e}communications (AlgoTel)},
year = {2012},
pages = {31-34},
abstract = {Dans le cadre du {\it nettoyage de graphes contaminés} ({\it graph searching}), des agents mobiles se d\'eplacent successivement le long des ar\^etes du graphe afin de les {\it nettoyer}.
Le but g\'en\'eral est le nettoyage en utilisant le moins d'agents possible.
Nous placons notre étude dans le mod\`ele de calcul distribu\'e {\it CORDA minimaliste}.
Ce mod\`ele est muni d'hypoth\`eses tr\`es faibles : les n\oe{}uds du r\'eseau et les agents sont anonymes, n'ont pas de m\'emoire du pass\'e ni sens commun de l'orientation et agissent par \emph{cycles} {\it Voir-Calculer-Agir} de mani\`ere \emph{asynchrone}.
Un int\'er\^et de ce mod\`ele vient du fait que si le nettoyage peut \^etre fait \`a partir de positions arbitraires des agents (par exemple, apr\`es pannes ou recontamination), l'absence de m\'emoire implique un nettoyage perp\'etuel et donc fournit une premi\`ere approche de nettoyage de graphe {\it tol\'erant aux pannes}.
Les contraintes dues au mod\`ele {\it CORDA minimaliste} nous am\`enent \`a d\'efinir une nouvelle variante de nettoyage de graphes - le {\it nettoyage sans collision}, autrement dit, plusieurs agents ne peuvent occuper simultan\'ement un m\^eme sommet.
Nous montrons que, dans un contexte \emph{centralis\'e}, cette variante ne satisfait pas certaines propri\'et\'es classiques de nettoyage comme par exemple la monotonie.
Nous montrons qu'interdire les ``collisions'' peut augmenter le nombre d'agents n\'ecessaires d'un facteur au plus $\Delta$ le degr\'e maximum du graphe et nous illustrons cette borne.
De plus, nous caract\'erisons compl\`etement le nettoyage sans collision dans les arbres.
Dans le contexte \emph{distribu\'e}, la question qui se pose est la suivante.
Existe-t-il un algorithme qui, \'etant donn\'e un ensemble d'agents mobiles arbitrairement r\'epartis sur des sommets distincts d'un r\'eseau, permet aux agents de nettoyer perp\'etuellement le graphe?
Dans le cas des chemins, nous montrons que la r\'eponse est n\'egative si le nombre d'agents est pair dans un chemin d'ordre impair, ou si il y a au plus deux agents dans un chemin d'ordre au moins $3$.
Nous proposons un algorithme qui nettoie les chemins dans tous les cas restants, ainsi qu'un algorithme pour nettoyer les arbres lorsqu'un nombre suffisant d'agents est disponible initialement.},
url = {http://hal.archives-ouvertes.fr/hal-00675233},
pdf ={http://hal.archives-ouvertes.fr/docs/00/67/52/33/PDF/RR-7897.pdf},
x-editorial-board={yes},
x-proceedings={yes},
x-international-audience={no},
x-pays= {},
sorte = "conf-nat",
}
-
L. Blin,
J. Burman,
and N. Nisse.
Brief Announcement: Distributed Exclusive and Perpetual Tree Searching.
In 26th International Symposium on Distributed Computing (DISC),
volume 7611,
pages 403-404,
2012.
Springer, LNCS.
[WWW
] [PDF
]
| Abstract: |
|
We tackle a practical version of the well known {\it graph searching} problem, where a team of robots aims at capturing an intruder in a graph.
The robots and the intruder move along the edges of the graph.
The intruder is invisible, arbitrary fast, and omniscient.
It is caught whenever it stands on a node occupied by a robot, and cannot escape to a neighboring node.
We study graph searching in the CORDA model of mobile computing: robots are asynchronous, and they perform cycles of {\it Look-Compute-Move} actions.
Moreover, motivated by physical constraints, we consider the \emph{exclusive} property, stating that no two or more robots can occupy the same node at the same time.
In addition, we assume that the network and the robots are anonymous.
Finally, robots are \emph{oblivious}, i.e., each robot performs its move actions based only on its current ''vision'' of the positions of the other robots.
Our objective is to characterize, for a graph $G$, the set of integers $k$ such that graph searching can be achieved by a team of $k$ robots starting from \emph{any} $k$ distinct nodes in $G$.
Our main result consists in a full characterization of this set, for any asymmetric tree.
Towards providing a characterization for all trees, including trees with non-trivial automorphisms, we have also provides a set of positive and negative results, including a full characterization for any line.
All our positive results are based on the design of algorithms enabling \emph{perpetual} graph searching to be achieved with the desired number of robots. |
@inproceedings{BBN12c,
author = {Blin, L. and Burman, J. and Nisse, N.},
title = {Brief Announcement: Distributed Exclusive and Perpetual Tree Searching},
booktitle = {26th International Symposium on Distributed Computing (DISC)},
publisher = {Springer, LNCS},
year = {2012},
volume = {7611},
pages = {403-404},
abstract = {We tackle a practical version of the well known {\it graph searching} problem, where a team of robots aims at capturing an intruder in a graph.
The robots and the intruder move along the edges of the graph.
The intruder is invisible, arbitrary fast, and omniscient.
It is caught whenever it stands on a node occupied by a robot, and cannot escape to a neighboring node.
We study graph searching in the CORDA model of mobile computing: robots are asynchronous, and they perform cycles of {\it Look-Compute-Move} actions.
Moreover, motivated by physical constraints, we consider the \emph{exclusive} property, stating that no two or more robots can occupy the same node at the same time.
In addition, we assume that the network and the robots are anonymous.
Finally, robots are \emph{oblivious}, i.e., each robot performs its move actions based only on its current ''vision'' of the positions of the other robots.
Our objective is to characterize, for a graph $G$, the set of integers $k$ such that graph searching can be achieved by a team of $k$ robots starting from \emph{any} $k$ distinct nodes in $G$.
Our main result consists in a full characterization of this set, for any asymmetric tree.
Towards providing a characterization for all trees, including trees with non-trivial automorphisms, we have also provides a set of positive and negative results, including a full characterization for any line.
All our positive results are based on the design of algorithms enabling \emph{perpetual} graph searching to be achieved with the desired number of robots.},
url = {http://hal.inria.fr/hal-00741982},
pdf ={http://hal.inria.fr/docs/00/74/19/82/PDF/disc2012-final88-2.pdf},
x-editorial-board={yes},
x-proceedings={yes},
x-international-audience={yes},
x-pays = {},
sorte = "conf-int",
}
-
L. Chiaraviglio and A. Cianfrani.
On the Effectiveness of Sleep Modes in Backbone Networks with Limited Configurations.
In 20th International Conference on Software, Telecommunications and Computer Networks (SoftCOM 2012),
Split, Croatia,
pages 1-6,
September 2012.
[PDF
]
| Abstract: |
|
We study the problem of putting in sleep mode devices of a backbone network, while limiting the number of times each device changes its power state (full power mode or sleep mode).
Our aim is to limit the number of network configurations, i.e., the change of the current set of network devices at full power.
We develop a model, based on random graph theory, to compute the energy saving given a traffic variation, QoS constraints, and the number of allowed network configurations.
Results show that the energy savings with few configurations (two or three per day) are close to the maximum one, in which a new configuration is applied for each traffic matrix.
Thus, we can conclude that a practical implementation of sleep mode strategies for network operators is to define, on the basis of typical traffic trend, few configurations to be activated in specific time instants. |
@inproceedings{ChCi12,
author = {Chiaraviglio, L. and Cianfrani, A.},
title = {{On the Effectiveness of Sleep Modes in Backbone Networks with Limited Configurations}},
abstract = {{We study the problem of putting in sleep mode devices of a backbone network, while limiting the number of times each device changes its power state (full power mode or sleep mode).
Our aim is to limit the number of network configurations, i.e., the change of the current set of network devices at full power.
We develop a model, based on random graph theory, to compute the energy saving given a traffic variation, QoS constraints, and the number of allowed network configurations.
Results show that the energy savings with few configurations (two or three per day) are close to the maximum one, in which a new configuration is applied for each traffic matrix.
Thus, we can conclude that a practical implementation of sleep mode strategies for network operators is to define, on the basis of typical traffic trend, few configurations to be activated in specific time instants.}},
booktitle = {{20th International Conference on Software, Telecommunications and Computer Networks (SoftCOM 2012)}},
address = {Split, Croatia},
year = {2012},
pages = {1-6},
month = Sep,
pdf={http://www.telematica.polito.it/oldsite/chiaraviglio/papers/SleepModeEffectiveness.pdf},
x-pays={IT},
OPTx-editorial-board={no},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
sorte = "conf-int"
}
-
D. Coudert,
L. Hogie,
A. Lancin,
D. Papadimitriou,
S. Pérennes,
and I. Tahiri.
Feasibility study on distributed simulations of BGP.
In PADS - 26th ACM/IEEE/SCS Workshop on Principles of Advanced and Distributed Simulation - 2012,
Zhangjiajie, Chine,
April 2012.
IEEE.
[WWW
] [PDF
]
| Abstract: |
|
The Autonomous System (AS) topology of the Internet (up to 61k ASs) is growing at a rate of about 10\(nil)er year.
The Border Gateway Protocol (BGP) starts to show its limits in terms of the number of routing table entries it can dynamically process and control.
Due to the increasing routing information processing and storage, the same trend is observed for routing model simulators such as DRMSim specialized in large-scale simulations of routing models.
Therefore, DRMSim needs enhancements to support the current size of the Internet topology and its evolution (up to 100k ASs).
To this end, this paper proposes a feasibility study of the extension of DRMSim so as to support the Distributed Parallel Discrete Event paradigm.
We first detail the possible distribution models and their associated communication overhead.
Then, we analyze this overhead by executing BGP on a partitioned topology according to different scenarios.
Finally, we conclude on the feasibility of such a simulator by computing the expected additional time required by a distributed simulation of BGP compared to its sequential simulation. |
@inproceedings{CHL+12,
author = {Coudert, D. and Hogie, L. and Lancin, A. and Papadimitriou, D. and P{\'e}rennes, S. and Tahiri, I.},
title = {{Feasibility study on distributed simulations of BGP}},
booktitle = {{PADS - 26th ACM/IEEE/SCS Workshop on Principles of Advanced and Distributed Simulation - 2012}},
year = {2012},
month = Apr,
address = {Zhangjiajie, Chine},
publisher = {IEEE},
language = {Anglais},
affiliation = {MASCOTTE - INRIA Sophia Antipolis / Laboratoire I3S , Alcatel-Lucent Bell - Belgique},
collaboration = {Alcatel-Lucent-Bell },
abstract = {{The Autonomous System (AS) topology of the Internet (up to 61k ASs) is growing at a rate of about 10\(nil)er year.
The Border Gateway Protocol (BGP) starts to show its limits in terms of the number of routing table entries it can dynamically process and control.
Due to the increasing routing information processing and storage, the same trend is observed for routing model simulators such as DRMSim specialized in large-scale simulations of routing models.
Therefore, DRMSim needs enhancements to support the current size of the Internet topology and its evolution (up to 100k ASs).
To this end, this paper proposes a feasibility study of the extension of DRMSim so as to support the Distributed Parallel Discrete Event paradigm.
We first detail the possible distribution models and their associated communication overhead.
Then, we analyze this overhead by executing BGP on a partitioned topology according to different scenarios.
Finally, we conclude on the feasibility of such a simulator by computing the expected additional time required by a distributed simulation of BGP compared to its sequential simulation.}},
url = {http://hal.inria.fr/hal-00706415},
pdf = {ftp://ftp-sop.inria.fr/mascotte/Publications/CHL+12.pdf},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
x-pays = {BE},
sorte = "conf-int",
}
-
G. D'Angelo,
M. D'Emidio,
D. Frigioni,
and V. Maurizio.
Engineering a new loop-free shortest paths routing algorithm.
In 11th International Symposium on Experimental Algorithms (SEA2012),
volume 7276 of Lecture Notes in Computer Science,
Bordeaux, France,
pages 123-134,
June 2012.
Springer.
[WWW
] [PDF
]
| Abstract: |
|
We present LFR (Loop Free Routing), a new loop-free distance vector routing algorithm, which is able to update the shortest paths of a distributed network with n nodes in fully dynamic scenarios.
If Phi is the total number of nodes affected by a set of updates to the network, and phi is the maximum number of destinations for which a node is affected, then LFR requires O(Phi*Delta) messages and O(n + phi*Delta) space per node, where Delta is the maximum degree of the nodes of the network.
We experimentally compare LFR with DUAL, one of the most popular loop-free distance vector algorithms, which is part of CISCO's EIGRP protocol and requires O(Phi*Delta) messages and $\Theta$(n*Delta) space per node.
The experiments are based on both real-world and artificial instances and show that LFR is always the best choice in terms of memory require- ments, while in terms of messages LFR outperforms DUAL on real-world instances, whereas DUAL is the best choice on artificial instances. |
@inproceedings{DDF+12,
author = {D'Angelo, G. and D'Emidio, M. and Frigioni, D. and Maurizio, V.},
title = {{Engineering a new loop-free shortest paths routing algorithm}},
url = {http://hal.inria.fr/hal-00729005},
abstract = {{We present LFR (Loop Free Routing), a new loop-free distance vector routing algorithm, which is able to update the shortest paths of a distributed network with n nodes in fully dynamic scenarios.
If Phi is the total number of nodes affected by a set of updates to the network, and phi is the maximum number of destinations for which a node is affected, then LFR requires O(Phi*Delta) messages and O(n + phi*Delta) space per node, where Delta is the maximum degree of the nodes of the network.
We experimentally compare LFR with DUAL, one of the most popular loop-free distance vector algorithms, which is part of CISCO's EIGRP protocol and requires O(Phi*Delta) messages and $\Theta$(n*Delta) space per node.
The experiments are based on both real-world and artificial instances and show that LFR is always the best choice in terms of memory require- ments, while in terms of messages LFR outperforms DUAL on real-world instances, whereas DUAL is the best choice on artificial instances.}},
booktitle = {{11th International Symposium on Experimental Algorithms (SEA2012)}},
publisher = {Springer},
pages = {123-134},
address = {Bordeaux, France},
volume = {7276},
series = {Lecture Notes in Computer Science },
doi = {10.1007/978-3-642-30850-5\_12 },
year = {2012},
month = Jun,
pdf = {http://hal.inria.fr/hal-00729005/PDF/main.pdf},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
x-pays = {IT},
sorte = "conf-int",
}
-
G. D'Angelo,
M. D'Emidio,
D. Frigioni,
and D. Romano.
Enhancing the computation of distributed shortest paths on real dynamic networks.
In 1st Mediterranean Conference on Algorithms,
volume 7659 of Lecture Notes in Computer Science,
Ein-Gedi, Israel,
pages 148-158,
December 2012.
Springer.
[WWW
] [PDF
]
| Abstract: |
|
The problem of finding and updating shortest paths in distributed networks is considered crucial in today's practical applications.
In the recent past, there has been a renewed interest in devising new efficient distance-vector algorithms as an attractive alternative to link-state solutions for large-scale Ethernet networks, in which scalability and reliability are key issues or the nodes can have limited storage capabilities.
In this paper we present Distributed Computation Pruning (DCP), a new technique, which can be combined with every distance-vector routing algorithm based on shortest paths, allowing to reduce the total number of messages sent by that algorithm and its space occupancy per node.
To check its effectiveness, we combined DCP with DUAL (Diffuse Update ALgorithm), one of the most popular distance-vector algorithm in the literature, which is part of CISCO's widely used EIGRP protocol, and with the recently introduced LFR (Loop Free Routing) which has been shown to have good performances on real networks.
We give experimental evidence that these combinations lead to a significant gain both in terms of number of messages sent and memory requirements per node. |
@inproceedings{DDF+12b,
author = {D'Angelo, G. and D'Emidio, M. and Frigioni, D. and Romano, D.},
title = {{Enhancing the computation of distributed shortest paths on real dynamic networks}},
booktitle = {{1st Mediterranean Conference on Algorithms}},
series = {Lecture Notes in Computer Science },
year = {2012},
month = Dec,
address = {Ein-Gedi, Israel},
volume = {7659},
pages = {148-158},
publisher = {Springer},
abstract = {{The problem of finding and updating shortest paths in distributed networks is considered crucial in today's practical applications.
In the recent past, there has been a renewed interest in devising new efficient distance-vector algorithms as an attractive alternative to link-state solutions for large-scale Ethernet networks, in which scalability and reliability are key issues or the nodes can have limited storage capabilities.
In this paper we present Distributed Computation Pruning (DCP), a new technique, which can be combined with every distance-vector routing algorithm based on shortest paths, allowing to reduce the total number of messages sent by that algorithm and its space occupancy per node.
To check its effectiveness, we combined DCP with DUAL (Diffuse Update ALgorithm), one of the most popular distance-vector algorithm in the literature, which is part of CISCO's widely used EIGRP protocol, and with the recently introduced LFR (Loop Free Routing) which has been shown to have good performances on real networks.
We give experimental evidence that these combinations lead to a significant gain both in terms of number of messages sent and memory requirements per node.}},
url = {http://hal.inria.fr/hal-00755395},
pdf = {http://hal.inria.fr/hal-00755395/PDF/main.pdf},
x-pays = {IT},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
sorte = "conf-int",
}
-
G. D'Angelo,
M. D'Emidio,
D. Frigioni,
and C. Vitale.
Fully Dynamic Maintenance of Arc-Flags in Road Networks.
In 11th International Symposium on Experimental Algorithms (SEA2012),
volume 7276 of Lecture Notes in Computer Science,
Bordeaux, France,
pages 135-147,
June 2012.
Springer.
[WWW
] [PDF
]
| Abstract: |
|
The problem of finding best routes in road networks can be solved by applying Dijkstra's shortest paths algorithm.
Unfortunately, road networks deriving from real-world applications are huge yielding unsustainable times to compute shortest paths.
For this reason, great research efforts have been done to accelerate Dijkstra's algorithm on road networks.
These efforts have led to the development of a number of speed-up techniques, as for example Arc-Flags, whose aim is to compute additional data in a preprocessing phase in order to accelerate the shortest paths queries in an on-line phase.
The main drawback of most of these techniques is that they do not work well in dynamic scenarios.
In this paper we propose a new algorithm to update the Arc-Flags of a graph subject to edge weight decrease operations.
To check the practical performances of the new algorithm we experimentally analyze it, along with a previously known algorithm for edge weight increase operations, on real-world road networks subject to fully dynamic sequences of operations.
Our experiments show a significant speed-up in the updating phase of the Arc-Flags, at the cost of a small space and time overhead in the preprocessing phase. |
@inproceedings{DDF+12a,
author = {D'Angelo, G. and D'Emidio, M. and Frigioni, D. and Vitale, C.},
title = {{Fully Dynamic Maintenance of Arc-Flags in Road Networks}},
booktitle = {{11th International Symposium on Experimental Algorithms (SEA2012)}},
year = {2012},
month = Jun,
volume = {7276},
pages = {135-147},
address = {Bordeaux, France},
publisher = {Springer},
series = {Lecture Notes in Computer Science },
abstract = {{The problem of finding best routes in road networks can be solved by applying Dijkstra's shortest paths algorithm.
Unfortunately, road networks deriving from real-world applications are huge yielding unsustainable times to compute shortest paths.
For this reason, great research efforts have been done to accelerate Dijkstra's algorithm on road networks.
These efforts have led to the development of a number of speed-up techniques, as for example Arc-Flags, whose aim is to compute additional data in a preprocessing phase in order to accelerate the shortest paths queries in an on-line phase.
The main drawback of most of these techniques is that they do not work well in dynamic scenarios.
In this paper we propose a new algorithm to update the Arc-Flags of a graph subject to edge weight decrease operations.
To check the practical performances of the new algorithm we experimentally analyze it, along with a previously known algorithm for edge weight increase operations, on real-world road networks subject to fully dynamic sequences of operations.
Our experiments show a significant speed-up in the updating phase of the Arc-Flags, at the cost of a small space and time overhead in the preprocessing phase.}},
doi = {10.1007/978-3-642-30850-5\_13 },
url = {http://hal.inria.fr/hal-00729008},
pdf = {http://hal.inria.fr/hal-00729008/PDF/main.pdf},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
x-pays = {IT},
sorte = "conf-int",
}
-
G. D'Angelo,
G. Di Stefano,
R. Klasing,
and A. Navarra.
Gathering of Robots on Anonymous Grids without multiplicity detection.
In 19th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2012),
volume 7355 of Lecture Notes in Computer Science,
Reykjavìk, Iceland,
pages 327-338,
June 2012.
Springer.
[WWW
] [PDF
]
| Abstract: |
|
The paper studies the gathering problem on grid networks.
A team of robots placed at different nodes of a grid, have to meet at some node and remain there.
Robots operate in Look-Compute-Move cycles; in one cycle, a robot perceives the current configuration in terms of occupied nodes (Look), decides whether to move towards one of its neighbors (Compute), and in the positive case makes the computed move instantaneously (Move).
Cycles are performed asynchronously for each robot.
The problem has been deeply studied for the case of ring networks.
However, the known techniques used on rings cannot be directly extended to grids.
Moreover, on rings, another assumption concerning the so-called multiplicity detection capability was required in order to accomplish the gathering task.
That is, a robot is able to detect during its Look operation whether a node is empty, or occupied by one robot, or occupied by an undefined number of robots greater than one.
In this paper, we provide a full characterization about gatherable configurations for grids.
In particular, we show that in this case, the multiplicity detection is not required.
Very interestingly, sometimes the problem appears trivial, as it is for the case of grids with both odd sides, while sometimes the involved techniques require new insights with respect to the well-studied ring case.
Moreover, our results reveal the importance of a structure like the grid that allows to overcome the multiplicity detection with respect to the ring case. |
@inproceedings{DDK12,
author = {D'Angelo, G. and Di Stefano, G. and Klasing, R. and Navarra, A.},
title = {{Gathering of Robots on Anonymous Grids without multiplicity detection}},
booktitle = {{19th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2012)}},
year = {2012},
month = Jun,
volume = {7355},
pages = {327-338},
address = {Reykjav{\'\i}k, Iceland},
publisher = {Springer},
series = {Lecture Notes in Computer Science},
abstract = {{The paper studies the gathering problem on grid networks.
A team of robots placed at different nodes of a grid, have to meet at some node and remain there.
Robots operate in Look-Compute-Move cycles; in one cycle, a robot perceives the current configuration in terms of occupied nodes (Look), decides whether to move towards one of its neighbors (Compute), and in the positive case makes the computed move instantaneously (Move).
Cycles are performed asynchronously for each robot.
The problem has been deeply studied for the case of ring networks.
However, the known techniques used on rings cannot be directly extended to grids.
Moreover, on rings, another assumption concerning the so-called multiplicity detection capability was required in order to accomplish the gathering task.
That is, a robot is able to detect during its Look operation whether a node is empty, or occupied by one robot, or occupied by an undefined number of robots greater than one.
In this paper, we provide a full characterization about gatherable configurations for grids.
In particular, we show that in this case, the multiplicity detection is not required.
Very interestingly, sometimes the problem appears trivial, as it is for the case of grids with both odd sides, while sometimes the involved techniques require new insights with respect to the well-studied ring case.
Moreover, our results reveal the importance of a structure like the grid that allows to overcome the multiplicity detection with respect to the ring case.}},
doi = {10.1007/978-3-642-31104-8\_28 },
url = {http://hal.inria.fr/hal-00728988},
pdf = {http://hal.inria.fr/hal-00728988/PDF/main.pdf},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
x-pays = {IT,DE},
sorte = "conf-int",
}
-
G. D'Angelo,
G. Di Stefano,
and A. Navarra.
How to gather asynchronous oblivious robots on anonymous rings.
In 26th International Symposium on Distributed Computing (DISC 2012),
volume 7611 of Lecture Notes in Computer Science,
Salvador, Brazil,
pages 330-344,
October 2012.
Springer.
[WWW
] [PDF
]
| Abstract: |
|
A set of robots arbitrarily placed on different nodes of an anonymous ring have to meet at one common node and remain in there.
This problem is known in the literature as the gathering.
Anonymous and oblivious robots operate in Look-Compute-Move cycles; in one cycle, a robot takes a snapshot of the current configuration (Look), decides whether to stay idle or to move to one of its neighbors (Compute), and in the latter case makes the computed move instantaneously (Move).
Cycles are asynchronous among robots.
Moreover, each robot is empowered by the so called multiplicity detection capability, that is, it is able to detect during its Look operation whether a node is empty, or occupied by one robot, or occupied by an undefined number of robots greater than one.
The described problem has been extensively studied during the last years.
However, the known solutions work only for specific initial configurations and leave some open cases.
In this paper, we provide an algorithm which solves the general problem, and is able to detect all the ungatherable configurations.
It is worth noting that our new algorithm makes use of a unified and general strategy for any initial configuration, even those left open by previous works. |
@inproceedings{DDN12c,
author = {D'Angelo, G. and Di Stefano, G. and Navarra, A.},
title = {{How to gather asynchronous oblivious robots on anonymous rings}},
url = {http://hal.inria.fr/hal-00728979},
abstract = {{A set of robots arbitrarily placed on different nodes of an anonymous ring have to meet at one common node and remain in there.
This problem is known in the literature as the gathering.
Anonymous and oblivious robots operate in Look-Compute-Move cycles; in one cycle, a robot takes a snapshot of the current configuration (Look), decides whether to stay idle or to move to one of its neighbors (Compute), and in the latter case makes the computed move instantaneously (Move).
Cycles are asynchronous among robots.
Moreover, each robot is empowered by the so called multiplicity detection capability, that is, it is able to detect during its Look operation whether a node is empty, or occupied by one robot, or occupied by an undefined number of robots greater than one.
The described problem has been extensively studied during the last years.
However, the known solutions work only for specific initial configurations and leave some open cases.
In this paper, we provide an algorithm which solves the general problem, and is able to detect all the ungatherable configurations.
It is worth noting that our new algorithm makes use of a unified and general strategy for any initial configuration, even those left open by previous works.}},
booktitle = {{26th International Symposium on Distributed Computing (DISC 2012)}},
publisher = {Springer},
pages = {330-344},
address = {Salvador, Brazil},
volume = {7611},
series = {Lecture Notes in Computer Science },
year = {2012},
month = Oct,
pdf = {http://hal.inria.fr/hal-00728979/PDF/main.pdf},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
x-pays = {IT},
sorte = "conf-int",
}
-
O. Dalle and E. Mancini.
Integrated tools for the simulation analysis of peer-to-peer backup systems.
In Proceedings of the 5th International ICST Conference on Simulation Tools and Techniques,
SIMUTOOLS '12,
pages 178-183,
March 2012.
ICST (Institute for Computer Sciences, Social-Informatics and Telecommunications Engineering).
[WWW
] [PDF
]
| Abstract: |
|
In order to evaluate the performance and estimate the resource usage of peer-to-peer backup systems, it is important to analyze the time they spend in storing, retrieving and keeping the redundancy of the stored files.
The analysis of such systems is difficult due to the random behavior of the peers and the variations of network conditions.
Simulations provide a unique means for reproducing such varying conditions in a controlled way.
In this paper we describe a general meta-model for peer-to-peer backup systems and a tool-chain, based on SimGrid, to help in their analysis.
We validated the meta-model and tool-chain through the analysis of a common scenario, and verified that they can be used, for example, for retrieving the relations between the storage size, the saved data fragment sizes and the induced network workload. |
@inproceedings{DaMa12,
author = {Dalle, O. and Mancini, E.},
title = {Integrated tools for the simulation analysis of peer-to-peer backup systems},
booktitle = {Proceedings of the 5th International ICST Conference on Simulation Tools and Techniques},
series = {SIMUTOOLS '12},
publisher = {ICST (Institute for Computer Sciences, Social-Informatics and Telecommunications Engineering)},
year = {2012},
month = Mar,
pages = {178-183},
abstract = {{In order to evaluate the performance and estimate the resource usage of peer-to-peer backup systems, it is important to analyze the time they spend in storing, retrieving and keeping the redundancy of the stored files.
The analysis of such systems is difficult due to the random behavior of the peers and the variations of network conditions.
Simulations provide a unique means for reproducing such varying conditions in a controlled way.
In this paper we describe a general meta-model for peer-to-peer backup systems and a tool-chain, based on SimGrid, to help in their analysis.
We validated the meta-model and tool-chain through the analysis of a common scenario, and verified that they can be used, for example, for retrieving the relations between the storage size, the saved data fragment sizes and the induced network workload.}},
url = {http://dl.acm.org/citation.cfm?id=2263019.2263042},
pdf = {http://hal.inria.fr/hal-00669241/PDF/paper.pdf},
OPTx-editorial-board={no},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
sorte = "conf-int",
}
-
F. V. Fomin,
F. Giroire,
A. Jean-Marie,
D. Mazauric,
and N. Nisse.
To Satisfy Impatient Web surfers is Hard.
In 6th International Conference on FUN with Algorithms (FUN),
volume 7288,
pages 166-176,
2012.
Springer, LNCS.
[WWW
] [PDF
]
| Abstract: |
|
Prefetching is a basic mechanism to avoid to waste time when accessing data.
However, a tradeoff must be established between the amount of network's resources wasted by the prefetching and the gain of time.
For instance, in the Web, browsers may download documents in advance while an Internaut is surfing on the Web.
Since the web surfer follows the hyperlinks in an unpredictable way, the choice of the web pages to be prefetched must be computed online.
The question is then to determine the minimum amount of resources used by prefetching and that ensures that all documents accessed by the web surfer have previously been loaded in the cache.
We model this problem as a game similar to Cops and Robber Games in graphs.
A fugitive starts on a marked vertex of a (di)graph G. Turn by turn, an observer marks at most k >= 1 vertices and then the fugitive can move along one edge/arcs of G.
The observer wins if he prevents the fugitive to reach an unmarked vertex.
The fugitive wins otherwise, i.e., if she enters an unmarked vertex.
The surveillance number of a graph is the least k >=1 allowing the observer to win whatever the fugitive does.
We also consider the connected variant of this game, i.e., when a vertex can be marked only if it is adjacent to an already marked vertex.
All our results hold for both variants, connected or not.
We show that deciding whether the surveillance number of a chordal graph equals 2 is NP-hard.
Deciding if the surveillance number of a DAG equals 4 is PSPACE-complete.
Moreover, computing the surveillance number is NP-hard in split graphs.
On the other hand, we provide polynomial time algorithms to compute surveillance number of trees and interval graphs.
Moreover, in the case of trees, we establish a combinatorial characterization, related to isoperimetry, of the surveillance number. |
@inproceedings{FGJ+12a,
author = {Fomin, F. V. and Giroire, F. and Jean-Marie, A. and Mazauric, D. and Nisse, N.},
title = {To Satisfy Impatient Web surfers is Hard},
booktitle = {6th International Conference on FUN with Algorithms (FUN)},
year = {2012},
publisher = {Springer, LNCS},
volume = {7288},
pages = {166-176},
abstract = {Prefetching is a basic mechanism to avoid to waste time when accessing data.
However, a tradeoff must be established between the amount of network's resources wasted by the prefetching and the gain of time.
For instance, in the Web, browsers may download documents in advance while an Internaut is surfing on the Web.
Since the web surfer follows the hyperlinks in an unpredictable way, the choice of the web pages to be prefetched must be computed online.
The question is then to determine the minimum amount of resources used by prefetching and that ensures that all documents accessed by the web surfer have previously been loaded in the cache.
We model this problem as a game similar to Cops and Robber Games in graphs.
A fugitive starts on a marked vertex of a (di)graph G. Turn by turn, an observer marks at most k >= 1 vertices and then the fugitive can move along one edge/arcs of G.
The observer wins if he prevents the fugitive to reach an unmarked vertex.
The fugitive wins otherwise, i.e., if she enters an unmarked vertex.
The surveillance number of a graph is the least k >=1 allowing the observer to win whatever the fugitive does.
We also consider the connected variant of this game, i.e., when a vertex can be marked only if it is adjacent to an already marked vertex.
All our results hold for both variants, connected or not.
We show that deciding whether the surveillance number of a chordal graph equals 2 is NP-hard.
Deciding if the surveillance number of a DAG equals 4 is PSPACE-complete.
Moreover, computing the surveillance number is NP-hard in split graphs.
On the other hand, we provide polynomial time algorithms to compute surveillance number of trees and interval graphs.
Moreover, in the case of trees, we establish a combinatorial characterization, related to isoperimetry, of the surveillance number.},
url = {http://hal.inria.fr/inria-00625703/en/},
pdf = {http://hal.inria.fr/inria-00625703/PDF/RR-7740.pdf},
x-editorial-board={yes},
x-proceedings={yes},
x-international-audience={yes},
x-pays = {NO},
sorte = "conf-int",
}
-
F. V. Fomin,
F. Giroire,
A. Jean-Marie,
D. Mazauric,
and N. Nisse.
Satisfaire un internaute impatient est difficile.
In 14es Rencontres Francophones sur les Aspects Algorithmiques de Télécommunications (AlgoTel),
pages 79-82,
2012.
Note: Best paper.
[WWW
] [PDF
]
| Abstract: |
|
Consid\'erons un internaute qui va d'une page Web \`a une autre en suivant les liens qu'il rencontre.
Pour \'eviter que l'internaute ne (s'im)patiente, il est important d'essayer de t\'el\'echarger les documents avant que l'internaute ne les atteigne.
Cependant, le co\^ut d'un tel pr\'e-t\'el\'echargement ne doit pas exc\'eder le gain en temps qu'il g\'en\`ere.
Ainsi, il faut minimiser la bande passante utilis\'ee pour le pr\'e-t\'el\'echargement tout en s'assurant que l'internaute impatient n'attende jamais.
Nous mod\'elisons ce probl\`eme sous forme d'un jeu de type {\it Cops and Robber} dans les graphes.
En particulier, \'etant donn\'es un graphe $G$ qui repr\'esente le graphe du Web et une page Web de d\'epart $v_0 \in V(G)$, nous d\'efinissons l'{\it indice de contr\^ole} de $G$, $ic(G,v_0) \in \mathbb{N}$, qui mod\'elise la vitesse minimum de t\'el\'echargement suffisante pour que l'internaute partant de $v_0$ n'attende jamais quoi qu'il fasse.
Nous consid\'erons le probl\`eme de d\'ecider si $ic(G,v_0) \leq k$ et d\'emontrons plusieurs r\'esultats de complexit\'e.
En particulier, d\'ecider si $ic(G,v_0) \leq 2$ est NP-difficile si $G$ est cordal, et d\'ecider si $ic(G,v_0) \leq 4$ est PSPACE-complet si $G$ est un graphe orient\'e acyclique.
Nous donnons un algorithme exponentiel exact qui calcule $ic(G,v_0)$ en temps $O^*(2^n)$ dans un graphe de $n$ sommets quelconque.
Puis, nous montrons que le probl\`eme est polynomial dans le cas des arbres et des graphes d'intervalles.
Enfin, nous donnons une caract\'erisation combinatoire de l'indice de contr\^ole.
Pour tout graphe $G$ et $v_0 \in V(G)$, $ic(G,v_0) \geq \max_{S} \lceil \frac{|N[S]|-1}{|S|} \rceil$ avec $v_0 \in S \subseteq V$, $S$ induit un sous-graphe connexe et $N[S]$ l'ensemble des sommets de $S$ ou voisins d'un sommet de $S$.
Il y a de plus \'egalit\'e dans le cas des arbres. |
@inproceedings{FGJ+12b,
author = {Fomin, F. V. and Giroire, F. and Jean-Marie, A. and Mazauric, D. and Nisse, N.},
title = {Satisfaire un internaute impatient est difficile},
booktitle = {{14es Rencontres Francophones sur les Aspects Algorithmiques de T{\'e}l{\'e}communications (AlgoTel)}},
year = {2012},
pages = {79-82},
note = {best paper},
abstract = {Consid\'erons un internaute qui va d'une page Web \`a une autre en suivant les liens qu'il rencontre.
Pour \'eviter que l'internaute ne (s'im)patiente, il est important d'essayer de t\'el\'echarger les documents avant que l'internaute ne les atteigne.
Cependant, le co\^ut d'un tel pr\'e-t\'el\'echargement ne doit pas exc\'eder le gain en temps qu'il g\'en\`ere.
Ainsi, il faut minimiser la bande passante utilis\'ee pour le pr\'e-t\'el\'echargement tout en s'assurant que l'internaute impatient n'attende jamais.
Nous mod\'elisons ce probl\`eme sous forme d'un jeu de type {\it Cops and Robber} dans les graphes.
En particulier, \'etant donn\'es un graphe $G$ qui repr\'esente le graphe du Web et une page Web de d\'epart $v_0 \in V(G)$, nous d\'efinissons l'{\it indice de contr\^ole} de $G$, $ic(G,v_0) \in \mathbb{N}$, qui mod\'elise la vitesse minimum de t\'el\'echargement suffisante pour que l'internaute partant de $v_0$ n'attende jamais quoi qu'il fasse.
Nous consid\'erons le probl\`eme de d\'ecider si $ic(G,v_0) \leq k$ et d\'emontrons plusieurs r\'esultats de complexit\'e.
En particulier, d\'ecider si $ic(G,v_0) \leq 2$ est NP-difficile si $G$ est cordal, et d\'ecider si $ic(G,v_0) \leq 4$ est PSPACE-complet si $G$ est un graphe orient\'e acyclique.
Nous donnons un algorithme exponentiel exact qui calcule $ic(G,v_0)$ en temps $O^*(2^n)$ dans un graphe de $n$ sommets quelconque.
Puis, nous montrons que le probl\`eme est polynomial dans le cas des arbres et des graphes d'intervalles.
Enfin, nous donnons une caract\'erisation combinatoire de l'indice de contr\^ole.
Pour tout graphe $G$ et $v_0 \in V(G)$, $ic(G,v_0) \geq \max_{S} \lceil \frac{|N[S]|-1}{|S|} \rceil$ avec $v_0 \in S \subseteq V$, $S$ induit un sous-graphe connexe et $N[S]$ l'ensemble des sommets de $S$ ou voisins d'un sommet de $S$.
Il y a de plus \'egalit\'e dans le cas des arbres.},
url = {http://hal.inria.fr/inria-00625703/en/},
pdf = {http://hal.inria.fr/inria-00625703/PDF/RR-7740.pdf},
x-editorial-board={yes},
x-proceedings={yes},
x-international-audience={no},
x-pays= {NO},
sorte = "conf-nat",
}
-
F. Giroire,
J. Moulierac,
T.K. Phan,
and F. Roudaut.
Minimization of Network Power Consumption with Redundancy Elimination.
In IFIP Networking,
Prague, Czech Republic,
pages 247-258,
May 2012.
Springer.
[WWW
] [PDF
]
| Abstract: |
|
Recently, energy-aware routing has gained increasing popularity in the networking research community.
The idea is that traffic demands are aggregated over a subset of the network links, allowing other links to be turned off to save energy.
In this paper, we propose GreenRE - a new energy-aware routing model with the support of the new technique of data redundancy elimination (RE).
This technique, enabled within the routers, can identify and remove repeated content from network transfers.
Hence, capacity of network links are virtually increased and more traffic demands can be aggregated.
Based on our real experiments on Orange Labs platform, we show that performing RE consumes some energy.
Thus, while preserving connectivity and QoS, it is important to identify at which routers to enable RE and which links to turn off so that the power consumption of the network is minimized.
We model the problem as an Integer Linear Program and propose a greedy heuristic algorithm. Simulations on several network
topologies show that GreenRE can gain further 300f energy savings in comparison with the traditional energy-aware routing model. |
@InProceedings{GMP+12,
author = {Giroire, F. and Moulierac, J. and Phan, T.K. and Roudaut, F.},
title = {Minimization of Network Power Consumption with Redundancy Elimination},
booktitle = {IFIP Networking},
year = {2012},
pages = {247-258},
address = {Prague, Czech Republic},
month = May,
publisher = {Springer},
abstract = {Recently, energy-aware routing has gained increasing popularity in the networking research community.
The idea is that traffic demands are aggregated over a subset of the network links, allowing other links to be turned off to save energy.
In this paper, we propose GreenRE - a new energy-aware routing model with the support of the new technique of data redundancy elimination (RE).
This technique, enabled within the routers, can identify and remove repeated content from network transfers.
Hence, capacity of network links are virtually increased and more traffic demands can be aggregated.
Based on our real experiments on Orange Labs platform, we show that performing RE consumes some energy.
Thus, while preserving connectivity and QoS, it is important to identify at which routers to enable RE and which links to turn off so that the power consumption of the network is minimized.
We model the problem as an Integer Linear Program and propose a greedy heuristic algorithm. Simulations on several network
topologies show that GreenRE can gain further 300f energy savings in comparison with the traditional energy-aware routing model.},
URL = {http://hal.inria.fr/hal-00721855},
PDF = {http://hal.inria.fr/docs/00/72/18/55/PDF/GMP_12.pdf},
x-editorial-board={yes},
x-proceedings={yes},
x-international-audience={yes},
x-pays = {},
sorte = "conf-int",
}
-
A. Goldman,
P. Floriano,
and A. Ferreira.
A tool for obtaining information on DTN traces.
In Proceedings of the 4th Extreme Conference on Communication,
Zurique, CH,
2012.
[PDF
]
| Abstract: |
|
The applications for dynamic networks are growing every day, and thus, so is the number of studies on them.
An important part of such studies is the generation of results through simulation and comparison with other works.
We implemented a tool to generate information on a given network trace, obtained by building its corresponding evolving graph.
This information is useful to help researchers choose the most suitable trace for their work, to interpret the results correctly and to compare data from their work to the optimal results in the network.
In this work, we present the implementation of the DTNTES tool which provides the aforementioned services and use the system to evaluate the DieselNet trace. |
@inproceedings{GPF12,
author = {Goldman, A. and Floriano, P. and Ferreira, A.},
title = {A tool for obtaining information on DTN traces},
booktitle = {Proceedings of the 4th Extreme Conference on Communication},
year = {2012},
address = {Zurique, CH},
abstract = {The applications for dynamic networks are growing every day, and thus, so is the number of studies on them.
An important part of such studies is the generation of results through simulation and comparison with other works.
We implemented a tool to generate information on a given network trace, obtained by building its corresponding evolving graph.
This information is useful to help researchers choose the most suitable trace for their work, to interpret the results correctly and to compare data from their work to the optimal results in the network.
In this work, we present the implementation of the DTNTES tool which provides the aforementioned services and use the system to evaluate the DieselNet trace.},
pdf = { extremecom2012.ee.ethz.ch/papers/12-extremecom2012-Floriano.pdf },
OPTx-editorial-board = {yes},
OPTx-proceedings = {yes},
OPTx-international-audience = {yes},
x-pays = {BR},
sorte = "conf-int",
}
-
F. Idzikowski,
R. Duque,
F. Jimenez,
E. Le Rouzic,
L. Chiaraviglio,
and M. Ajmone-Marsan.
Energy Saving in Optical Operator Networks: the Challenges, the TREND Vision, and Some Results.
In ECOC 2012 - European Conference and Exhibition on Optical Communication,
Amsterdam, Netherlands,
pages 1-3,
September 2012.
[PDF
]
| Abstract: |
|
We discuss how to save energy in IP-over-WDM networks, presenting the vision of TREND, the FP7 NoE, and the saving that can be obtained with an adaptive routing solution that puts network interfaces of various granularities to sleep in periods of low traffic.
Results refer to two operator networks, considering power and traffic forecasts for 2020. |
@inproceedings{IDJ+12,
author = {Idzikowski, F. and Duque, R. and Jimenez, F. and Le Rouzic, E. and Chiaraviglio, L. and Ajmone-Marsan, M.},
title = {{Energy Saving in Optical Operator Networks: the Challenges, the TREND Vision, and Some Results}},
abstract = {{We discuss how to save energy in IP-over-WDM networks, presenting the vision of TREND, the FP7 NoE, and the saving that can be obtained with an adaptive routing solution that puts network interfaces of various granularities to sleep in periods of low traffic.
Results refer to two operator networks, considering power and traffic forecasts for 2020.}},
booktitle = {{ECOC 2012 - European Conference and Exhibition on Optical Communication}},
address = {Amsterdam, Netherlands},
year = {2012},
pages = {1-3},
month = Sep,
pdf={http://www.telematica.polito.it/oldsite/chiaraviglio/papers/ECOC2012.pdf},
x-pays={IT,ES,DE,FR},
OPTx-editorial-board={no},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
sorte = "inv-conf"
}
-
A. Kosowski,
B. Li,
N. Nisse,
and K. Suchan.
k-Chordal Graphs: from Cops and Robber to Compact Routing via Treewidth.
In 39th International Colloquium on Automata, Languages and Programming (ICALP, track C),
volume 7392,
pages 610-622,
2012.
Springer, LNCS.
[WWW
] [PDF
]
| Abstract: |
|
{\it Cops and robber games} concern a team of cops that must capture a robber moving in a graph.
We consider the class of $k$-chordal graphs, i.e., graphs with no induced cycle of length greater than $k$, $k\geq 3$.
We prove that $k-1$ cops are always sufficient to capture a robber in $k$-chordal graphs.
This leads us to our main result, a new structural decomposition for a graph class including $k$-chordal graphs.
We present a quadratic algorithm that, given a graph $G$ and $k\geq 3$, either returns an induced cycle larger than $k$ in $G$, or computes a {\it tree-decomposition} of $G$, each {\it bag} of which contains a dominating path with at most $k-1$ vertices.
This allows us to prove that any $k$-chordal graph with maximum degree $\Delta$ has treewidth at most $(k-1)(\Delta-1)+2$, improving the $O(\Delta (\Delta-1)^{k-3})$ bound of Bodlaender and Thilikos (1997).
Moreover, any graph admitting such a tree-decomposition has hyperbolicity $\leq\lfloor \frac{3}{2}k\rfloor$.
As an application, for any $n$-node graph admitting such a tree-decomposition, we propose a {\it compact routing scheme} using routing tables, addresses and headers of size $O(\log n)$ bits and achieving an additive stretch of $O(k\log \Delta)$.
As far as we know, this is the first routing scheme with $O(\log n)$-routing tables and small additive stretch for $k$-chordal graphs. |
@inproceedings{KLN+12b,
author = {Kosowski, A. and Li, B. and Nisse, N. and Suchan, K.},
title = {k-Chordal Graphs: from Cops and Robber to Compact Routing via Treewidth},
booktitle = {39th International Colloquium on Automata, Languages and Programming (ICALP, track C)},
publisher = {Springer, LNCS},
year = {2012},
volume = {7392},
pages = {610-622},
abstract = {{\it Cops and robber games} concern a team of cops that must capture a robber moving in a graph.
We consider the class of $k$-chordal graphs, i.e., graphs with no induced cycle of length greater than $k$, $k\geq 3$.
We prove that $k-1$ cops are always sufficient to capture a robber in $k$-chordal graphs.
This leads us to our main result, a new structural decomposition for a graph class including $k$-chordal graphs.
We present a quadratic algorithm that, given a graph $G$ and $k\geq 3$, either returns an induced cycle larger than $k$ in $G$, or computes a {\it tree-decomposition} of $G$, each {\it bag} of which contains a dominating path with at most $k-1$ vertices.
This allows us to prove that any $k$-chordal graph with maximum degree $\Delta$ has treewidth at most $(k-1)(\Delta-1)+2$, improving the $O(\Delta (\Delta-1)^{k-3})$ bound of Bodlaender and Thilikos (1997).
Moreover, any graph admitting such a tree-decomposition has hyperbolicity $\leq\lfloor \frac{3}{2}k\rfloor$.
As an application, for any $n$-node graph admitting such a tree-decomposition, we propose a {\it compact routing scheme} using routing tables, addresses and headers of size $O(\log n)$ bits and achieving an additive stretch of $O(k\log \Delta)$.
As far as we know, this is the first routing scheme with $O(\log n)$-routing tables and small additive stretch for $k$-chordal graphs.},
url = {http://hal.inria.fr/hal-00671861},
pdf = {http://hal.archives-ouvertes.fr/docs/00/67/18/97/PDF/RR-7888.pdf},
x-editorial-board={yes},
x-proceedings={yes},
x-international-audience={yes},
x-pays = {CL},
sorte = "conf-int",
}
-
A. Kosowski,
B. Li,
N. Nisse,
and K. Suchan.
k-Chordal Graphs: from Cops and Robber to Compact Routing via Treewidth.
In 14es Rencontres Francophones sur les Aspects Algorithmiques de Télécommunications (AlgoTel),
pages 83-86,
2012.
[WWW
] [PDF
]
| Abstract: |
|
{\it Cops and robber games} concern a team of cops that must capture a robber moving in a graph.
We consider the class of $k$-chordal graphs, i.e., graphs with no induced cycle of length greater than $k$, $k\geq 3$.
We prove that $k-1$ cops are always sufficient to capture a robber in $k$-chordal graphs.
This leads us to our main result, a new structural decomposition for a graph class including $k$-chordal graphs.
We present a quadratic algorithm that, given a graph $G$ and $k\geq 3$, either returns an induced cycle larger than $k$ in $G$, or computes a {\it tree-decomposition} of $G$, each {\it bag} of which contains a dominating path with at most $k-1$ vertices.
This allows us to prove that any $k$-chordal graph with maximum degree $\Delta$ has treewidth at most $(k-1)(\Delta-1)+2$, improving the $O(\Delta (\Delta-1)^{k-3})$ bound of Bodlaender and Thilikos (1997).
Moreover, any graph admitting such a tree-decomposition has hyperbolicity $\leq\lfloor \frac{3}{2}k\rfloor$.
As an application, for any $n$-node graph admitting such a tree-decomposition, we propose a {\it compact routing scheme} using routing tables, addresses and headers of size $O(\log n)$ bits and achieving an additive stretch of $O(k\log \Delta)$.
As far as we know, this is the first routing scheme with $O(\log n)$-routing tables and small additive stretch for $k$-chordal graphs. |
@inproceedings{KLN+12c,
author = {Kosowski, A. and Li, B. and Nisse, N. and Suchan, K.},
title = {k-Chordal Graphs: from Cops and Robber to Compact Routing via Treewidth},
booktitle = {14es Rencontres Francophones sur les Aspects Algorithmiques de T{\'e}l{\'e}communications (AlgoTel)},
year = {2012},
pages = {83-86},
abstract = {{\it Cops and robber games} concern a team of cops that must capture a robber moving in a graph.
We consider the class of $k$-chordal graphs, i.e., graphs with no induced cycle of length greater than $k$, $k\geq 3$.
We prove that $k-1$ cops are always sufficient to capture a robber in $k$-chordal graphs.
This leads us to our main result, a new structural decomposition for a graph class including $k$-chordal graphs.
We present a quadratic algorithm that, given a graph $G$ and $k\geq 3$, either returns an induced cycle larger than $k$ in $G$, or computes a {\it tree-decomposition} of $G$, each {\it bag} of which contains a dominating path with at most $k-1$ vertices.
This allows us to prove that any $k$-chordal graph with maximum degree $\Delta$ has treewidth at most $(k-1)(\Delta-1)+2$, improving the $O(\Delta (\Delta-1)^{k-3})$ bound of Bodlaender and Thilikos (1997).
Moreover, any graph admitting such a tree-decomposition has hyperbolicity $\leq\lfloor \frac{3}{2}k\rfloor$.
As an application, for any $n$-node graph admitting such a tree-decomposition, we propose a {\it compact routing scheme} using routing tables, addresses and headers of size $O(\log n)$ bits and achieving an additive stretch of $O(k\log \Delta)$.
As far as we know, this is the first routing scheme with $O(\log n)$-routing tables and small additive stretch for $k$-chordal graphs.},
url = {http://hal.inria.fr/hal-00671861},
pdf = {http://hal.archives-ouvertes.fr/docs/00/67/18/97/PDF/RR-7888.pdf},
x-editorial-board={yes},
x-proceedings={yes},
x-international-audience={no},
x-pays= {CL},
sorte = "conf-nat",
}
-
J. Moulierac,
T.K. Phan,
N. Thoai,
and N.C. Tran.
Xcast6 Treemap Islands - Revisiting Multicast Model.
In ACM CoNEXT Student Workshop,
Nice, France,
December 2012.
ACM.
[WWW
] [PDF
]
| Abstract: |
|
Due to the complexity and poor scalability, IP Multicast has not been used on the Internet. Recently, Xcast6 - a complementary protocol of IP Multicast has been proposed.
However, the key limitation of Xcast6 is that it only supports small multicast sessions.
To overcome this, we propose Xcast6 Treemap islands (X6Ti) - a hybrid model of Overlay Multicast and Xcast6.
In summary, X6Ti has many advantages: support large multicast groups, simple and easy to deploy on the Internet, no router configuration, no restriction on the number of groups, no multicast routing protocol and no group management protocol.
Based on simulation, we compare X6Ti with IP Multicast and NICE protocols to show the benefits of our new model. |
@InProceedings{PMT+12,
author = {Moulierac, J. and Phan, T.K. and Thoai, N. and Tran, N.C.},
title = {Xcast6 Treemap Islands - Revisiting Multicast Model},
booktitle = {ACM CoNEXT Student Workshop},
pages = {},
year = {2012},
OPTeditor = {},
OPTvolume = {},
OPTnumber = {},
OPTseries = {},
address = {Nice, France},
month = December,
OPTorganization = {},
publisher = {ACM},
OPTnote = {},
OPTannote = {},
URL = {http://hal.inria.fr/hal-00749266},
PDF = {http://hal.inria.fr/docs/00/74/92/66/PDF/stud16-phan.pdf},
abstract = {Due to the complexity and poor scalability, IP Multicast has not been used on the Internet. Recently, Xcast6 - a complementary protocol of IP Multicast has been proposed.
However, the key limitation of Xcast6 is that it only supports small multicast sessions.
To overcome this, we propose Xcast6 Treemap islands (X6Ti) - a hybrid model of Overlay Multicast and Xcast6.
In summary, X6Ti has many advantages: support large multicast groups, simple and easy to deploy on the Internet, no router configuration, no restriction on the number of groups, no multicast routing protocol and no group management protocol.
Based on simulation, we compare X6Ti with IP Multicast and NICE protocols to show the benefits of our new model.},
x-editorial-board={yes},
x-proceedings={yes},
x-international-audience={yes},
x-pays = {VN},
sorte = "conf-int",
}
-
D.D. Nguyen,
T.K. Phan,
N. Thoai,
and T.T. Tran.
MaxNet and TCP Reno/RED on Mice Traffic.
In Modeling, Simulation and Optimization of Complex Processes,
pages 247-255,
2012.
Springer Berlin Heidelberg.
[WWW
] [PDF
]
| Abstract: |
|
Congestion control is a distributed algorithm to share network bandwidth among competing users on the Internet.
In the common case, quick response time for mice traffic (HTTP traffic) is desired when mixed with elephant traffic (FTP traffic).
The current approach using loss-based with Additive Increase, Multiplicative Decrease (AIMD) is too greedy and eventually, most of the network bandwidth would be consumed by elephant traffic.
As a result, it causes longer response time for mice traffic because there is no room left at the routers.
MaxNet is a new TCP congestion control architecture using an explicit signal to control transmission rate at the source node.
In this paper, we show that MaxNet can control well the queue length at routers and therefore the response time to HTTP traffic is several times faster than with TCP Reno/RED. |
@InProceedings{PTN+12,
author = {Nguyen, D.D. and Phan, T.K. and Thoai, N. and Tran, T.T.},
title = {MaxNet and TCP Reno/RED on Mice Traffic},
booktitle = {Modeling, Simulation and Optimization of Complex Processes},
year = {2012},
pages = {247-255},
publisher = {Springer Berlin Heidelberg},
abstract = {Congestion control is a distributed algorithm to share network bandwidth among competing users on the Internet.
In the common case, quick response time for mice traffic (HTTP traffic) is desired when mixed with elephant traffic (FTP traffic).
The current approach using loss-based with Additive Increase, Multiplicative Decrease (AIMD) is too greedy and eventually, most of the network bandwidth would be consumed by elephant traffic.
As a result, it causes longer response time for mice traffic because there is no room left at the routers.
MaxNet is a new TCP congestion control architecture using an explicit signal to control transmission rate at the source node.
In this paper, we show that MaxNet can control well the queue length at routers and therefore the response time to HTTP traffic is several times faster than with TCP Reno/RED.},
URL = {http://hal.inria.fr/hal-00721882},
PDF = {http://hal.inria.fr/docs/00/72/18/82/PDF/PTN_12.pdf},
x-editorial-board={yes},
x-proceedings={yes},
x-international-audience={yes},
x-pays = {VN},
sorte = "conf-int",
}
-
J. Araujo,
F. Giroire,
Y. Liu,
R. Modrzejewski,
and J. Moulierac.
Energy Efficient Content Distribution.
Technical report RR-8091,
INRIA,
October 2012.
[WWW
] [PDF
]
| Abstract: |
|
To optimize energy efficiency in network, operators try to switch off as many network devices as possible.
Recently, there is a trend to introduce content caches as an inherent capacity of network equipment, with the objective of improving the efficiency of content distribution and reducing network congestion.
In this work, we study the impact of using in-network caches and CDN cooperation on an energy-efficient routing.
We formulate this problem as Energy Efficient Content Distribution.
The objective is to find a feasible routing, so that the total energy con- sumption of the network is minimized subject to satisfying all the demands and link capacity.
We exhibit the range of parameters (size of caches, popularity of content, demand intensity, etc.) for which caches are useful.
Experiment results show that by placing a cache on each backbone router to store the most popular content, along with well choosing the best content provider server for each demand to a CDN, we can save a total up to 23\0f power in the backbone, while 16\Ran be gained solely thanks to caches. |
@techreport{AGL+12,
author = {Araujo, J. and Giroire, F. and Liu, Y. and Modrzejewski, R. and Moulierac, J.},
title = {{Energy Efficient Content Distribution}},
year = {2012},
month = Oct,
institution = {INRIA},
affiliation = {MASCOTTE - INRIA Sophia Antipolis / Laboratoire I3S , Parallelism, Graphs and Optimization Research Group - ParGO , JCP-Consult},
number = {RR-8091},
abstract = {{To optimize energy efficiency in network, operators try to switch off as many network devices as possible.
Recently, there is a trend to introduce content caches as an inherent capacity of network equipment, with the objective of improving the efficiency of content distribution and reducing network congestion.
In this work, we study the impact of using in-network caches and CDN cooperation on an energy-efficient routing.
We formulate this problem as Energy Efficient Content Distribution.
The objective is to find a feasible routing, so that the total energy con- sumption of the network is minimized subject to satisfying all the demands and link capacity.
We exhibit the range of parameters (size of caches, popularity of content, demand intensity, etc.) for which caches are useful.
Experiment results show that by placing a cache on each backbone router to store the most popular content, along with well choosing the best content provider server for each demand to a CDN, we can save a total up to 23\0f power in the backbone, while 16\Ran be gained solely thanks to caches.}},
url = {http://hal.inria.fr/hal-00743248},
pdf = {http://hal.inria.fr/hal-00743248/PDF/report.pdf},
OPTx-editorial-board={no},
OPTx-proceedings={no},
OPTx-international-audience={no},
x-pays={BR},
sorte = "Rapports",
}
-
J. Araujo,
G. Morel,
L. Sampaio,
R. Soares,
and V. Weber.
Hull number: $P_5$-free graphs and reduction rules.
Technical report RR-8045,
INRIA,
August 2012.
[WWW
] [PDF
]
| Abstract: |
|
In this paper, we study the (geodesic) hull number of graphs.
For any two vertices $u,v\in V$ of a connected undirected graph $G=(V,E)$, the closed interval $I[u,v]$ of $u$ and $v$ is the set of vertices that belong to some shortest $(u,v)$-path.
For any $S \subseteq V$, let $I[S]= \bigcup\_{u,v\in S} I[u,v]$.
A subset $S\subseteq V$ is (geodesically) convex if $I[S] = S$.
Given a subset $S\subseteq V$, the convex hull $I\_h[S]$ of $S$ is the smallest convex set that contains $S$.
We say that $S$ is a hull set of $G$ if $I\_h[S] = V$.
The size of a minimum hull set of $G$ is the hull number of $G$, denoted by $hn(G)$.
First, we show a polynomial-time algorithm to compute the hull number of any $P\_5$-free triangle-free graph.
Then, we present four reduction rules based on vertices with the same neighborhood.
We use these reduction rules to propose a fixed parameter tractable algorithm to compute the hull number of any graph $G$, where the parameter can be the size of a vertex cover of $G$ or, more generally, its neighborhood diversity, and we also use these reductions to characterize the hull number of the lexicographic product of any two graphs. |
@techreport{AMS+12,
title = {Hull number: $P_5$-free graphs and reduction rules},
author = {Araujo, J. and Morel, G. and Sampaio, L. and Soares, R. and Weber, V.},
year = {2012},
month = Aug,
language = {Anglais},
affiliation = {MASCOTTE - INRIA Sophia Antipolis / Laboratoire I3S , Parallelism, Graphs and Optimization Research Group - ParGO , Laboratoire des sciences pour la conception, l'optimisation et la production - G-SCOP},
pages = {10},
institution = {INRIA},
number = {RR-8045},
abstract = {{In this paper, we study the (geodesic) hull number of graphs.
For any two vertices $u,v\in V$ of a connected undirected graph $G=(V,E)$, the closed interval $I[u,v]$ of $u$ and $v$ is the set of vertices that belong to some shortest $(u,v)$-path.
For any $S \subseteq V$, let $I[S]= \bigcup\_{u,v\in S} I[u,v]$.
A subset $S\subseteq V$ is (geodesically) convex if $I[S] = S$.
Given a subset $S\subseteq V$, the convex hull $I\_h[S]$ of $S$ is the smallest convex set that contains $S$.
We say that $S$ is a hull set of $G$ if $I\_h[S] = V$.
The size of a minimum hull set of $G$ is the hull number of $G$, denoted by $hn(G)$.
First, we show a polynomial-time algorithm to compute the hull number of any $P\_5$-free triangle-free graph.
Then, we present four reduction rules based on vertices with the same neighborhood.
We use these reduction rules to propose a fixed parameter tractable algorithm to compute the hull number of any graph $G$, where the parameter can be the size of a vertex cover of $G$ or, more generally, its neighborhood diversity, and we also use these reductions to characterize the hull number of the lexicographic product of any two graphs.}},
url = {http://hal.inria.fr/hal-00724120},
pdf = {http://hal.inria.fr/hal-00724120/PDF/RR-8045.pdf},
OPTx-editorial-board={no},
OPTx-proceedings={no},
OPTx-international-audience={no},
x-pays = {BR},
sorte = "Rapports",
}
-
J. Bang-Jensen,
F. Havet,
and A. K. Maia.
Finding a subdivision of a digraph.
Technical report RR-8024,
INRIA,
July 2012.
[WWW
] [PDF
]
| Abstract: |
|
We consider the following problem for oriented graphs and digraphs: Given a directed graph D, does it contain a subdivision of a prescribed digraph F?
We give a number of examples of polynomial instances, several NP-completeness proofs as well as a number of conjectures and open problems. |
@techreport{BHM12,
author = {Bang-Jensen, J. and Havet, F. and Maia, A. K.},
title = {Finding a subdivision of a digraph},
institution = {INRIA},
number = {RR-8024},
year = {2012},
month = Jul,
abstract = {We consider the following problem for oriented graphs and digraphs: Given a directed graph D, does it contain a subdivision of a prescribed digraph F?
We give a number of examples of polynomial instances, several NP-completeness proofs as well as a number of conjectures and open problems.},
url = {http://hal.inria.fr/hal-00720500},
pdf = {http://hal.inria.fr/hal-00720500/PDF/RR-8024.pdf},
x-editorial-board={no},
x-proceedings={no},
x-international-audience={no},
x-pays = {DK},
sorte = "Rapports",
}
-
J-C. Bermond,
D. Coudert,
G. D'Angelo,
and F. Z. Moataz.
Diverse Routing with the star property.
Technical report RR-8071,
INRIA,
September 2012.
[WWW
] [PDF
]
| Abstract: |
|
The notion of Shared Risk Link Groups (SRLG) has been introduced to capture survivability issues where a set of links of a network fail simultaneously.
In this context, the \emph{diverse routing} problem is to find a set of SRLG-disjoint paths between a given pair of end nodes of the network.
This problem has been proved $NP$-complete in general\~\cite{Hu03} and some polynomial instances have been characterized\~\cite{CDP+07}.
In this paper, we investigate the diverse routing problem in networks satisfying the \emph{star property}\~\cite{LW05}.
This property states that an edge may be subject to several SRLGs but all edges subject to a given SRLG are incident to a common node.
We first provide counter-examples to the polynomial time algorithm proposed in\~\cite{LW05} for computing pairs of SRLG-disjoint paths in networks with the star property, and then prove that this problem is in fact $NP$-hard in the strong sense.
More generally, we prove that the diverse routing problem in networks with the star property is $NP$-hard in the strong sense, hard to approximate, and $W[1]$-hard when the parameter is the number of SRLG-disjoint paths. Last, we devise polynomial time algorithms for practically relevant subcases, in particular when the number of SRLG is constant, the maximum degree of the vertices is strictly smaller than 5, and when the network is a directed acyclic graph. |
@techreport{BCD+12b,
author = {Bermond, J-C. and Coudert, D. and D'Angelo, G. and Moataz, F. Z.},
title = {{Diverse Routing with the star property}},
language = {Anglais},
affiliation = {MASCOTTE - INRIA Sophia Antipolis / Laboratoire I3S},
institution = {INRIA},
number = {RR-8071},
year = {2012},
month = Sep,
abstract = {{The notion of Shared Risk Link Groups (SRLG) has been introduced to capture survivability issues where a set of links of a network fail simultaneously.
In this context, the \emph{diverse routing} problem is to find a set of SRLG-disjoint paths between a given pair of end nodes of the network.
This problem has been proved $NP$-complete in general\~\cite{Hu03} and some polynomial instances have been characterized\~\cite{CDP+07}.
In this paper, we investigate the diverse routing problem in networks satisfying the \emph{star property}\~\cite{LW05}.
This property states that an edge may be subject to several SRLGs but all edges subject to a given SRLG are incident to a common node.
We first provide counter-examples to the polynomial time algorithm proposed in\~\cite{LW05} for computing pairs of SRLG-disjoint paths in networks with the star property, and then prove that this problem is in fact $NP$-hard in the strong sense.
More generally, we prove that the diverse routing problem in networks with the star property is $NP$-hard in the strong sense, hard to approximate, and $W[1]$-hard when the parameter is the number of SRLG-disjoint paths. Last, we devise polynomial time algorithms for practically relevant subcases, in particular when the number of SRLG is constant, the maximum degree of the vertices is strictly smaller than 5, and when the network is a directed acyclic graph.}},
hal_id = {hal-00733869},
url = {http://hal.inria.fr/hal-00733869},
pdf = {http://hal.inria.fr/hal-00733869/PDF/RR-8071.pdf},
x-pays = {IT,MA},
x-editorial-board={no},
x-proceedings={no},
x-international-audience={yes},
sorte = "Rapports",
}
-
L. Blin,
J. Burman,
and N. Nisse.
Perpetual Graph Searching.
Technical report RR-7897,
INRIA,
February 2012.
[WWW
] [PDF
]
| Abstract: |
|
In {\it graph searching}, a team of mobile agents aims at clearing the edges of a contaminated graph.
To clear an edge, an agent has to slide along it, however, an edge can be {\it recontaminated} if there is a path without agents from a contaminated edge to a clear edge.
To goal of graph searching is to clear the graph, i.e., all edges are clear simultaneously, using the fewest number of agents.
We study this problem in the {\it minimal CORDA} model of distributed computation.
This model has very weak hypothesis: network nodes and agents are anonymous, have no memory of the past, and agents have no common sense of orientation.
Moreover, all agents execute the same algorithm in the {\it Look-Compute-Move} manner and in an asynchronous environment.
One interest of this model is that, if the clearing can be done by the agents starting from arbitrary positions (e.g., after faults or recontamination), the lack of memory implies that the clearing is done perpetually and then provides a first approach of fault-tolerant graph searching.
Constraints due to the minimal CORDA model lead us to define a new variant of graph searching, called {\it graph searching without collisions}, where more than one agent cannot occupy the same node.
We show that, in a centralized setting, this variant does not have the same behavior as classical graph searching.
For instance, it not monotonous nor close by subgraph. We show that, in a graph with maximum degree $\Delta$, the smallest number of agents required to clear a graph without collisions is at most $\Delta$ times the number of searchers required when collisions are allowed.
Moreover, this bound is tight up to a constant ratio. Then, we fully characterize graph searching without collisions in trees.
In a distributed setting, i.e., in the minimal CORDA model, the question we ask is the following. Given a graph $G$, does there exist an algorithm that clears $G$, whatever be the initial positions of the agents on distinct vertices.
In the case of a path network, we show that it is not possible is the number of agents is even in a path of odd order, or if there are at most two agents in a path with at least three vertices. We present an algorithm that clears all paths in all remaining cases.
Finally, we propose an algorithm that clears any tree using a sufficient number of agents. |
@techreport{BBN12a,
author = {L. Blin and J. Burman and N. Nisse},
title = {Perpetual Graph Searching},
url = {http://hal.archives-ouvertes.fr/hal-00675233},
pdf ={http://hal.archives-ouvertes.fr/docs/00/67/52/33/PDF/RR-7897.pdf},
institution = {INRIA},
number = {RR-7897},
year = {2012},
month = feb,
abstract = {In {\it graph searching}, a team of mobile agents aims at clearing the edges of a contaminated graph.
To clear an edge, an agent has to slide along it, however, an edge can be {\it recontaminated} if there is a path without agents from a contaminated edge to a clear edge.
To goal of graph searching is to clear the graph, i.e., all edges are clear simultaneously, using the fewest number of agents.
We study this problem in the {\it minimal CORDA} model of distributed computation.
This model has very weak hypothesis: network nodes and agents are anonymous, have no memory of the past, and agents have no common sense of orientation.
Moreover, all agents execute the same algorithm in the {\it Look-Compute-Move} manner and in an asynchronous environment.
One interest of this model is that, if the clearing can be done by the agents starting from arbitrary positions (e.g., after faults or recontamination), the lack of memory implies that the clearing is done perpetually and then provides a first approach of fault-tolerant graph searching.
Constraints due to the minimal CORDA model lead us to define a new variant of graph searching, called {\it graph searching without collisions}, where more than one agent cannot occupy the same node.
We show that, in a centralized setting, this variant does not have the same behavior as classical graph searching.
For instance, it not monotonous nor close by subgraph. We show that, in a graph with maximum degree $\Delta$, the smallest number of agents required to clear a graph without collisions is at most $\Delta$ times the number of searchers required when collisions are allowed.
Moreover, this bound is tight up to a constant ratio. Then, we fully characterize graph searching without collisions in trees.
In a distributed setting, i.e., in the minimal CORDA model, the question we ask is the following. Given a graph $G$, does there exist an algorithm that clears $G$, whatever be the initial positions of the agents on distinct vertices.
In the case of a path network, we show that it is not possible is the number of agents is even in a path of odd order, or if there are at most two agents in a path with at least three vertices. We present an algorithm that clears all paths in all remaining cases.
Finally, we propose an algorithm that clears any tree using a sufficient number of agents.},
x-editorial-board={no},
x-proceedings={no},
x-international-audience={no},
x-pays = {},
sorte = "Rapports",
}
-
V. Campos,
F. Havet,
R. Sampaio,
and A. Silva.
Backbone colouring: tree backbones with small diameter in planar graphs.
Technical report RR-8151,
INRIA,
November 2012.
[WWW
] [PDF
]
| Abstract: |
|
Given a graph $G$ and a spanning subgraph $T$ of $G$, a {\it backbone $k$-colouring} for $(G,T)$ is a mapping $c:V(G)\to\{1,\ldots,k\}$ such that $|c(u)-c(v)|\geq 2$ for every edge $uv\in E(T)$ and $|c(u)-c(v)|\geq 1$ for every edge $uv\in E(G)\setminus E(T)$.
The {\it backbone chromatic number} $BBC(G,T)$ is the smallest integer $k$ such that there exists a backbone $k$-colouring of $(G,T)$.
In 2007, Broersma et al. \cite{BFG+07} conjectured that $BBC(G,T)\leq 6$ for every planar graph $G$ and every spanning tree $T$ of $G$.
In this paper, we prove this conjecture when $T$ has diameter at most four. |
@techreport{CHS+12,
author = {Campos, V. and Havet, F. and Sampaio, R. and Silva, A.},
title = {{Backbone colouring: tree backbones with small diameter in planar graphs}},
year = {2012},
month = Nov,
institution = {INRIA},
affiliation = {Parallelism, Graphs and Optimization Research Group - ParGO , MASCOTTE - INRIA Sophia Antipolis / Laboratoire I3S},
number = {RR-8151},
language = {Anglais},
abstract = {{Given a graph $G$ and a spanning subgraph $T$ of $G$, a {\it backbone $k$-colouring} for $(G,T)$ is a mapping $c:V(G)\to\{1,\ldots,k\}$ such that $|c(u)-c(v)|\geq 2$ for every edge $uv\in E(T)$ and $|c(u)-c(v)|\geq 1$ for every edge $uv\in E(G)\setminus E(T)$.
The {\it backbone chromatic number} $BBC(G,T)$ is the smallest integer $k$ such that there exists a backbone $k$-colouring of $(G,T)$.
In 2007, Broersma et al. \cite{BFG+07} conjectured that $BBC(G,T)\leq 6$ for every planar graph $G$ and every spanning tree $T$ of $G$.
In this paper, we prove this conjecture when $T$ has diameter at most four.}},
url = {http://hal.inria.fr/hal-00758548},
pdf = {http://hal.inria.fr/hal-00758548/PDF/RR-8151.pdf},
OPTx-editorial-board={no},
OPTx-proceedings={no},
OPTx-international-audience={no},
x-pays={BR},
sorte = "Rapports",
}
-
N. Cohen,
D. Coudert,
and A. Lancin.
Exact and approximate algorithms for computing the hyperbolicity of large-scale graphs.
Technical report RR-8074,
INRIA,
September 2012.
[WWW
] [PDF
]
| Abstract: |
|
Let $G$ be a connected graph, and let $\dd(a,b)$ denotes the shortest path distance between vertices $a$ and $b$ of $G$.
The graph $G$ is $\delta$-hyperbolic if for any vertices $a, b, c, d$ of $G$, the two largest of the three sums $S\_1=\dd(a,b)+\dd(c,d)$, $S\_2 = \dd(a,c)+\dd(b,d)$, and $S\_3 = \dd(a,d)+\dd(b,c)$ differ by at most $2\delta$.
This can be determined in time $O(n^4)$ which could be prohibitive for large graphs.
In this document, we propose an exact algorithm for determining the hyperbolicity of a graph that is scalable for large graphs.
The time complexity of this algorithm is a function of the size of the largest bi-connected component of the graph, of the shortest path distance distribution in this componenant and of the value of the hyperbolicity.
In the worst case, the time complexity remains in $O(n^4)$, but it is much faster in practice. We also propose both a multiplicative factor and an additive constant approximation algorithms.
We then analyze further the time complexity of our exact algorithm for several class of graphs, and present some computational results on large-scale graphs. |
@techreport{CCL12,
url = {http://hal.inria.fr/hal-00735481},
title = {{Exact and approximate algorithms for computing the hyperbolicity of large-scale graphs}},
author = {Cohen, N. and Coudert, D. and Lancin, A.},
abstract = {{Let $G$ be a connected graph, and let $\dd(a,b)$ denotes the shortest path distance between vertices $a$ and $b$ of $G$.
The graph $G$ is $\delta$-hyperbolic if for any vertices $a, b, c, d$ of $G$, the two largest of the three sums $S\_1=\dd(a,b)+\dd(c,d)$, $S\_2 = \dd(a,c)+\dd(b,d)$, and $S\_3 = \dd(a,d)+\dd(b,c)$ differ by at most $2\delta$.
This can be determined in time $O(n^4)$ which could be prohibitive for large graphs.
In this document, we propose an exact algorithm for determining the hyperbolicity of a graph that is scalable for large graphs.
The time complexity of this algorithm is a function of the size of the largest bi-connected component of the graph, of the shortest path distance distribution in this componenant and of the value of the hyperbolicity.
In the worst case, the time complexity remains in $O(n^4)$, but it is much faster in practice. We also propose both a multiplicative factor and an additive constant approximation algorithms.
We then analyze further the time complexity of our exact algorithm for several class of graphs, and present some computational results on large-scale graphs.}},
language = {Anglais},
affiliation = {Laboratoire de Recherche en Informatique - LRI , MASCOTTE - INRIA Sophia Antipolis / Laboratoire I3S},
institution = {INRIA},
number = {RR-8074},
year = {2012},
month = Sep,
pdf = {http://hal.inria.fr/hal-00735481/PDF/RR-8074-v2.pdf},
x-pays = {},
x-editorial-board={no},
x-proceedings={no},
x-international-audience={yes},
sorte = "Rapports",
}
-
G. D'Angelo,
G. Di Stefano,
and A. Navarra.
How to gather asynchronous oblivious robots on anonymous rings.
Technical report RR-7963,
INRIA,
2012.
[WWW
] [PDF
]
| Abstract: |
|
A set of robots arbitrarily placed on the nodes of an anonymous graph have to meet at one common node and remain in there.
This problem is known in the literature as the \emph{gathering}.
Robots operate in Look-Compute-Move cycles;
in one cycle, a robot takes a snapshot of the current configuration (Look), decides whether to stay idle or to move to one of its neighbors (Compute), and in the latter case makes the computed move instantaneously (Move).
Cycles are performed asynchronously for each robot.
Moreover, each robot is empowered by the so called \emph{multiplicity detection} capability, that is, a robot is able to detect during its Look operation whether a node is empty, or occupied by one robot, or occupied by an undefined number of robots greater than one.
The described problem has been extensively studied during the last years.
However, the known solutions work only for specific initial configurations and leave some open cases.
In this paper, we provide an algorithm which solves the general problem, and is able to detect all the non-gatherable configurations.
It is worth noting that our new algorithm makes use of a unified and general strategy for any initial configuration. |
@techreport{DDN12b,
author = {D'Angelo, G. and Di Stefano, G. and Navarra, A.},
title = {{How to gather asynchronous oblivious robots on anonymous rings}},
year = {2012},
institution = {INRIA},
number = {RR-7963},
pages = {24},
abstract = {{A set of robots arbitrarily placed on the nodes of an anonymous graph have to meet at one common node and remain in there.
This problem is known in the literature as the \emph{gathering}.
Robots operate in Look-Compute-Move cycles;
in one cycle, a robot takes a snapshot of the current configuration (Look), decides whether to stay idle or to move to one of its neighbors (Compute), and in the latter case makes the computed move instantaneously (Move).
Cycles are performed asynchronously for each robot.
Moreover, each robot is empowered by the so called \emph{multiplicity detection} capability, that is, a robot is able to detect during its Look operation whether a node is empty, or occupied by one robot, or occupied by an undefined number of robots greater than one.
The described problem has been extensively studied during the last years.
However, the known solutions work only for specific initial configurations and leave some open cases.
In this paper, we provide an algorithm which solves the general problem, and is able to detect all the non-gatherable configurations.
It is worth noting that our new algorithm makes use of a unified and general strategy for any initial configuration.}},
url = {http://hal.inria.fr/hal-00697132},
pdf = {http://hal.inria.fr/hal-00697132/PDF/RR-7963.pdf},
OPTx-editorial-board={no},
OPTx-proceedings={no},
OPTx-international-audience={no},
x-pays = {IT},
sorte = "Rapports",
}
-
G. D'Angelo,
G. Di Stefano,
A. Navarra,
N. Nisse,
and K. Suchan.
A unified approach for different tasks on rings in robot-based computing systems.
Technical report RR-8013,
INRIA,
2012.
[WWW
] [PDF
]
| Abstract: |
|
A set of autonomous robots have to collaborate in order to accomplish a common task in a ring-topology where neither nodes nor edges are labeled.
We present a unified approach to solve three important problems in the field: the \emph{exclusive perpetual exploration}, the \emph{exclusive perpetual graph searching} and the \emph{gathering} problems.
In the first problem, each robot aims at visiting each node infinitely often; in perpetual graph searching, the team of robots aims at clearing all edges of the network infinitely often; and in the gathering problem, all robots must eventually occupy the same node.
We investigate these tasks in the famous {\it CORDA} distributed computing model where the robots cannot communicate but can perceive the positions of other robots.
More precisely, each robot is equipped with visibility sensors and motion actuators, and it operates in {\it Look-Compute-Move} asynchronous cycles.
In each cycle, a robot takes a snapshot of the current global configuration (Look), then, based on the perceived configuration, takes a decision to stay idle or to move to one of its adjacent nodes (Compute), and in the latter case it eventually moves to this neighbor (Move).
Moreover, robots are endowed with very weak capabilities.
Namely, they are {\it anonymous}, {\it oblivious}, {\it uniform} (execute the same algorithm) and have {\it no common sense of orientation}.
For the first two problems, the {\it exclusivity constraint} must also be satisfied, i.e., a node can be occupied by at most one robot.
Finally, the robots have the {\it local multiplicity detection capability} which is required to solve the gathering problem.
In this setting, we devise algorithms that, starting from any exclusive rigid (i.e. aperiodic and asymmetric) configuration, solve the three above mentioned problems in anonymous ring-topologies.
Our main algorithms consist of two phases.
The first phase is common to all problems and allows $k>2$ robots to achieve a particular configuration in an $n$-node ring, $k9)$ and $(k=5,n=10)$. |
@techreport{ADN+12,
author = {D'Angelo, G. and Di Stefano, G. and Navarra, A. and Nisse, N. and Suchan, K.},
title = {{A unified approach for different tasks on rings in robot-based computing systems}},
year = {2012},
institution = {INRIA},
number = {RR-8013},
abstract = {{A set of autonomous robots have to collaborate in order to accomplish a common task in a ring-topology where neither nodes nor edges are labeled.
We present a unified approach to solve three important problems in the field: the \emph{exclusive perpetual exploration}, the \emph{exclusive perpetual graph searching} and the \emph{gathering} problems.
In the first problem, each robot aims at visiting each node infinitely often; in perpetual graph searching, the team of robots aims at clearing all edges of the network infinitely often; and in the gathering problem, all robots must eventually occupy the same node.
We investigate these tasks in the famous {\it CORDA} distributed computing model where the robots cannot communicate but can perceive the positions of other robots.
More precisely, each robot is equipped with visibility sensors and motion actuators, and it operates in {\it Look-Compute-Move} asynchronous cycles.
In each cycle, a robot takes a snapshot of the current global configuration (Look), then, based on the perceived configuration, takes a decision to stay idle or to move to one of its adjacent nodes (Compute), and in the latter case it eventually moves to this neighbor (Move).
Moreover, robots are endowed with very weak capabilities.
Namely, they are {\it anonymous}, {\it oblivious}, {\it uniform} (execute the same algorithm) and have {\it no common sense of orientation}.
For the first two problems, the {\it exclusivity constraint} must also be satisfied, i.e., a node can be occupied by at most one robot.
Finally, the robots have the {\it local multiplicity detection capability} which is required to solve the gathering problem.
In this setting, we devise algorithms that, starting from any exclusive rigid (i.e. aperiodic and asymmetric) configuration, solve the three above mentioned problems in anonymous ring-topologies.
Our main algorithms consist of two phases.
The first phase is common to all problems and allows $k>2$ robots to achieve a particular configuration in an $n$-node ring, $k9)$ and $(k=5,n=10)$.}},
url = {http://hal.inria.fr/hal-00716761},
pdf = {http://hal.inria.fr/hal-00716761/PDF/RR-8013.pdf},
x-editorial-board={no},
x-proceedings={no},
x-international-audience={no},
x-pays = {IT,CL},
sorte = "Rapports",
}
-
G. Ducoffe.
Eulerian and Hamiltonian Directed Hypergraphs.
Technical report RR-7893,
INRIA,
2012.
[WWW
] [PDF
]
| Abstract: |
|
Let $H=(\mathcal{V},\mathcal{E})$ be a directed hypergraph, sometimes called a dihypergraph.
Each vertex $v\in{\mathcal{V}}$ is incident to some hyperarcs in $\mathcal{E}$.
Conversely, each hyperarc $E\in{\mathcal{E}}$ is incident to some vertices in $\mathcal{V}$.
$H$ is Eulerian if there is a circuit $C$ such that each hyperarc $E\in{\mathcal{E}}$ appears exactly once in $C$.
Similarly, $H$ is Hamiltonian if there is a circuit $C^{'}$ such that every vertex $v\in{\mathcal{V}}$ appears exactly once in $C^{'}$.
We show that both of the problems are NP-complete.
Some necessary conditions for a dihypergraph to be Eulerian are presented.
We exhibit some families of hypergraphs for which those are sufficient conditions.
We also generalize a part of the properties of the Eulerian digraphs to the uniform and regular directed hypergraphs.
Stronger generalizations of \textit{Eulerianicity} to dihypergraphs are also studied.
Finally, we show that the de Bruijn and Kautz dihypergraphs are Eulerian and Hamiltonian in most cases.
We also study some properties of their bipartite representation digraph. |
@techreport{Duc12,
author = {G. Ducoffe},
title={{E}ulerian and {H}amiltonian Directed Hypergraphs},
year={2012},
institution={INRIA},
number={RR-7893},
abstract={Let $H=(\mathcal{V},\mathcal{E})$ be a directed hypergraph, sometimes called a dihypergraph.
Each vertex $v\in{\mathcal{V}}$ is incident to some hyperarcs in $\mathcal{E}$.
Conversely, each hyperarc $E\in{\mathcal{E}}$ is incident to some vertices in $\mathcal{V}$.
$H$ is Eulerian if there is a circuit $C$ such that each hyperarc $E\in{\mathcal{E}}$ appears exactly once in $C$.
Similarly, $H$ is Hamiltonian if there is a circuit $C^{'}$ such that every vertex $v\in{\mathcal{V}}$ appears exactly once in $C^{'}$.
We show that both of the problems are NP-complete.
Some necessary conditions for a dihypergraph to be Eulerian are presented.
We exhibit some families of hypergraphs for which those are sufficient conditions.
We also generalize a part of the properties of the Eulerian digraphs to the uniform and regular directed hypergraphs.
Stronger generalizations of \textit{Eulerianicity} to dihypergraphs are also studied.
Finally, we show that the de Bruijn and Kautz dihypergraphs are Eulerian and Hamiltonian in most cases.
We also study some properties of their bipartite representation digraph.},
URL={http://hal.inria.fr/hal-00674655},
pdf = {http://hal.inria.fr/docs/00/67/46/55/PDF/RR-7893.pdf},
OPTx-editorial-board={no},
OPTx-proceedings={no},
OPTx-international-audience={no},
x-pays={},
sorte = "Rapports",
}
-
F. Havet,
A. D. King,
M. Liedloff,
and I. Todinca.
(Circular) backbone colouring: tree backbones in planar graphs.
Technical report RR-8152,
INRIA,
November 2012.
[WWW
] [PDF
]
| Abstract: |
|
Consider an undirected graph G and a subgraph H of G, on the same vertex set.
The q-backbone chromatic number BBCq(G,H) is the minimum k such that G can be properly coloured with colours from {1, ..., k}, and moreover for each edge of H, the colours of its ends differ by at least q.
In this paper we focus on the case when G is planar and H is a forest.
We give a series of NP-hardness results as well as upper bounds for BBCq(G,H), depending on the type of the forest (matching, galaxy, spanning tree).
Eventually, we discuss a circular version of the problem. |
@techreport{HKL+12,
author = {Havet, F. and King, A. D. and Liedloff, M. and Todinca, I.},
title = {{(Circular) backbone colouring: tree backbones in planar graphs}},
year = {2012},
month = Nov,
institution = {INRIA},
affiliation = {MASCOTTE - INRIA Sophia Antipolis / Laboratoire I3S , Department of Mathematics , Department of Computer Science , Laboratoire d'Informatique Fondamentale d'Orl{\'e}ans - LIFO},
number = {RR-8152},
language = {Anglais},
abstract = {{Consider an undirected graph G and a subgraph H of G, on the same vertex set.
The q-backbone chromatic number BBCq(G,H) is the minimum k such that G can be properly coloured with colours from {1, ..., k}, and moreover for each edge of H, the colours of its ends differ by at least q.
In this paper we focus on the case when G is planar and H is a forest.
We give a series of NP-hardness results as well as upper bounds for BBCq(G,H), depending on the type of the forest (matching, galaxy, spanning tree).
Eventually, we discuss a circular version of the problem.}},
url = {http://hal.inria.fr/hal-00759044},
pdf = {http://hal.inria.fr/hal-00759044/PDF/RR-8152.pdf},
OPTx-editorial-board={no},
OPTx-proceedings={no},
OPTx-international-audience={no},
x-pays={CA},
sorte = "Rapports",
}
-
F. Havet and A. D. King.
List circular backbone colouring.
Technical report RR-8159,
INRIA,
November 2012.
[WWW
] [PDF
]
| Abstract: |
|
A natural generalization of graph colouring involves taking colours from a metric space and insisting that the endpoints of an edge receive colours separated by a minimum distance dictated by properties of the edge.
In the $q$-backbone colouring problem, these minimum distances are either $q$ or $1$, depending on whether or not the edge is in the {\em backbone}.
In this paper we consider the list version of this problem, with particular focus on colours in $\Z\_p$ -- this problem is closely related to the problem of circular choosability.
We first prove that the {\em list circular $q$-backbone chromatic number} of a graph is bounded by a function of the list chromatic number.
We then consider the more general problem in which each edge is assigned an individual distance between its endpoints, and provide bounds using the Combinatorial Nullstellensatz.
Through this result and through structural approaches, we achieve good bounds when both the graph and the backbone belong to restricted families of graphs. |
@techreport{HaKi12,
author = {Havet, F. and King, A. D.},
title = {{List circular backbone colouring}},
year = {2012},
month = Nov,
institution = {INRIA},
affiliation = {MASCOTTE - INRIA Sophia Antipolis / Laboratoire I3S , Pacific Institute for the Mathematical Sciences - UMI 3069 , Department of Mathematics , Department of Computer Science},
number = {RR-8159},
language = {Anglais},
abstract = {{A natural generalization of graph colouring involves taking colours from a metric space and insisting that the endpoints of an edge receive colours separated by a minimum distance dictated by properties of the edge.
In the $q$-backbone colouring problem, these minimum distances are either $q$ or $1$, depending on whether or not the edge is in the {\em backbone}.
In this paper we consider the list version of this problem, with particular focus on colours in $\Z\_p$ -- this problem is closely related to the problem of circular choosability.
We first prove that the {\em list circular $q$-backbone chromatic number} of a graph is bounded by a function of the list chromatic number.
We then consider the more general problem in which each edge is assigned an individual distance between its endpoints, and provide bounds using the Combinatorial Nullstellensatz.
Through this result and through structural approaches, we achieve good bounds when both the graph and the backbone belong to restricted families of graphs.}},
url = {http://hal.inria.fr/hal-00759527},
pdf = {http://hal.inria.fr/hal-00759527/PDF/RR-8159.pdf},
OPTx-editorial-board={no},
OPTx-proceedings={no},
OPTx-international-audience={no},
x-pays={CA},
sorte = "Rapports",
}
-
F. Havet,
A. K. Maia,
and M-L. Yu.
Complexity of greedy edge-colouring.
Technical report RR-8171,
INRIA,
December 2012.
[WWW
] [PDF
]
| Abstract: |
|
The Grundy index of a graph G = (V,E) is the greatest number of colours that the greedy edge-colouring algorithm can use on G.
We prove that the problem of determining the Grundy index of a graph G = (V,E) is NP-hard for general graphs.
We also show that this problem is polynomial-time solvable for caterpillars.
More specifically, we prove that the Grundy index of a caterpillar is $\Delta(G)$ or $\Delta(G)+1$ and present a polynomial-time algorithm to determine it exactly. |
@techreport{HMY12,
author = {Havet, F. and Maia, A. K. and Yu, M-L.},
title = {{Complexity of greedy edge-colouring}},
year = {2012},
month = Dec,
institution = {INRIA},
affiliation = {MASCOTTE - INRIA Sophia Antipolis / Laboratoire I3S , Department of Maths and Statistics},
number = {RR-8171},
abstract = {{The Grundy index of a graph G = (V,E) is the greatest number of colours that the greedy edge-colouring algorithm can use on G.
We prove that the problem of determining the Grundy index of a graph G = (V,E) is NP-hard for general graphs.
We also show that this problem is polynomial-time solvable for caterpillars.
More specifically, we prove that the Grundy index of a caterpillar is $\Delta(G)$ or $\Delta(G)+1$ and present a polynomial-time algorithm to determine it exactly.}},
url = {http://hal.inria.fr/hal-00762534},
pdf = {http://hal.inria.fr/hal-00762534/PDF/RR-8171.pdf},
OPTx-editorial-board={no},
OPTx-proceedings={no},
OPTx-international-audience={no},
x-pays={CA},
sorte = "Rapports",
}
-
F. Havet,
N. Paramaguru,
and R. Sampathkumar.
Detection number of bipartite graphs and cubic graphs.
Technical report RR-8115,
INRIA,
October 2012.
[WWW
] [PDF
]
| Abstract: |
|
For a connected graph $G$ of order $|V(G)|\,\geq\,3$ and a $k$-labelling $c\,:\,E(G)\,\rightarrow\,\{1,2,\ldots,k\}$ of the edges of $G,$ the {\it code} of a vertex $v$ of $G$ is the ordered $k\!$-tuple $(\ell\_1,\ell\_2,\ldots,\ell\_k),$ where $\ell\_i$ is the number of edges incident with $v$ that are labelled $i.$
The $k$-labelling $c$ is {\it detectable} if every two adjacent vertices of $G$ have distinct codes.
The minimum positive integer $k$ for which $G$ has a detectable $k$-labelling is the {\it detection number} of $G.$
In this paper, we show that it is NP-complete to decide if the detection number of a cubic graph is $2.$
We also show that the detection number of every bipartite graph of minimum degree at least $3$ is at most $2.$
Finally, we give some sufficient condition for a cubic graph to have detection number $3.$ |
@techreport{HPS12,
author = {Havet, F. and Paramaguru, N. and Sampathkumar, R.},
title = {{Detection number of bipartite graphs and cubic graphs}},
year = {2012},
month = Oct,
institution = {INRIA},
affiliation = {MASCOTTE - INRIA Sophia Antipolis / Laboratoire I3S , Mathematics Wing, Directorate of Distance Education, Mathematics Section, Faculty of Engineering and Technology},
number = {RR-8115},
hal_id = {hal-00744365},
language = {Anglais},
abstract = {{For a connected graph $G$ of order $|V(G)|\,\geq\,3$ and a $k$-labelling $c\,:\,E(G)\,\rightarrow\,\{1,2,\ldots,k\}$ of the edges of $G,$ the {\it code} of a vertex $v$ of $G$ is the ordered $k\!$-tuple $(\ell\_1,\ell\_2,\ldots,\ell\_k),$ where $\ell\_i$ is the number of edges incident with $v$ that are labelled $i.$
The $k$-labelling $c$ is {\it detectable} if every two adjacent vertices of $G$ have distinct codes.
The minimum positive integer $k$ for which $G$ has a detectable $k$-labelling is the {\it detection number} of $G.$
In this paper, we show that it is NP-complete to decide if the detection number of a cubic graph is $2.$
We also show that the detection number of every bipartite graph of minimum degree at least $3$ is at most $2.$
Finally, we give some sufficient condition for a cubic graph to have detection number $3.$}},
url = {http://hal.inria.fr/hal-00744365},
pdf = {http://hal.inria.fr/hal-00744365/PDF/RR-8115.pdf},
OPTx-editorial-board={no},
OPTx-proceedings={no},
OPTx-international-audience={no},
x-pays={IN},
sorte = "Rapports",
}
-
A. Kosowski,
B. Li,
N. Nisse,
and K. Suchan.
k-Chordal Graphs: from Cops and Robber to Compact Routing via Treewidth.
Technical report RR-7888,
INRIA,
February 2012.
[WWW
] [PDF
]
| Abstract: |
|
{\it Cops and robber games} concern a team of cops that must capture a robber moving in a graph.
We consider the class of $k$-chordal graphs, i.e., graphs with no induced cycle of length greater than $k$, $k\geq 3$.
We prove that $k-1$ cops are always sufficient to capture a robber in $k$-chordal graphs.
This leads us to our main result, a new structural decomposition for a graph class including $k$-chordal graphs.
We present a quadratic algorithm that, given a graph $G$ and $k\geq 3$, either returns an induced cycle larger than $k$ in $G$, or computes a {\it tree-decomposition} of $G$, each {\it bag} of which contains a dominating path with at most $k-1$ vertices.
This allows us to prove that any $k$-chordal graph with maximum degree $\Delta$ has treewidth at most $(k-1)(\Delta-1)+2$, improving the $O(\Delta (\Delta-1)^{k-3})$ bound of Bodlaender and Thilikos (1997).
Moreover, any graph admitting such a tree-decomposition has hyperbolicity $\leq\lfloor \frac{3}{2}k\rfloor$. As an application, for any $n$-node graph admitting such a tree-decomposition, we propose a {\it compact routing scheme} using routing tables, addresses and headers of size $O(\log n)$ bits and achieving an additive stretch of $O(k\log \Delta)$.
As far as we know, this is the first routing scheme with $O(\log n)$-routing tables and small additive stretch for $k$-chordal graphs. |
@techreport{KLN+12a,
author = {A. Kosowski and B. Li and N. Nisse and K. Suchan},
title ={k-Chordal Graphs: from Cops and Robber to Compact Routing via Treewidth},
url = {http://hal.inria.fr/hal-00671861},
pdf ={http://hal.archives-ouvertes.fr/docs/00/67/18/97/PDF/RR-7888.pdf},
institution = {INRIA},
number = {RR-7888},
year = {2012},
month = feb,
abstract = {{\it Cops and robber games} concern a team of cops that must capture a robber moving in a graph.
We consider the class of $k$-chordal graphs, i.e., graphs with no induced cycle of length greater than $k$, $k\geq 3$.
We prove that $k-1$ cops are always sufficient to capture a robber in $k$-chordal graphs.
This leads us to our main result, a new structural decomposition for a graph class including $k$-chordal graphs.
We present a quadratic algorithm that, given a graph $G$ and $k\geq 3$, either returns an induced cycle larger than $k$ in $G$, or computes a {\it tree-decomposition} of $G$, each {\it bag} of which contains a dominating path with at most $k-1$ vertices.
This allows us to prove that any $k$-chordal graph with maximum degree $\Delta$ has treewidth at most $(k-1)(\Delta-1)+2$, improving the $O(\Delta (\Delta-1)^{k-3})$ bound of Bodlaender and Thilikos (1997).
Moreover, any graph admitting such a tree-decomposition has hyperbolicity $\leq\lfloor \frac{3}{2}k\rfloor$. As an application, for any $n$-node graph admitting such a tree-decomposition, we propose a {\it compact routing scheme} using routing tables, addresses and headers of size $O(\log n)$ bits and achieving an additive stretch of $O(k\log \Delta)$.
As far as we know, this is the first routing scheme with $O(\log n)$-routing tables and small additive stretch for $k$-chordal graphs.},
x-editorial-board={no},
x-proceedings={no},
x-international-audience={no},
x-pays = {CL},
sorte = "Rapports",
}
-
N. Nisse and R. Soares.
On The Monotonicity of Process Number.
Technical report RR-7003,
INRIA,
October 2012.
[WWW
] [PDF
]
| Abstract: |
|
Graph searching games involve a team of searchers that aims at capturing a fugitive in a graph.
These games have been widely studied for their relationships with tree- and path-decomposition of graphs.
In order to define decompositions for directed graphs, similar games have been proposed in directed graphs.
In this paper, we consider such a game that has been defined and studied in the context of routing reconfiguration problems in WDM networks.
Namely, in the processing game, the fugitive is invisible, arbitrary fast, it moves in the opposite direction of the arcs of a digraph, but only as long as it has access to a strongly connected component free of searchers.
We prove that the processing game is monotone which leads to its equivalence with a new digraph decomposition. |
@techreport{NiSo12,
author = {Nisse, N. and Soares, R.},
title = {{On The Monotonicity of Process Number}},
institution = {INRIA},
affiliation = {MASCOTTE - INRIA Sophia Antipolis / Laboratoire I3S},
number = {RR-7003},
year = {2012},
month = Oct,
language = {Anglais},
pages = {17},
abstract = {{Graph searching games involve a team of searchers that aims at capturing a fugitive in a graph.
These games have been widely studied for their relationships with tree- and path-decomposition of graphs.
In order to define decompositions for directed graphs, similar games have been proposed in directed graphs.
In this paper, we consider such a game that has been defined and studied in the context of routing reconfiguration problems in WDM networks.
Namely, in the processing game, the fugitive is invisible, arbitrary fast, it moves in the opposite direction of the arcs of a digraph, but only as long as it has access to a strongly connected component free of searchers.
We prove that the processing game is monotone which leads to its equivalence with a new digraph decomposition.}},
hal_id = {hal-00745587},
url = {http://hal.inria.fr/hal-00745587},
pdf = {http://hal.inria.fr/hal-00745587/PDF/RRProcessNumberMonotone.pdf},
OPTx-editorial-board={no},
OPTx-proceedings={no},
OPTx-international-audience={no},
x-pays = {BR},
sorte = "Rapports",
}
