-
G. D'Angelo,
G. Di Stefano,
and A. Navarra.
Gathering asynchronous and oblivious robots on basic graph topologies under the Look -Compute-Move model.
In Steve Alpern,
Robbert Fokkink,
Leszek Gasieniec,
Roy Lindelauf,
and VS Subrahmanian, editors,Search Games and Rendezvous.
Springer,
.
Note: Volume dedicated to the Workshop on Search and Rendezvous that took place in May 2012 in Lorentz Centre. To appear. [WWW
] [PDF
]
| Abstract: |
Recent and challenging models of robot-based computing systems consider identical, oblivious and mobile robots placed on the nodes of anonymous graphs. Robots operate asynchronously in order to reach a common node and remain with it. This task is known in the literature as the athering or rendezvous problem. The target node is neither chosen in advance nor marked differently compared to the other nodes. In fact, the graph is anonymous and robots have minimal capabilities. In the context of robot-based computing systems, resources are always limited and precious. Then, the research of the minimal set of assumptions and capabilities required to accomplish the gathering task as well as for other achievements is of main interest. Moreover, the minimality of the assumptions stimulates the investigation of new and challenging techniques that might reveal crucial peculiarities even for other tasks. The model considered in this chapter is known in the literature as the Look-Compute-Move model. Identical robots initially placed at different nodes of an anonymous input graph operate in asynchronous Look-Compute-Move 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 makes an instantaneous move to this neighbor (Move). Cycles are performed asynchronously for each robot. This means that the time between Look, Compute, and Move operations is finite but unbounded, and it is decided by the adversary for each robot. Hence, robots may move based on significantly outdated perceptions. The only constraint is that moves are instantaneous, and hence any robot performing a Look operation perceives all other robots at nodes of the ring and not on edges. Robots are all identical, anonymous, and execute the same deterministic algorithm. They cannot leave any marks at visited nodes, nor can they send messages to other robots. In this chapter, we aim to survey on recent results obtained for the gathering task over basic graph topologies, that are rings, grids, and trees. Recent achievements to this matter have attracted many researchers, and have provided interesting approaches that might be of main interest to the community that studies robot-based computing systems. |
@incollection{DDN+12d,
author = {D'Angelo, G. and Di Stefano, G. and Navarra, A.},
title = {{Gathering asynchronous and oblivious robots on basic graph topologies under the Look -Compute-Move model}},
booktitle = {{Search Games and Rendezvous}},
publisher = {Springer},
editor = {Steve Alpern and Robbert Fokkink and Leszek Gasieniec and Roy Lindelauf and VS Subrahmanian },
year = {},
month =,
note = {Volume dedicated to the Workshop on Search and Rendezvous that took place in May 2012 in Lorentz Centre. To appear.},
abstract = {{Recent and challenging models of robot-based computing systems consider identical, oblivious and mobile robots placed on the nodes of anonymous graphs. Robots operate asynchronously in order to reach a common node and remain with it. This task is known in the literature as the athering or rendezvous problem. The target node is neither chosen in advance nor marked differently compared to the other nodes. In fact, the graph is anonymous and robots have minimal capabilities. In the context of robot-based computing systems, resources are always limited and precious. Then, the research of the minimal set of assumptions and capabilities required to accomplish the gathering task as well as for other achievements is of main interest. Moreover, the minimality of the assumptions stimulates the investigation of new and challenging techniques that might reveal crucial peculiarities even for other tasks. The model considered in this chapter is known in the literature as the Look-Compute-Move model. Identical robots initially placed at different nodes of an anonymous input graph operate in asynchronous Look-Compute-Move 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 makes an instantaneous move to this neighbor (Move). Cycles are performed asynchronously for each robot. This means that the time between Look, Compute, and Move operations is finite but unbounded, and it is decided by the adversary for each robot. Hence, robots may move based on significantly outdated perceptions. The only constraint is that moves are instantaneous, and hence any robot performing a Look operation perceives all other robots at nodes of the ring and not on edges. Robots are all identical, anonymous, and execute the same deterministic algorithm. They cannot leave any marks at visited nodes, nor can they send messages to other robots. In this chapter, we aim to survey on recent results obtained for the gathering task over basic graph topologies, that are rings, grids, and trees. Recent achievements to this matter have attracted many researchers, and have provided interesting approaches that might be of main interest to the community that studies robot-based computing systems.}},
url = { http://hal.inria.fr/hal-00755407 },
pdf = { http://hal.inria.fr/hal-00755407/PDF/main.pdf },
x-pays = {IT},
OPTx-editorial-board={yes},
OPTx-proceedings={no},
OPTx-international-audience={yes},
sorte = "livres-chap",
}
-
S. Bessy and F. Havet.
Enumerating the edge-colourings and total colourings of a regular graph.
Journal of Combinatorial Optimization,
.
Note: To appear.
[PDF
]
| Abstract: |
In this paper, we are interested in computing the number of edge colourings and total colourings of a graph. We prove that the maximum number of $k$-edge-colourings of a $k$-regular graph on $n$ vertices is $k\cdot(k-1!)^{n/2}$. Our proof is constructible and leads to a branching algorithm enumerating all the $k$-edge-colourings of a $k$-regular graph using a time $O^*((k-1!)^{n/2})$ and polynomial space. In particular, we obtain a algorithm on time $O^*(2^{n/2})=O^*(1.4143^n)$ and polynomial space to enumerate all the $3$-edge colourings of a cubic graph, improving the running time of $O^*(1.5423^n)$ of the algorithm due to Golovach et al.\~\cite{GKC10}. We also show that the number of $4$-total-colourings of a connected cubic graph is at most $3.2^{3n/2}$. Again, our proof yields a branching algorithm to enumerate all the $4$-total-colourings of a connected cubic graph. |
@article{BeHa,
title = {{Enumerating the edge-colourings and total colourings of a regular graph}},
author = {S. Bessy and F. Havet},
journal = "Journal of Combinatorial Optimization",
note = "to appear",
volume = "",
abstract = {{In this paper, we are interested in computing the number of edge colourings and total colourings of a graph. We prove that the maximum number of $k$-edge-colourings of a $k$-regular graph on $n$ vertices is $k\cdot(k-1!)^{n/2}$. Our proof is constructible and leads to a branching algorithm enumerating all the $k$-edge-colourings of a $k$-regular graph using a time $O^*((k-1!)^{n/2})$ and polynomial space. In particular, we obtain a algorithm on time $O^*(2^{n/2})=O^*(1.4143^n)$ and polynomial space to enumerate all the $3$-edge colourings of a cubic graph, improving the running time of $O^*(1.5423^n)$ of the algorithm due to Golovach et al.\~\cite{GKC10}. We also show that the number of $4$-total-colourings of a connected cubic graph is at most $3.2^{3n/2}$. Again, our proof yields a branching algorithm to enumerate all the $4$-total-colourings of a connected cubic graph.}},
pdf = {http://hal.inria.fr/inria-00602188/PDF/RR-7652.pdf},
x-editorial-board={yes},
x-proceedings={yes},
x-international-audience={yes},
x-pays={},
}
-
S. Caron,
F. Giroire,
D. Mazauric,
J. Monteiro,
and S. Pérennes.
P2P Storage Systems: Study of Different Placement Policies.
ELSEVIER Journal of Peer-to-Peer Networking and Applications, Springer,
.
Note: To appear.
[PDF
]
| Abstract: |
In a P2P storage system using erasure codes, a data block is encoded in many redundancy fragments. These fragments are then sent to distinct peers of the network. In this work, we study the impact of different placement policies of these fragments on the performance of storage systems. Several practical factors (easier control, software reuse, latency) tend to favor data placement strategies that preserve some degree of locality. We compare three policies: two of them are {\em local}, in which the data are stored in logical neighbors, and the other one, {\em global}, in which the data are spread randomly in the whole system. We focus on the study of the probability to lose a data block and the bandwidth consumption to maintain such redundancy. We use simulations to show that, without resource constraints, the average values are the same no matter which placement policy is used. However, the variations in the use of bandwidth are much more bursty under the {\em local} policies. When the bandwidth is limited, these bursty variations induce longer maintenance time and henceforth a higher risk of data loss. We then show that a suitable degree of locality could be introduced in order to combine the efficiency of the global policy with the practical advantages of a local placement. Additionally, we propose a new {\em external reconstruction} strategy that greatly improves the performance of local placement strategies. Finally, we give analytical methods to estimate the mean time to the occurrence of data loss for the three policies. |
@article{CGM+13,
author = {Caron, S. and Giroire, F. and Mazauric, D. and Monteiro, J. and P\'erennes, S.},
title = {P2P Storage Systems: Study of Different Placement Policies},
journal = {ELSEVIER Journal of Peer-to-Peer Networking and Applications, Springer},
year = {},
OPTvolume = {},
OPTnumber = {},
OPTpages = {},
note = {To appear},
abstract = {In a P2P storage system using erasure codes, a data block is encoded in many redundancy fragments. These fragments are then sent to distinct peers of the network. In this work, we study the impact of different placement policies of these fragments on the performance of storage systems. Several practical factors (easier control, software reuse, latency) tend to favor data placement strategies that preserve some degree of locality. We compare three policies: two of them are {\em local}, in which the data are stored in logical neighbors, and the other one, {\em global}, in which the data are spread randomly in the whole system. We focus on the study of the probability to lose a data block and the bandwidth consumption to maintain such redundancy. We use simulations to show that, without resource constraints, the average values are the same no matter which placement policy is used. However, the variations in the use of bandwidth are much more bursty under the {\em local} policies. When the bandwidth is limited, these bursty variations induce longer maintenance time and henceforth a higher risk of data loss. We then show that a suitable degree of locality could be introduced in order to combine the efficiency of the global policy with the practical advantages of a local placement. Additionally, we propose a new {\em external reconstruction} strategy that greatly improves the performance of local placement strategies. Finally, we give analytical methods to estimate the mean time to the occurrence of data loss for the three policies.},
pdf = {ftp://ftp-sop.inria.fr/coati/Publications/CGM+13.pdf},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
x-pays = {US, BR},
sorte = "rev-int",
}
-
S. Cicerone,
G. D'Angelo,
G. Di Stefano,
D. Frigioni,
and V. Maurizio.
Engineering a new algorithm for distributed shortest paths on dynamic networks.
Algorithmica,
.
Note: To appear.
[WWW
] [PDF
]
| Abstract: |
We study the problem of dynamically updatingall-pairs shortest paths in a distributed network while edge update operations occur to the network. We consider the practical case of a dynamic network in which an edge update can occur while one or more other edge updates are under processing. A node of the network might be affected by a subset of these changes, thus being involved in the concurrent executions related to such changes. In this paper, we provide a new algorithm for this problem, and experimentally compare its performance with respect to those of the most popular solutions in the literature: the classical distributed Bellman-Ford method, which is still used in real network and implemented in the RIP protocol, and DUAL, the Diffuse Update ALgorithm, which is part of CISCO's widely used EIGRP protocol. As input to the algorithms, we used both real-world and artificial instances of the problem. The experiments performed show that the space occupancy per node required by the new algorithm is smaller than that required by both Bellman-Ford and DUAL. In terms of messages, the new algorithm outperforms both Bellman-Ford and DUAL on the real-world topologies, while on artificial instances, the new algorithm sends a number of messages that is more than that of DUAL and much smaller than that of Bellman-Ford. |
@article{CDD+12,
title = {{Engineering a new algorithm for distributed shortest paths on dynamic networks}},
author = {Cicerone, S. and D'Angelo, G. and Di Stefano, G. and Frigioni, D. and Maurizio, V.},
journal = {Algorithmica},
year = {},
note = {to appear},
volume = {},
number = {},
pages = {},
publisher = {Springer},
abstract = {{We study the problem of dynamically updatingall-pairs shortest paths in a distributed network while edge update operations occur to the network. We consider the practical case of a dynamic network in which an edge update can occur while one or more other edge updates are under processing. A node of the network might be affected by a subset of these changes, thus being involved in the concurrent executions related to such changes. In this paper, we provide a new algorithm for this problem, and experimentally compare its performance with respect to those of the most popular solutions in the literature: the classical distributed Bellman-Ford method, which is still used in real network and implemented in the RIP protocol, and DUAL, the Diffuse Update ALgorithm, which is part of CISCO's widely used EIGRP protocol. As input to the algorithms, we used both real-world and artificial instances of the problem. The experiments performed show that the space occupancy per node required by the new algorithm is smaller than that required by both Bellman-Ford and DUAL. In terms of messages, the new algorithm outperforms both Bellman-Ford and DUAL on the real-world topologies, while on artificial instances, the new algorithm sends a number of messages that is more than that of DUAL and much smaller than that of Bellman-Ford.}},
doi = {10.1007/s00453-012-9623-9},
url = {http://hal.inria.fr/hal-00728876},
pdf = {http://hal.inria.fr/hal-00728876/PDF/main.pdf},
OPTx-editorial-board={yes},
OPTx-proceedings={no},
OPTx-international-audience={yes},
x-pays = {IT},
sorte = "rev-int",
}
-
G. D'Angelo,
G. Di Stefano,
and A. Navarra.
Flow problems in multi-interface networks.
IEEE Transactions on Computers,
.
Note: To appear.
[WWW
] [PDF
]
| Abstract: |
In heterogeneous networks, devices communicate by means of multiple wired or wireless interfaces. By switching among interfaces or by combining the available ones, each device might establish several connections. A connection may be established when the devices at its endpoints share at least one active interface. In this paper, we consider two fundamental optimization problems. In the first one (Maximum Flow in Multi-Interface Networks MFMI), we aim to establish the maximal bandwidth that can be guaranteed between two given nodes of the input network. In the second problem (Minimum-Cost Flow in Multi-Interface Networks MCFMI), we look for activating the cheapest set of interfaces among a network in order to guarantee a minimum bandwidth B of communication between two specified nodes. We show that MFMI is polynomially solvable while MCFMI is NP-hard even for a bounded number of different interfaces and bounded degree networks. Moreover, we provide polynomial approximation algorithms for MCFMI and exact algorithms for relevant sub-problems. Finally, we experimentally analyze the proposed approximation algorithm, showing that in practical cases it guarantees a low approximation ratio. |
@article{DDN12,
author = {D'Angelo, G. and Di Stefano, G. and Navarra, A.},
title = {{Flow problems in multi-interface networks}},
journal = {IEEE Transactions on Computers},
year = {},
note = {to appear},
volume = {},
number = {},
pages = {},
abstract = {{In heterogeneous networks, devices communicate by means of multiple wired or wireless interfaces. By switching among interfaces or by combining the available ones, each device might establish several connections. A connection may be established when the devices at its endpoints share at least one active interface. In this paper, we consider two fundamental optimization problems. In the first one (Maximum Flow in Multi-Interface Networks MFMI), we aim to establish the maximal bandwidth that can be guaranteed between two given nodes of the input network. In the second problem (Minimum-Cost Flow in Multi-Interface Networks MCFMI), we look for activating the cheapest set of interfaces among a network in order to guarantee a minimum bandwidth B of communication between two specified nodes. We show that MFMI is polynomially solvable while MCFMI is NP-hard even for a bounded number of different interfaces and bounded degree networks. Moreover, we provide polynomial approximation algorithms for MCFMI and exact algorithms for relevant sub-problems. Finally, we experimentally analyze the proposed approximation algorithm, showing that in practical cases it guarantees a low approximation ratio.}},
url = {http://hal.inria.fr/hal-00728878},
pdf = {http://hal.inria.fr/hal-00728878/PDF/main.pdf},
OPTx-editorial-board={yes},
OPTx-proceedings={no},
OPTx-international-audience={yes},
x-pays = {IT},
sorte = "rev-int",
}
-
W. Fang,
X. Liang,
S. Li,
L. Chiaraviglio,
and N. Xiong.
VMPlanner: Optimizing Virtual Machine Placement and Traffic Flow Routing to Reduce Network Power Costs in Cloud Data Centers.
Computer Networks,
September.
Note: To appear.
[PDF
]
| Abstract: |
In recent years, the power costs of cloud data centers have become a practical concern and have attracted significant attention from both industry and academia. Most of the early works on data center energy efficiency have focused on the biggest power consumers (i.e., computer servers and cooling systems), yet without taking the networking part into consideration. However, recent studies have revealed that the network elements consume 10-20\27775643230f the total power in the data center, which poses a great challenge to effectively reducing network power cost without adversely affecting overall network performance. Based on the analysis on topology characteristics and traffic patterns of data centers, this paper presents a novel approach, called VMPlanner, for network power reduction in the virtualization-based data centers. The basic idea of VMPlanner is to optimize both virtual machine placement and traffic flow routing so as to turn off as many unneeded network elements as possible for power saving. We formulate the optimization problem, analyze its hardness, and solve it by designing VMPlanner as a stepwise optimization approach with three approximation algorithms. VMPlanner is implemented and evaluated in a simulated environment with traffic traces collected from a data center test-bed, and the experiment results illustrate the efficacy and efficiency of this approach. |
@article{FLL+12,
author = {Fang, W. and Liang, X. and Li, S. and Chiaraviglio, L. and Xiong, N.},
title = {{VMPlanner: Optimizing Virtual Machine Placement and Traffic Flow Routing to Reduce Network Power Costs in Cloud Data Centers}},
abstract = {{In recent years, the power costs of cloud data centers have become a practical concern and have attracted significant attention from both industry and academia. Most of the early works on data center energy efficiency have focused on the biggest power consumers (i.e., computer servers and cooling systems), yet without taking the networking part into consideration. However, recent studies have revealed that the network elements consume 10-20\27775643230f the total power in the data center, which poses a great challenge to effectively reducing network power cost without adversely affecting overall network performance. Based on the analysis on topology characteristics and traffic patterns of data centers, this paper presents a novel approach, called VMPlanner, for network power reduction in the virtualization-based data centers. The basic idea of VMPlanner is to optimize both virtual machine placement and traffic flow routing so as to turn off as many unneeded network elements as possible for power saving. We formulate the optimization problem, analyze its hardness, and solve it by designing VMPlanner as a stepwise optimization approach with three approximation algorithms. VMPlanner is implemented and evaluated in a simulated environment with traffic traces collected from a data center test-bed, and the experiment results illustrate the efficacy and efficiency of this approach.}},
publisher = {Elsevier},
journal = {Computer Networks},
year = {},
month = Sep,
note = {To appear},
pdf={http://www.telematica.polito.it/oldsite/chiaraviglio/papers/VMPlanner.pdf},
x-pays={CN,IT},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
sorte = "inv-conf"
}
-
F. Havet and L. Sampaio.
On the Grundy and $b$-chromatic Numbers of a Graph.
Algorithmica,
pp 1-15,
.
Note: To appear.
@article{HaSa11,
author = {Havet, F. and Sampaio, L.},
title = {On the Grundy and $b$-chromatic Numbers of a Graph},
journal = {Algorithmica},
publisher = {Springer New York},
note = {To appear},
year = {},
pages = {1-15},
doi = {10.1007/s00453-011-9604-4},
x-editorial-board={yes},
x-proceedings={no},
x-international-audience={yes},
x-pays={BR},
sorte = "rev-int",
}
-
F. Havet and X. Zhu.
The game Grundy number of graphs.
Journal of Combinatorial Optimization,
.
Note: To appear.
[WWW
] [PDF
]
Keywords:
colouring game,
game Grundy number,
trees,
partial 2-trees.
| Abstract: |
Given a graph G = (V;E), two players, Alice and Bob, alternate their turns in choosing uncoloured vertices to be coloured. Whenever an uncoloured vertex is chosen, it is coloured by the least positive integer not used by any of its coloured neighbours. Alice's goal is to minimize the total number of colours used in the game, and Bob's goal is to maximize it. The game Grundy number of G is the number of colours used in the game when both players use optimal strategies. It is proved in this paper that the maximum game Grundy number of forests is 3, and the game Grundy number of any partial 2-tree is at most 7. |
@article{HaZh,
title = {{The game Grundy number of graphs}},
author = {Havet, F. and Zhu, X.},
JOURNAL = "Journal of Combinatorial Optimization",
VOLUME = "",
note = {To appear},
abstract = {{Given a graph G = (V;E), two players, Alice and Bob, alternate their turns in choosing uncoloured vertices to be coloured. Whenever an uncoloured vertex is chosen, it is coloured by the least positive integer not used by any of its coloured neighbours. Alice's goal is to minimize the total number of colours used in the game, and Bob's goal is to maximize it. The game Grundy number of G is the number of colours used in the game when both players use optimal strategies. It is proved in this paper that the maximum game Grundy number of forests is 3, and the game Grundy number of any partial 2-tree is at most 7.}},
keywords = {colouring game, game Grundy number, trees, partial 2-trees},
language = {Anglais},
affiliation = {MASCOTTE - INRIA Sophia Antipolis / Laboratoire I3S - INRIA - Universit\'e de Nice Sophia-Antipolis - CNRS : UMR6070 - Department of Mathematics - Zhejiang Normal University},
url = {http://hal.inria.fr/inria-00600738},
pdf = {http://hal.inria.fr/inria-00600738/PDF/RR-7646.pdf},
x-editorial-board={yes},
x-proceedings={no},
x-international-audience={yes},
x-pays={CN},
sorte = "rev-int",
}
-
G. D'Angelo,
G. Di Stefano,
A. Navarra,
N. Nisse,
and N. Suchan.
A unified approach for different tasks on rings in robot-based computing systems.
In 15th Workshop on Advances in Parallel and Distributed Computational Models (APDCM),
.
IEEE.
Note: To appear.
[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 exclusive perpetual exploration, the exclusive perpetual graph searching and the 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 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 Look-Compute-Move asynchronous cycles. Moreover, robots are anonymous, oblivious, uniform and have no common sense of orientation. For the first two problems, the exclusivity constraint must also be satisfied, i.e., a node can be occupied by at most one robot. 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. Besides being a unified approach for three different tasks, the given algorithms solve some open problems. Moreover, we provide some impossibility results for the perpetual graph searching problem. |
@inproceedings{ASN+13,
author = {D'Angelo, G. and Di Stefano, G. and Navarra, A. and Nisse, N. and Suchan, N.},
title = {A unified approach for different tasks on rings in robot-based computing systems},
booktitle = {15th Workshop on Advances in Parallel and Distributed Computational Models (APDCM)},
publisher = {IEEE},
year = {},
note = {To appear},
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 exclusive perpetual exploration, the exclusive perpetual graph searching and the 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 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 Look-Compute-Move asynchronous cycles. Moreover, robots are anonymous, oblivious, uniform and have no common sense of orientation. For the first two problems, the exclusivity constraint must also be satisfied, i.e., a node can be occupied by at most one robot. 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. Besides being a unified approach for three different tasks, the given algorithms solve some open problems. Moreover, we provide some impossibility results for the perpetual graph searching problem.},
url = {http://hal.inria.fr/hal-00716761},
pdf ={http://hal.inria.fr/docs/00/71/67/61/PDF/RR-8013.pdf},
x-editorial-board={yes},
x-proceedings={yes},
x-international-audience={yes},
x-pays = {CL,IT},
sorte = "conf-int",
}
-
N. Nisse and R. Soares.
On The Monotonicity of Process Number.
In proceedings of the Latin-American Algorithms, Graphs and Optimization Symposium (LAGOS'13),
Electronic Notes in Discrete Mathematics,
Playa del Carmen, Mexico,
April.
[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. |
@inproceedings{NiSo13,
author = {Nisse, N. and Soares, R.},
title = {On The Monotonicity of Process Number},
booktitle = {proceedings of the Latin-American Algorithms, Graphs and Optimization Symposium (LAGOS'13)},
year = {},
month = apr,
series = {Electronic Notes in Discrete Mathematics},
address = {Playa del Carmen, Mexico},
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.},
pdf = {http://hal.inria.fr/hal-00745587/PDF/RRProcessNumberMonotone.pdf},
OPTx-editorial-board={yes},
OPTx-proceedings={yes},
OPTx-international-audience={yes},
x-pays={BR},
sorte = {conf-int},
}