-
Deepesh Agarwal,
Christelle Caillouet,
David Coudert,
and Frédéric Cazals.
Unveiling Contacts within Macro-molecular assemblies by solving Minimum Weight Connectivity Inference Problems.
Molecular and Cellular Proteomics,
14:2274-2284,
April 2015.
[WWW
] [PDF
]
Keywords:
Biophysics,
Bioinformatics,
Mathematical Modeling,
connectivity inference,
Algorithms,
Mass Spectrometry,
Structural Biology.
| Abstract: |
|
Consider a set of oligomers listing the subunits involved in sub-complexes of a macro-molecular assembly, obtained e.g. using native mass spectrometry or affinity purification. Given these oligomers, connectivity inference (CI) consists of finding the most plausible contacts between these subunits, and minimum connectivity inference (MCI) is the variant consisting of finding a set of contacts of smallest cardinality. MCI problems avoid speculating on the total number of contacts, but yield a subset of all contacts and do not allow exploiting a priori information on the likelihood of individual contacts. In this context, we present two novel algorithms, MILP-W and MILP-WB. The former solves the minimum weight connectivity inference (MWCI), an optimization problem whose criterion mixes the number of contacts and their likelihood. The latter uses the former in a bootstrap fashion, to improve the sensitivity and the specificity of solution sets. Experiments on three systems (yeast exosome, yeast proteasome lid, human eiF3), for which reference contacts are known (crystal structure, cryo electron microscopy, cross-linking), show that our algorithms predict contacts with high specificity and sensitivity, yielding a very significant improvement over previous work, typically a twofold increase in sensitivity. The software accompanying this paper is made available, and should prove of ubiquitous interest whenever connectivity inference from oligomers is faced. |
@article{agarwal:hal-01245401,
TITLE = {{Unveiling Contacts within Macro-molecular assemblies by solving Minimum Weight Connectivity Inference Problems}},
AUTHOR = {Agarwal, Deepesh and Caillouet, Christelle and Coudert, David and Cazals, Fr{\'e}d{\'e}ric},
URL = {https://hal.inria.fr/hal-01245401},
JOURNAL = {{Molecular and Cellular Proteomics}},
PUBLISHER = {{American Society for Biochemistry and Molecular Biology}},
VOLUME = {14},
PAGES = {2274-2284},
YEAR = {2015},
MONTH = Apr,
DOI = {10.1074/mcp.M114.047779},
ABSTRACT = {Consider a set of oligomers listing the subunits involved in sub-complexes of a macro-molecular assembly, obtained e.g. using native mass spectrometry or affinity purification. Given these oligomers, connectivity inference (CI) consists of finding the most plausible contacts between these subunits, and minimum connectivity inference (MCI) is the variant consisting of finding a set of contacts of smallest cardinality. MCI problems avoid speculating on the total number of contacts, but yield a subset of all contacts and do not allow exploiting a priori information on the likelihood of individual contacts. In this context, we present two novel algorithms, MILP-W and MILP-WB. The former solves the minimum weight connectivity inference (MWCI), an optimization problem whose criterion mixes the number of contacts and their likelihood. The latter uses the former in a bootstrap fashion, to improve the sensitivity and the specificity of solution sets. Experiments on three systems (yeast exosome, yeast proteasome lid, human eiF3), for which reference contacts are known (crystal structure, cryo electron microscopy, cross-linking), show that our algorithms predict contacts with high specificity and sensitivity, yielding a very significant improvement over previous work, typically a twofold increase in sensitivity. The software accompanying this paper is made available, and should prove of ubiquitous interest whenever connectivity inference from oligomers is faced.},
KEYWORDS = {Biophysics ; Bioinformatics ; Mathematical Modeling ; connectivity inference ; Algorithms ; Mass Spectrometry ; Structural Biology},
PDF = {https://hal.inria.fr/hal-01245401/file/mwci.pdf},
HAL_ID = {hal-01245401},
HAL_VERSION = {v2},
}
-
Omid Amini,
David Coudert,
and Nicolas Nisse.
Non-deterministic graph searching in trees.
Journal of Theoretical Computer Science (TCS),
580:101-121,
May 2015.
[WWW
] [PDF
]
Keywords:
Pathwidth,
Trees,
Graph Searching,
Treewidth.
| Abstract: |
|
Non-deterministic graph searching was introduced by Fomin et al. to provide a unified approach for pathwidth, treewidth, and their interpretations in terms of graph searching games. Given q $\ge$ 0, the q-limited search number, s q (G), of a graph G is the smallest number of searchers required to capture an invisible fugitive in G, when the searchers are allowed to know the position of the fugitive at most q times. The search parameter s 0 (G) corresponds to the pathwidth of a graph G, and s $\infty$ (G) to its treewidth. Determining s q (G) is NP-complete for any fixed q $\ge$ 0 in general graphs and s 0 (T) can be computed in linear time in trees, however the complexity of the problem on trees has been unknown for any q \textgreater{} 0. We introduce a new variant of graph searching called restricted non-deterministic. The corresponding parameter is denoted by rs q and is shown to be equal to the non-deterministic graph searching parameter s q for q = 0, 1, and at most twice s q for any q $\ge$ 2 (for any graph G). Our main result is a polynomial time algorithm that computes rs q (T) for any tree T and any q $\ge$ 0. This provides a 2-approximation of s q (T) for any tree T , and shows that the decision problem associated to s 1 is polynomial in the class of trees. Our proofs are based on a new decomposition technique for trees which might be of independent interest. |
@article{amini:hal-01132032,
TITLE = {{Non-deterministic graph searching in trees}},
AUTHOR = {Amini, Omid and Coudert, David and Nisse, Nicolas},
URL = {https://hal.inria.fr/hal-01132032},
JOURNAL = {{Journal of Theoretical Computer Science (TCS)}},
PUBLISHER = {{Elsevier}},
VOLUME = {580},
PAGES = {101-121},
YEAR = {2015},
MONTH = May,
DOI = {10.1016/j.tcs.2015.02.038},
ABSTRACT = {Non-deterministic graph searching was introduced by Fomin et al. to provide a unified approach for pathwidth, treewidth, and their interpretations in terms of graph searching games. Given q $\ge$ 0, the q-limited search number, s q (G), of a graph G is the smallest number of searchers required to capture an invisible fugitive in G, when the searchers are allowed to know the position of the fugitive at most q times. The search parameter s 0 (G) corresponds to the pathwidth of a graph G, and s $\infty$ (G) to its treewidth. Determining s q (G) is NP-complete for any fixed q $\ge$ 0 in general graphs and s 0 (T) can be computed in linear time in trees, however the complexity of the problem on trees has been unknown for any q \textgreater{} 0. We introduce a new variant of graph searching called restricted non-deterministic. The corresponding parameter is denoted by rs q and is shown to be equal to the non-deterministic graph searching parameter s q for q = 0, 1, and at most twice s q for any q $\ge$ 2 (for any graph G). Our main result is a polynomial time algorithm that computes rs q (T) for any tree T and any q $\ge$ 0. This provides a 2-approximation of s q (T) for any tree T , and shows that the decision problem associated to s 1 is polynomial in the class of trees. Our proofs are based on a new decomposition technique for trees which might be of independent interest.},
KEYWORDS = {Pathwidth ; Trees ; Graph Searching ; Treewidth},
PDF = {https://hal.inria.fr/hal-01132032/file/ACN15.pdf},
HAL_ID = {hal-01132032},
HAL_VERSION = {v1},
}
-
Julio Araujo,
Nathann Cohen,
Susanna F. De Rezende,
Frédéric Havet,
and Phablo Moura.
On the proper orientation number of bipartite graphs.
Journal of Theoretical Computer Science (TCS),
566:59-75,
February 2015.
[WWW
]
| Abstract: |
|
An {\it orientation} of a graph $G$ is a digraph $D$ obtained from $G$ by replacing each edge by exactly one of the twopossible arcs with the same endvertices.For each $v \in V(G)$, the \emph{indegree} of $v$ in $D$, denoted by $d^-\_D(v)$, is the number of arcs with head $v$ in $D$.An orientation $D$ of $G$ is \emph{proper} if $d^-\_D(u)\neq d^-\_D(v)$, for all $uv\in E(G)$.The \emph{proper orientation number} of a graph $G$, denoted by $po(G)$, is the minimum of the maximumindegree over all its proper orientations. In this paper, we prove that $po(G) \leq \left(\Delta(G) + \sqrt{\Delta(G)}\right)/2 + 1$ if $G$ is a bipartite graph, and $po(G)\leq 4$ if $G$ is a tree.% Moreover, we show that deciding whether the proper orientation number is at most~2 and at most~3 0s an $NP$-complete problem for planar subcubic graphs and planar bipartite graphs, respectively. It is well-known that $po(G)\leq \Delta(G)$, for every graph $G$.However, we prove that deciding whether $po(G)\leq \Delta(G)-1$ is already an $NP$-complete problem on graphs with $\Delta(G) = k$, for every $k \geq 3$.We also show that it is $NP$-complete to decide whether $po(G)\leq 2$, for planar \emph{subcubic} graphs $G$. Moreover, we prove that it is $NP$-complete to decide whether $po(G)\leq 3$, for planar bipartite graphs $G$ with maximum degree 5. |
@article{araujo:hal-01101578,
TITLE = {{On the proper orientation number of bipartite graphs}},
AUTHOR = {Araujo, Julio and Cohen, Nathann and De Rezende, Susanna F. and Havet, Fr{\'e}d{\'e}ric and Moura, Phablo},
URL = {https://hal.archives-ouvertes.fr/hal-01101578},
JOURNAL = {{Journal of Theoretical Computer Science (TCS)}},
PUBLISHER = {{Elsevier}},
VOLUME = {566},
PAGES = {59-75},
YEAR = {2015},
MONTH = Feb,
DOI = {10.1016/j.tcs.2014.11.037},
ABSTRACT = {An {\it orientation} of a graph $G$ is a digraph $D$ obtained from $G$ by replacing each edge by exactly one of the twopossible arcs with the same endvertices.For each $v \in V(G)$, the \emph{indegree} of $v$ in $D$, denoted by $d^-\_D(v)$, is the number of arcs with head $v$ in $D$.An orientation $D$ of $G$ is \emph{proper} if $d^-\_D(u)\neq d^-\_D(v)$, for all $uv\in E(G)$.The \emph{proper orientation number} of a graph $G$, denoted by $po(G)$, is the minimum of the maximumindegree over all its proper orientations. In this paper, we prove that $po(G) \leq \left(\Delta(G) + \sqrt{\Delta(G)}\right)/2 + 1$ if $G$ is a bipartite graph, and $po(G)\leq 4$ if $G$ is a tree.% Moreover, we show that deciding whether the proper orientation number is at most~2 and at most~3 0s an $NP$-complete problem for planar subcubic graphs and planar bipartite graphs, respectively. It is well-known that $po(G)\leq \Delta(G)$, for every graph $G$.However, we prove that deciding whether $po(G)\leq \Delta(G)-1$ is already an $NP$-complete problem on graphs with $\Delta(G) = k$, for every $k \geq 3$.We also show that it is $NP$-complete to decide whether $po(G)\leq 2$, for planar \emph{subcubic} graphs $G$. Moreover, we prove that it is $NP$-complete to decide whether $po(G)\leq 3$, for planar bipartite graphs $G$ with maximum degree 5.},
HAL_ID = {hal-01101578},
HAL_VERSION = {v1},
}
-
Julio Araujo,
Frédéric Havet,
and Mathieu Schmitt.
Steinberg-like theorems for backbone colouring.
Electronic Notes in Discrete Mathematics,
pp 223-229,
December 2015.
[WWW
] [PDF
]
Keywords:
Graph Colouring,
Planar Graph,
Backbone Colouring,
Steinberg's Conjecture.
| Abstract: |
|
A function f:V(G)$\rightarrow${1,â¦,k}f:V(G)$\rightarrow${1,â¦,k} is a (proper) k-colouring of G if |f(u)--f(v)|$\ge$1|f(u)--f(v)|$\ge$1, for every edge uv$\in$E(G)uv$\in$E(G). The chromatic number $\chi$(G)$\chi$(G) is the smallest integer k for which there exists a proper k-colouring of G.Given a graph G and a subgraph H of G, a circular q-backbone k-colouring c of (G, H) is a k-colouring of G such that q$\le$|c(u)--c(v)|$\le$k--qq$\le$|c(u)--c(v)|$\le$k--q, for each edge uv$\in$E(H)uv$\in$E(H). The circular q-backbone chromatic number of a graph pair (G, H ), denoted CBCq(G,H)CBCq(G,H), is the minimum k such that (G, H) admits a circular q-backbone k-colouring.In this work, we first show that if G is a planar graph containing no cycle on 4 or 5 vertices and H$\subseteq$GH$\subseteq$G is a forest, then CBC2(G,H)$\le$7CBC2(G,H)$\le$7. Then, we prove that if H$\subseteq$GH$\subseteq$G is a forest whose connected components are paths, then CBC2(G,H)$\le$6CBC2(G,H)$\le$6. |
@article{araujo:hal-01246205,
TITLE = {{Steinberg-like theorems for backbone colouring}},
AUTHOR = {Araujo, Julio and Havet, Fr{\'e}d{\'e}ric and Schmitt, Mathieu},
URL = {https://hal.inria.fr/hal-01246205},
JOURNAL = {{Electronic Notes in Discrete Mathematics}},
PUBLISHER = {{Elsevier}},
SERIES = {LAGOS'15 -- VIII Latin-American Algorithms, Graphs and Optimization Symposium},
PAGES = {223-229},
YEAR = {2015},
MONTH = Dec,
ABSTRACT = {A function f:V(G)$\rightarrow${1,â¦,k}f:V(G)$\rightarrow${1,â¦,k} is a (proper) k-colouring of G if |f(u)--f(v)|$\ge$1|f(u)--f(v)|$\ge$1, for every edge uv$\in$E(G)uv$\in$E(G). The chromatic number $\chi$(G)$\chi$(G) is the smallest integer k for which there exists a proper k-colouring of G.Given a graph G and a subgraph H of G, a circular q-backbone k-colouring c of (G, H) is a k-colouring of G such that q$\le$|c(u)--c(v)|$\le$k--qq$\le$|c(u)--c(v)|$\le$k--q, for each edge uv$\in$E(H)uv$\in$E(H). The circular q-backbone chromatic number of a graph pair (G, H ), denoted CBCq(G,H)CBCq(G,H), is the minimum k such that (G, H) admits a circular q-backbone k-colouring.In this work, we first show that if G is a planar graph containing no cycle on 4 or 5 vertices and H$\subseteq$GH$\subseteq$G is a forest, then CBC2(G,H)$\le$7CBC2(G,H)$\le$7. Then, we prove that if H$\subseteq$GH$\subseteq$G is a forest whose connected components are paths, then CBC2(G,H)$\le$6CBC2(G,H)$\le$6.},
KEYWORDS = { Graph Colouring ; Planar Graph ; Backbone Colouring ; Steinberg's Conjecture},
PDF = {https://hal.inria.fr/hal-01246205/file/backbone-steinberg-dam.pdf},
HAL_ID = {hal-01246205},
HAL_VERSION = {v1},
}
-
Jorgen Bang-Jensen,
Frédéric Havet,
and Ana Karolinna MAIA DE OLIVEIRA.
Finding a subdivision of a digraph.
Theoretical Computer Science,
562:20,
2015.
[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. |
@article{bangjensen:hal-01111374,
TITLE = {{Finding a subdivision of a digraph}},
AUTHOR = {Bang-Jensen, J{{\o}}rgen and Havet, Fr{\'e}d{\'e}ric and MAIA DE OLIVEIRA, Ana Karolinna},
URL = {https://hal.inria.fr/hal-01111374},
JOURNAL = {{Theoretical Computer Science}},
PUBLISHER = {{Elsevier}},
VOLUME = {562},
PAGES = {20},
YEAR = {2015},
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.},
PDF = {https://hal.inria.fr/hal-01111374/file/subdivision.pdf},
HAL_ID = {hal-01111374},
HAL_VERSION = {v1},
}
-
Florent Becker,
Adrian Kosowski,
Martin Matamala,
Nicolas Nisse,
Ivan Rapaport,
Karol Suchan,
and Ioan Todinca.
Allowing each node to communicate only once in a distributed system: shared whiteboard models.
Distributed Computing,
28(3):189-200,
2015.
[WWW
] [PDF
]
| Abstract: |
|
In this paper we study distributed algorithms on massive graphs where links represent a particular relationship between nodes (for instance, nodes may represent phone numbers and links may indicate telephone calls). Since such graphs are massive they need to be processed in a distributed way. When computing graph-theoretic properties, nodes become natural units for distributed computation. Links do not necessarily represent communication channels between the computing units and therefore do not restrict the communication flow. Our goal is to model and analyze the computational power of such distributed systems where one computing unit is assigned to each node. Communication takes place on a whiteboard where each node is allowed to write at most one message. Every node can read the contents of the whiteboard and, when activated, can write one small message based on its local knowledge. When the protocol terminates its output is computed from the final contents of the whiteboard. We describe four synchronization models for accessing the whiteboard. We show that message size and synchronization power constitute two orthogonal hierarchies for these systems.We exhibit problems that separate these models, i.e., that can be solved in one model but not in a weaker one, even with increased message size. These problems are related to maximal independent set and connectivity. We also exhibit problems that require a given message size independently of the synchronization model. |
@article{becker:hal-01163186,
TITLE = {{Allowing each node to communicate only once in a distributed system: shared whiteboard models}},
AUTHOR = {Becker, Florent and Kosowski, Adrian and Matamala, Martin and Nisse, Nicolas and Rapaport, Ivan and Suchan, Karol and Todinca, Ioan},
URL = {https://hal.inria.fr/hal-01163186},
JOURNAL = {{Distributed Computing}},
PUBLISHER = {{Springer Verlag}},
VOLUME = {28},
NUMBER = {3},
PAGES = {189-200},
YEAR = {2015},
DOI = {10.1007/s00446-014-0221-8},
ABSTRACT = {In this paper we study distributed algorithms on massive graphs where links represent a particular relationship between nodes (for instance, nodes may represent phone numbers and links may indicate telephone calls). Since such graphs are massive they need to be processed in a distributed way. When computing graph-theoretic properties, nodes become natural units for distributed computation. Links do not necessarily represent communication channels between the computing units and therefore do not restrict the communication flow. Our goal is to model and analyze the computational power of such distributed systems where one computing unit is assigned to each node. Communication takes place on a whiteboard where each node is allowed to write at most one message. Every node can read the contents of the whiteboard and, when activated, can write one small message based on its local knowledge. When the protocol terminates its output is computed from the final contents of the whiteboard. We describe four synchronization models for accessing the whiteboard. We show that message size and synchronization power constitute two orthogonal hierarchies for these systems.We exhibit problems that separate these models, i.e., that can be solved in one model but not in a weaker one, even with increased message size. These problems are related to maximal independent set and connectivity. We also exhibit problems that require a given message size independently of the synchronization model.},
PDF = {https://hal.inria.fr/hal-01163186/file/article%20-vHAL.pdf},
HAL_ID = {hal-01163186},
HAL_VERSION = {v1},
}
-
Jean-Claude Bermond,
David Coudert,
Gianlorenzo D 'angelo,
and Fatima Zahra Moataz.
Finding disjoint paths in networks with star shared risk link groups.
Journal of Theoretical Computer Science (TCS),
579:74-87,
May 2015.
[WWW
] [PDF
]
Keywords:
Diverse routing,
Shared Risk Link Group,
Complexity,
Algorithms,
Disjoint paths,
Colored graph.
| Abstract: |
|
The notion of Shared Risk Link Groups (SRLG) has been introduced to capture surviv-ability issues where some links of a network fail simultaneously. In this context, the k-diverse routing problem is to find a set of k pairwise SRLG-disjoint paths between a given pair of end nodes of the network. This problem has been proven NP-complete in general and some polynomial instances have been characterized. In this paper, we investigate the k-diverse routing problem in networks where the SRLGs are localized and satisfy the star property. This property states that a link may be subject to several SRLGs, but all links subject to a given SRLG are incident to a common node. We first provide counterexamples to the polynomial time algorithm proposed by X. Luo and B. Wang (DRCN'05) for computing a pair of SRLG-disjoint paths in networks with SRLGs satisfying the star property, and then prove that this problem is in fact NP-complete. We then characterize instances that can be solved in polynomial time or are fixed parameter tractable, in particular when the number of SRLGs is constant, the maximum degree of the vertices is at most 4, and when the network is a directed acyclic graph. Finally we consider the problem of finding the maximum number of SRLG-disjoint paths in networks with SRLGs satisfying the star property. We prove that this problem is NP-hard to approximate within O(|V | 1--$\epsilon$) for any 0 \textless{} $\epsilon$ \textless{} 1, where V is the set of nodes in the network. Then, we provide exact and approximation algorithms for relevant subcases. |
@article{bermond:hal-01132216,
TITLE = {{Finding disjoint paths in networks with star shared risk link groups}},
AUTHOR = {Bermond, Jean-Claude and Coudert, David and D 'angelo, Gianlorenzo and Zahra Moataz, Fatima},
URL = {https://hal.inria.fr/hal-01132216},
JOURNAL = {{Journal of Theoretical Computer Science (TCS)}},
PUBLISHER = {{Elsevier}},
VOLUME = {579},
PAGES = {74-87},
YEAR = {2015},
MONTH = May,
DOI = {10.1016/j.tcs.2015.02.012},
ABSTRACT = {The notion of Shared Risk Link Groups (SRLG) has been introduced to capture surviv-ability issues where some links of a network fail simultaneously. In this context, the k-diverse routing problem is to find a set of k pairwise SRLG-disjoint paths between a given pair of end nodes of the network. This problem has been proven NP-complete in general and some polynomial instances have been characterized. In this paper, we investigate the k-diverse routing problem in networks where the SRLGs are localized and satisfy the star property. This property states that a link may be subject to several SRLGs, but all links subject to a given SRLG are incident to a common node. We first provide counterexamples to the polynomial time algorithm proposed by X. Luo and B. Wang (DRCN'05) for computing a pair of SRLG-disjoint paths in networks with SRLGs satisfying the star property, and then prove that this problem is in fact NP-complete. We then characterize instances that can be solved in polynomial time or are fixed parameter tractable, in particular when the number of SRLGs is constant, the maximum degree of the vertices is at most 4, and when the network is a directed acyclic graph. Finally we consider the problem of finding the maximum number of SRLG-disjoint paths in networks with SRLGs satisfying the star property. We prove that this problem is NP-hard to approximate within O(|V | 1--$\epsilon$) for any 0 \textless{} $\epsilon$ \textless{} 1, where V is the set of nodes in the network. Then, we provide exact and approximation algorithms for relevant subcases.},
KEYWORDS = {Diverse routing ; Shared Risk Link Group ; Complexity ; Algorithms ; Disjoint paths ; Colored graph},
PDF = {https://hal.inria.fr/hal-01132216/file/BCDM15.pdf},
HAL_ID = {hal-01132216},
HAL_VERSION = {v1},
}
-
Jean-Claude Bermond,
Bi Li,
Nicolas Nisse,
Hervé Rivano,
and Min-Li Yu.
Data gathering and personalized broadcasting in radio grids with interference.
Journal of Theoretical Computer Science (TCS),
562:453-475,
2015.
[WWW
] [PDF
]
Keywords:
Gathering,
Personalized broadcasting,
Interference,
Grid,
Radio networks.
| Abstract: |
|
In the gathering problem, a particular node in a graph, the base station , aims at receiving messages from some nodes in the graph. At each step, a node can send one message to one of its neighbors (such an action is called a call ). However, a node cannot send and receive a message during the same step. Moreover, the communication is subject to interference constraints, more precisely, two calls interfere in a step, if one sender is at distance at most dI from the other receiver. Given a graph with a base station and a set of nodes having some messages, the goal of the gathering problem is to compute a schedule of calls for the base station to receive all messages as fast as possible, i.e., minimizing the number of steps (called makespan). The gathering problem is equivalent to the personalized broadcasting problem where the base station has to send messages to some nodes in the graph, with same transmission constraints.In this paper, we focus on the gathering and personalized broadcasting problem in grids. Moreover, we consider the non-buffering model: when a node receives a message at some step, it must transmit it during the next step. In this setting, though the problem of determining the complexity of computing the optimal makespan in a grid is still open, we present linear (in the number of messages) algorithms that compute schedules for gathering with dI$\in${0,1,2}. In particular, we present an algorithm that achieves the optimal makespan up to an additive constant 2 when dI=0. If no messages are "close" to the axes (the base station being the origin), our algorithms achieve the optimal makespan up to an additive constant 1 when dI=0, 4 when dI=2, and 3 when both dI=1 and the base station is in a corner. Note that, the approximation algorithms that we present also provide approximation up to a ratio 2 for the gathering with buffering. All our results are proved in terms of personalized broadcasting. |
@article{bermond:hal-01084996,
TITLE = {{Data gathering and personalized broadcasting in radio grids with interference}},
AUTHOR = {Bermond, Jean-Claude and Li, Bi and Nisse, Nicolas and Rivano, Herv{\'e} and Yu, Min-Li},
URL = {https://hal.inria.fr/hal-01084996},
JOURNAL = {{Journal of Theoretical Computer Science (TCS)}},
PUBLISHER = {{Elsevier}},
VOLUME = {562},
PAGES = {453-475},
YEAR = {2015},
DOI = {10.1016/j.tcs.2014.10.029},
ABSTRACT = {In the gathering problem, a particular node in a graph, the base station , aims at receiving messages from some nodes in the graph. At each step, a node can send one message to one of its neighbors (such an action is called a call ). However, a node cannot send and receive a message during the same step. Moreover, the communication is subject to interference constraints, more precisely, two calls interfere in a step, if one sender is at distance at most dI from the other receiver. Given a graph with a base station and a set of nodes having some messages, the goal of the gathering problem is to compute a schedule of calls for the base station to receive all messages as fast as possible, i.e., minimizing the number of steps (called makespan). The gathering problem is equivalent to the personalized broadcasting problem where the base station has to send messages to some nodes in the graph, with same transmission constraints.In this paper, we focus on the gathering and personalized broadcasting problem in grids. Moreover, we consider the non-buffering model: when a node receives a message at some step, it must transmit it during the next step. In this setting, though the problem of determining the complexity of computing the optimal makespan in a grid is still open, we present linear (in the number of messages) algorithms that compute schedules for gathering with dI$\in${0,1,2}. In particular, we present an algorithm that achieves the optimal makespan up to an additive constant 2 when dI=0. If no messages are "close" to the axes (the base station being the origin), our algorithms achieve the optimal makespan up to an additive constant 1 when dI=0, 4 when dI=2, and 3 when both dI=1 and the base station is in a corner. Note that, the approximation algorithms that we present also provide approximation up to a ratio 2 for the gathering with buffering. All our results are proved in terms of personalized broadcasting.},
KEYWORDS = {Gathering ; Personalized broadcasting ; Interference ; Grid ; Radio networks},
PDF = {https://hal.inria.fr/hal-01084996/file/tcs_bermond_li_nisse_rivano_yu.pdf},
HAL_ID = {hal-01084996},
HAL_VERSION = {v1},
}
-
Nathann Cohen,
David Coudert,
and Aurélien Lancin.
On computing the Gromov hyperbolicity.
ACM Journal on Experimental Algorithmics,
20(1):18,
2015.
[WWW
] [PDF
]
Keywords:
Algorithms,
Gromov Hyperbolicity,
Networks.
| Abstract: |
|
The Gromov hyperbolicity is an important parameter for analyzing complex networks which expresses how the metric structure of a network looks like a tree. It is for instance used to provide bounds on the expected stretch of greedy-routing algorithms in Internet-like graphs. However, the best known theoretical algorithm computing this parameter runs in O(n^3.69) time, which is prohibitive for large-scale graphs. In this paper, we propose an algorithm for determining the hyperbolicity of graphs with tens of thousands of nodes. Its running time depends on the distribution of distances and on the actual value of the hyperbolicity. Although its worst case runtime is O(n^4), it is in practice much faster than previous proposals as observed in our experimentations. Finally, we propose a heuristic algorithm that can be used on graphs with millions of nodes. Our algorithms are all evaluated on benchmark instances. |
@article{cohen:hal-01182890,
TITLE = {{On computing the Gromov hyperbolicity}},
AUTHOR = {Cohen, Nathann and Coudert, David and Lancin, Aur{\'e}lien},
URL = {https://hal.inria.fr/hal-01182890},
JOURNAL = {{ACM Journal on Experimental Algorithmics}},
PUBLISHER = {{Association for Computing Machinery}},
VOLUME = {20},
NUMBER = {1},
PAGES = {18},
YEAR = {2015},
DOI = {10.1145/2780652},
ABSTRACT = {The Gromov hyperbolicity is an important parameter for analyzing complex networks which expresses how the metric structure of a network looks like a tree. It is for instance used to provide bounds on the expected stretch of greedy-routing algorithms in Internet-like graphs. However, the best known theoretical algorithm computing this parameter runs in O(n^3.69) time, which is prohibitive for large-scale graphs. In this paper, we propose an algorithm for determining the hyperbolicity of graphs with tens of thousands of nodes. Its running time depends on the distribution of distances and on the actual value of the hyperbolicity. Although its worst case runtime is O(n^4), it is in practice much faster than previous proposals as observed in our experimentations. Finally, we propose a heuristic algorithm that can be used on graphs with millions of nodes. Our algorithms are all evaluated on benchmark instances.},
KEYWORDS = {Algorithms ; Gromov Hyperbolicity ; Networks},
PDF = {https://hal.inria.fr/hal-01182890/file/CCL15-no-format.pdf},
HAL_ID = {hal-01182890},
HAL_VERSION = {v1},
}
-
David Coudert,
Alvinice Kodjo,
and Truong Khoa Phan.
Robust Energy-aware Routing with Redundancy Elimination.
Computers and Operations Research,
64:21,
December 2015.
[WWW
] [PDF
]
Keywords:
Robust Network Optimization,
Green Networking,
Energy-aware Routing,
Redundancy Elimination.
| Abstract: |
|
Many studies in literature have shown that energy-aware routing (EAR) can significantly reduce energy consumption for backbone networks. Also, as an arising concern in networking research area, the protocol-independent traffic redundancy elimination (RE) technique helps to reduce (a.k.a compress) traffic load on backbone network. Motivation from a formulation perspective, we first present an extended model of the classical multi-commodity flow problem with compressible flows. Moreover, our model is robust with fluctuation of traffic demand and compression rate. In details, we allow any set of a predefined size of traffic flows to deviate simultaneously from their nominal volumes or compression rates. As an applicable example, we use this model to combine redundancy elimination and energy-aware routing to increase energy efficiency for a backbone network. Using this extra knowledge on the dynamics of the traffic pattern, we are able to significantly increase energy efficiency for the network. We formally define the problem and model it as a Mixed Integer Linear Program (MILP). We then propose an efficient heuristic algorithm that is suitable for large networks. Simulation results with real traffic traces on Abilene, Geant and Germany50 networks show that our approach allows for 16-28 5.243879e-267xtra energy saving with respect to the classical EAR model. |
@article{coudert:hal-01155639,
TITLE = {{Robust Energy-aware Routing with Redundancy Elimination}},
AUTHOR = {Coudert, David and Kodjo, Alvinice and Phan, Truong Khoa},
URL = {https://hal.inria.fr/hal-01155639},
JOURNAL = {{Computers and Operations Research}},
VOLUME = {64},
PAGES = {21},
YEAR = {2015},
MONTH = Dec,
DOI = {10.1016/j.cor.2015.05.008},
ABSTRACT = {Many studies in literature have shown that energy-aware routing (EAR) can significantly reduce energy consumption for backbone networks. Also, as an arising concern in networking research area, the protocol-independent traffic redundancy elimination (RE) technique helps to reduce (a.k.a compress) traffic load on backbone network. Motivation from a formulation perspective, we first present an extended model of the classical multi-commodity flow problem with compressible flows. Moreover, our model is robust with fluctuation of traffic demand and compression rate. In details, we allow any set of a predefined size of traffic flows to deviate simultaneously from their nominal volumes or compression rates. As an applicable example, we use this model to combine redundancy elimination and energy-aware routing to increase energy efficiency for a backbone network. Using this extra knowledge on the dynamics of the traffic pattern, we are able to significantly increase energy efficiency for the network. We formally define the problem and model it as a Mixed Integer Linear Program (MILP). We then propose an efficient heuristic algorithm that is suitable for large networks. Simulation results with real traffic traces on Abilene, Geant and Germany50 networks show that our approach allows for 16-28 5.243879e-267xtra energy saving with respect to the classical EAR model.},
KEYWORDS = {Robust Network Optimization ; Green Networking ; Energy-aware Routing ; Redundancy Elimination},
PDF = {https://hal.inria.fr/hal-01155639/file/CKP15.pdf},
HAL_ID = {hal-01155639},
HAL_VERSION = {v1},
}
-
Gianlorenzo d'Angelo,
Gabriele Di Stefano,
Alfredo Navarra,
Nicolas Nisse,
and Karol Suchan.
Computing on rings by oblivious robots: a unified approach for different tasks.
Algorithmica,
72(4):1055-1096,
2015.
[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 (that is, the ring is anonymous). We present a unified approach to solve three important problems: the exclusive perpetual exploration, the exclusive perpetual clearing, and the gathering problems. In the first problem, each robot aims at visiting each node infinitely often while avoiding that two robots occupy a same node (exclusivity property); in exclusive perpetual clearing (also known as searching), the team of robots aims at clearing the whole ring infinitely often (an edge is cleared if it is traversed by a robot or if both its endpoints are occupied); and in the gathering problem, all robots must eventually occupy the same node. We investigate these tasks in the Look-Compute-Move model where the robots cannot communicate but can perceive the positions of other robots. Each robot is equipped with visibility sensors and motion actuators, and it operates in 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 anonymous, asynchronous, oblivious, uniform (execute the same algorithm) and have no common sense of orientation. In this setting, we devise algorithms that, starting from an exclusive and rigid (i.e. aperiodic and asymmetric) configuration, solve the three above problems in anonymous ring-topologies. |
@article{dangelo:hal-01168428,
TITLE = {{Computing on rings by oblivious robots: a unified approach for different tasks}},
AUTHOR = {d'Angelo, Gianlorenzo and Di Stefano, Gabriele and Navarra, Alfredo and Nisse, Nicolas and Suchan, Karol},
URL = {https://hal.inria.fr/hal-01168428},
JOURNAL = {{Algorithmica}},
PUBLISHER = {{Springer Verlag}},
VOLUME = {72},
NUMBER = {4},
PAGES = {1055-1096},
YEAR = {2015},
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 (that is, the ring is anonymous). We present a unified approach to solve three important problems: the exclusive perpetual exploration, the exclusive perpetual clearing, and the gathering problems. In the first problem, each robot aims at visiting each node infinitely often while avoiding that two robots occupy a same node (exclusivity property); in exclusive perpetual clearing (also known as searching), the team of robots aims at clearing the whole ring infinitely often (an edge is cleared if it is traversed by a robot or if both its endpoints are occupied); and in the gathering problem, all robots must eventually occupy the same node. We investigate these tasks in the Look-Compute-Move model where the robots cannot communicate but can perceive the positions of other robots. Each robot is equipped with visibility sensors and motion actuators, and it operates in 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 anonymous, asynchronous, oblivious, uniform (execute the same algorithm) and have no common sense of orientation. In this setting, we devise algorithms that, starting from an exclusive and rigid (i.e. aperiodic and asymmetric) configuration, solve the three above problems in anonymous ring-topologies.},
PDF = {https://hal.inria.fr/hal-01168428/file/ring-asym-journal.pdf},
HAL_ID = {hal-01168428},
HAL_VERSION = {v1},
}
-
Olivier Delmas,
Frédéric Havet,
and Mickaël Montassier.
Design of fault-tolerant on-board networks with variable switch sizes.
Theoretical Computer Science,
562:15,
2015.
[WWW
]
| Abstract: |
|
An \emph{$(n,k,r)$-network} is a triple $N=(G,\inp,\outp)$ where $G=(V,E)$is a graph and $\inp,\outp$ are non-negative integer functions defined on $V$ calledthe \emph{input} and \emph{output} functions, such that for any $v \in V$,$\inp(v)+\outp(v)+ \degree(v)\leq 2r$ where $\degree(v)$ is the degree of $v$ in thegraph $G$. The total number of inputs is $\inp(V)=\sum\_{v\in V}\inp(v)=n$, and the total number of outputs is $\outp(V)=\sum\_{v\in V}\outp(v)=n+k$.An $(n,k,r)$-network is \emph{valid}, if for any \emph{faulty} outputfunction $\outp'$ (that is such that $0\leq \outp'(v) \leq \outp(v)$ for any $v\in V$, and $\outp'(V) = n$), there are $n$ edge-disjoint paths in $G$such that each vertex $v\in V$ is the initial vertex of $\inp(v)$ pathsand the terminal vertex of $\outp'(v)$ paths.We investigate the design problem of determining the minimum number ${\cal N}(n,k,r)$ ofvertices in a valid $(n,k,r)$-network and of constructing minimum$(n,k,r)$-networks, or at least valid $(n,k,r)$-networks with a numberof vertices close to the optimal value.We first give some upper bounds on ${\cal N}(n,k,r)$.We show ${\cal N}(n,k,r)\leq \left\lceil \frac{k+2}{2r-2}\right\rceil \left\lceil\frac{n}{2}\right\rceil$. When $r\geq k/2$, we prove a better upper bound: ${\cal N}(n,k,r) \leq \frac{r-2+k/2}{r^2-2r+k/2} n + O(1)$.Next, we establish some lower bounds. We show that if $k\geq r$, then${\cal N}(n,k,r) \geq \frac{3n+k}{2r}$. We improve this bound when $k\geq 2r$:$\displaystyle {\cal N}(n,k,r) \geq \formule$.Finally, we determine ${\cal N}(n,k,r)$ up to additive constants for $k\leq 6$. |
@article{delmas:hal-01111370,
TITLE = {{Design of fault-tolerant on-board networks with variable switch sizes}},
AUTHOR = {Delmas, Olivier and Havet, Fr{\'e}d{\'e}ric and Montassier, Micka{\"e}l},
URL = {https://hal.inria.fr/hal-01111370},
JOURNAL = {{Theoretical Computer Science}},
PUBLISHER = {{Elsevier}},
VOLUME = {562},
PAGES = {15},
YEAR = {2015},
ABSTRACT = {An \emph{$(n,k,r)$-network} is a triple $N=(G,\inp,\outp)$ where $G=(V,E)$is a graph and $\inp,\outp$ are non-negative integer functions defined on $V$ calledthe \emph{input} and \emph{output} functions, such that for any $v \in V$,$\inp(v)+\outp(v)+ \degree(v)\leq 2r$ where $\degree(v)$ is the degree of $v$ in thegraph $G$. The total number of inputs is $\inp(V)=\sum\_{v\in V}\inp(v)=n$, and the total number of outputs is $\outp(V)=\sum\_{v\in V}\outp(v)=n+k$.An $(n,k,r)$-network is \emph{valid}, if for any \emph{faulty} outputfunction $\outp'$ (that is such that $0\leq \outp'(v) \leq \outp(v)$ for any $v\in V$, and $\outp'(V) = n$), there are $n$ edge-disjoint paths in $G$such that each vertex $v\in V$ is the initial vertex of $\inp(v)$ pathsand the terminal vertex of $\outp'(v)$ paths.We investigate the design problem of determining the minimum number ${\cal N}(n,k,r)$ ofvertices in a valid $(n,k,r)$-network and of constructing minimum$(n,k,r)$-networks, or at least valid $(n,k,r)$-networks with a numberof vertices close to the optimal value.We first give some upper bounds on ${\cal N}(n,k,r)$.We show ${\cal N}(n,k,r)\leq \left\lceil \frac{k+2}{2r-2}\right\rceil \left\lceil\frac{n}{2}\right\rceil$. When $r\geq k/2$, we prove a better upper bound: ${\cal N}(n,k,r) \leq \frac{r-2+k/2}{r^2-2r+k/2} n + O(1)$.Next, we establish some lower bounds. We show that if $k\geq r$, then${\cal N}(n,k,r) \geq \frac{3n+k}{2r}$. We improve this bound when $k\geq 2r$:$\displaystyle {\cal N}(n,k,r) \geq \formule$.Finally, we determine ${\cal N}(n,k,r)$ up to additive constants for $k\leq 6$.},
HAL_ID = {hal-01111370},
HAL_VERSION = {v1},
}
-
Frédéric Giroire,
Ioannis Lamprou,
Dorian Mazauric,
Nicolas Nisse,
Stéphane Pérennes,
and Ronan Soares.
Connected Surveillance Game.
Journal of Theoretical Computer Science (TCS),
584:131-143,
June 2015.
[WWW
] [PDF
]
Keywords:
Surveillance game,
Cops and robber games,
Prefetching,
Online strategy,
Competitive ratio,
Cost of connectivity.
| Abstract: |
|
The surveillance game [Fomin et al., 2012] models the problem of web-page prefetching as a pursuit evasion game played on a graph. This two-player game is played turn-by-turn. The first player, called the observer, can mark a fixed amount of vertices at each turn. The second one controls a surfer that stands at vertices of the graph and can slide along edges. The surfer starts at some initially marked vertex of the graph, its objective is to reach an unmarked node before all nodes of the graph are marked. The surveillance number sn(G) of a graph G is the minimum amount of nodes that the observer has to mark at each turn ensuring it wins against any surfer in G. Fomin et al. also defined the connected surveillance game where the observer must ensure that marked nodes always induce a connected subgraph. They ask what is the cost of connectivity, i.e., is there a constant c \textgreater{} 0 such that the ratio between the connected surveillance number csn(G) and sn(G) is at most c for any graph G. It is straightforward to show that csn(G) $\le$ â sn(G) for any graph G with maximum degree â. Moreover, it has been shown that there are graphs G for which csn(G) = sn(G) + 1. In this paper, we investigate the question of the cost of the connectivity. We first provide new non-trivial upper and lower bounds for the cost of connectivity in the surveillance game. More precisely, we present a family of graphs G such that csn(G) \textgreater{} sn(G) + 1. Moreover, we prove that csn(G) $\le$ sn(G)n for any n-node graph G. While the gap between these bounds remains huge, it seems difficult to reduce it. We then define the online surveillance game where the observer has no a priori knowledge of the graph topology and discovers it little-by-little. This variant, which fits better the prefetching motivation, is a restriction of the connected variant. Unfortunately, we show that no algorithm for solving the online surveillance game has competitive ratio better than â¦(â). That is, while interesting, this variant does not help to obtain better upper bounds for the connected variant. We finally answer an open question [Fomin et al., 2012] by proving that deciding if the surveillance number of a digraph with maximum degree 6 is at most 2 is NP-hard. |
@article{giroire:hal-01163170,
TITLE = {{Connected Surveillance Game}},
AUTHOR = {Giroire, Fr{\'e}d{\'e}ric and Lamprou, Ioannis and Mazauric, Dorian and Nisse, Nicolas and P{\'e}rennes, St{\'e}phane and Soares, Ronan},
URL = {https://hal.inria.fr/hal-01163170},
JOURNAL = {{Journal of Theoretical Computer Science (TCS)}},
PUBLISHER = {{Elsevier}},
VOLUME = {584},
PAGES = {131-143},
YEAR = {2015},
MONTH = Jun,
ABSTRACT = {The surveillance game [Fomin et al., 2012] models the problem of web-page prefetching as a pursuit evasion game played on a graph. This two-player game is played turn-by-turn. The first player, called the observer, can mark a fixed amount of vertices at each turn. The second one controls a surfer that stands at vertices of the graph and can slide along edges. The surfer starts at some initially marked vertex of the graph, its objective is to reach an unmarked node before all nodes of the graph are marked. The surveillance number sn(G) of a graph G is the minimum amount of nodes that the observer has to mark at each turn ensuring it wins against any surfer in G. Fomin et al. also defined the connected surveillance game where the observer must ensure that marked nodes always induce a connected subgraph. They ask what is the cost of connectivity, i.e., is there a constant c \textgreater{} 0 such that the ratio between the connected surveillance number csn(G) and sn(G) is at most c for any graph G. It is straightforward to show that csn(G) $\le$ â sn(G) for any graph G with maximum degree â. Moreover, it has been shown that there are graphs G for which csn(G) = sn(G) + 1. In this paper, we investigate the question of the cost of the connectivity. We first provide new non-trivial upper and lower bounds for the cost of connectivity in the surveillance game. More precisely, we present a family of graphs G such that csn(G) \textgreater{} sn(G) + 1. Moreover, we prove that csn(G) $\le$ sn(G)n for any n-node graph G. While the gap between these bounds remains huge, it seems difficult to reduce it. We then define the online surveillance game where the observer has no a priori knowledge of the graph topology and discovers it little-by-little. This variant, which fits better the prefetching motivation, is a restriction of the connected variant. Unfortunately, we show that no algorithm for solving the online surveillance game has competitive ratio better than â¦(â). That is, while interesting, this variant does not help to obtain better upper bounds for the connected variant. We finally answer an open question [Fomin et al., 2012] by proving that deciding if the surveillance number of a digraph with maximum degree 6 is at most 2 is NP-hard.},
KEYWORDS = {Surveillance game ; Cops and robber games ; Prefetching ; Online strategy ; Competitive ratio ; Cost of connectivity},
PDF = {https://hal.inria.fr/hal-01163170/file/Connected-Surveillance-Journal%20-%20vHAL.pdf},
HAL_ID = {hal-01163170},
HAL_VERSION = {v1},
}
-
Frédéric Giroire,
Joanna Moulierac,
Truong Khoa Phan,
and frederic roudaut.
Minimization of network power consumption with redundancy elimination.
Computer Communications,
59:98--105,
March 2015.
[WWW
] [PDF
]
| Abstract: |
|
Recently, energy-aware routing (EAR) has gained an increasing popularity in the networking research community. The idea is that traffic demands are redirected over a subset of the network links, allowing other links to sleep to save energy. In this paper, we propose GreenRE -- a new EAR model with the support of data redundancy elimination (RE). This technique, enabled within routers, can virtually increase the capacity of network links. Based on real experiments on Orange Labs platform, we show that performing RE increases the energy consumption for routers. Therefore, it is important to determine which routers should enable RE and which links to put into sleep mode so that the power consumption of the network is minimized. We model the problem as Mixed Integer Linear Program and propose greedy heuristic algorithms for large networks. Simulations on several network topologies show that the GreenRE model can gain further 370f energy savings compared to the classical EAR model. |
@article{giroire:hal-01162715,
TITLE = {{Minimization of network power consumption with redundancy elimination}},
AUTHOR = {Giroire, Fr{\'e}d{\'e}ric and Moulierac, Joanna and Phan, Truong Khoa and roudaut, frederic},
URL = {https://hal.inria.fr/hal-01162715},
JOURNAL = {{Computer Communications}},
PUBLISHER = {{Elsevier}},
VOLUME = {59},
PAGES = {98--105},
YEAR = {2015},
MONTH = Mar,
DOI = {10.1016/j.comcom.2014.12.002},
ABSTRACT = {Recently, energy-aware routing (EAR) has gained an increasing popularity in the networking research community. The idea is that traffic demands are redirected over a subset of the network links, allowing other links to sleep to save energy. In this paper, we propose GreenRE -- a new EAR model with the support of data redundancy elimination (RE). This technique, enabled within routers, can virtually increase the capacity of network links. Based on real experiments on Orange Labs platform, we show that performing RE increases the energy consumption for routers. Therefore, it is important to determine which routers should enable RE and which links to put into sleep mode so that the power consumption of the network is minimized. We model the problem as Mixed Integer Linear Program and propose greedy heuristic algorithms for large networks. Simulations on several network topologies show that the GreenRE model can gain further 370f energy savings compared to the classical EAR model.},
PDF = {https://hal.inria.fr/hal-01162715/file/GreenRE_COMCOM13.pdf},
HAL_ID = {hal-01162715},
HAL_VERSION = {v1},
}
-
Frédéric Giroire,
Stéphane Pérennes,
and Issam Tahiri.
On the complexity of equal shortest path routing.
Networks,
2015.
[WWW
] [PDF
]
Keywords:
shortest path,
routing,
OSPF-ECMP protocol,
maximum flow,
NP-hard,
approximation algorithms,
inverse shortest path.
| Abstract: |
|
In telecommunication networks packets are carried from a source s to a destination t on a path determined by the underlying routing protocol. Most routing protocols belong to the class of shortest path routing protocols. In such protocols, the network operator assigns a length to each link. A packet going from s to t follows a shortest path according to these lengths. For better protection and efficiency, one wishes to use multiple (shortest) paths between two nodes. Therefore the routing protocol must determine how the traffic from s to t is distributed among the shortest paths. In the protocol called OSPF-ECMP (for Open Shortest Path First-Equal Cost Multiple Path) the traffic incoming at every node is uniformly balanced on all outgoing links that are on shortest paths. In that context, the operator task is to determine the '' best '' link lengths, toward a goal such as maximizing the network throughput for given link capacities. In this work, we show that the problem of maximizing even a single commodity flow for the OSPF-ECMP protocol cannot be approximated within any constant factor ratio. Besides this main theorem, we derive some positive results which include polynomial-time approximations and an exponential-time exact algorithm. |
@article{giroire:hal-01218473,
TITLE = {{On the complexity of equal shortest path routing}},
AUTHOR = {Giroire, Fr{\'e}d{\'e}ric and P{\'e}rennes, St{\'e}phane and Tahiri, Issam},
URL = {https://hal.inria.fr/hal-01218473},
JOURNAL = {{Networks}},
PUBLISHER = {{Wiley}},
YEAR = {2015},
DOI = {10.1002/net.21612},
ABSTRACT = {In telecommunication networks packets are carried from a source s to a destination t on a path determined by the underlying routing protocol. Most routing protocols belong to the class of shortest path routing protocols. In such protocols, the network operator assigns a length to each link. A packet going from s to t follows a shortest path according to these lengths. For better protection and efficiency, one wishes to use multiple (shortest) paths between two nodes. Therefore the routing protocol must determine how the traffic from s to t is distributed among the shortest paths. In the protocol called OSPF-ECMP (for Open Shortest Path First-Equal Cost Multiple Path) the traffic incoming at every node is uniformly balanced on all outgoing links that are on shortest paths. In that context, the operator task is to determine the '' best '' link lengths, toward a goal such as maximizing the network throughput for given link capacities. In this work, we show that the problem of maximizing even a single commodity flow for the OSPF-ECMP protocol cannot be approximated within any constant factor ratio. Besides this main theorem, we derive some positive results which include polynomial-time approximations and an exponential-time exact algorithm.},
KEYWORDS = {shortest path ; routing ; OSPF-ECMP protocol ; maximum flow ; NP-hard ; approximation algorithms ; inverse shortest path},
PDF = {https://hal.inria.fr/hal-01218473/file/ospf-journal.pdf},
HAL_ID = {hal-01218473},
HAL_VERSION = {v1},
}
-
Frédéric Havet,
A Karolinna Maia,
and Min-Li Yu.
Complexity of greedy edge-colouring.
Journal of the Brazilian Computer Society,
21(18),
2015.
[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 (G) or (G) + 1 and present a polynomial-time algorithm to determine it exactly. |
@article{havet:hal-01233312,
TITLE = {{Complexity of greedy edge-colouring}},
AUTHOR = {Havet, Fr{\'e}d{\'e}ric and Karolinna Maia, A and Yu, Min-Li},
URL = {https://hal.inria.fr/hal-01233312},
JOURNAL = {{Journal of the Brazilian Computer Society}},
PUBLISHER = {{Springer Verlag}},
VOLUME = {21},
NUMBER = {18},
YEAR = {2015},
DOI = {10.1186/s13173-015-0036-x},
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 (G) or (G) + 1 and present a polynomial-time algorithm to determine it exactly.},
PDF = {https://hal.inria.fr/hal-01233312/file/soumis-bresil.pdf},
HAL_ID = {hal-01233312},
HAL_VERSION = {v1},
}
-
Adrian Kosowski,
Bi Li,
Nicolas Nisse,
and Karol Suchan.
k-Chordal Graphs: from Cops and Robber to Compact Routing via Treewidth.
Algorithmica,
72(3):758-777,
2015.
[WWW
] [PDF
]
| Abstract: |
|
Cops and robber games, introduced by Winkler and Nowakowski [41] and independently defined by Quilliot [43], 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 (chordless) cycle of length greater than k, k $\ge$ 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 polynomial-time algorithm that, given a graph G and k $\ge$ 3, either returns an induced cycle larger than k in G, or computes a tree-decomposition of G, each 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 â has treewidth at most (k --1)(â --1) +2, improving the O(â (â --1) k--3) bound of Bodlaender and Thilikos (1997). Moreover, any graph admitting such a tree-decomposition has small hyperbolicity. As an application, for any n-vertex graph admitting such a tree-decomposition, we propose a compact routing scheme using routing tables, addresses and headers of size O(k log â + log n) bits and achieving an additive stretch of O(k log â). As far as we know, this is the first routing scheme with O(k log â + log n)-routing tables and small additive stretch for k-chordal graphs. |
@article{kosowski:hal-01163494,
TITLE = {{k-Chordal Graphs: from Cops and Robber to Compact Routing via Treewidth}},
AUTHOR = {Kosowski, Adrian and Li, Bi and Nisse, Nicolas and Suchan, Karol},
URL = {https://hal.archives-ouvertes.fr/hal-01163494},
JOURNAL = {{Algorithmica}},
PUBLISHER = {{Springer Verlag}},
VOLUME = {72},
NUMBER = {3},
PAGES = {758-777},
YEAR = {2015},
ABSTRACT = {Cops and robber games, introduced by Winkler and Nowakowski [41] and independently defined by Quilliot [43], 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 (chordless) cycle of length greater than k, k $\ge$ 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 polynomial-time algorithm that, given a graph G and k $\ge$ 3, either returns an induced cycle larger than k in G, or computes a tree-decomposition of G, each 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 â has treewidth at most (k --1)(â --1) +2, improving the O(â (â --1) k--3) bound of Bodlaender and Thilikos (1997). Moreover, any graph admitting such a tree-decomposition has small hyperbolicity. As an application, for any n-vertex graph admitting such a tree-decomposition, we propose a compact routing scheme using routing tables, addresses and headers of size O(k log â + log n) bits and achieving an additive stretch of O(k log â). As far as we know, this is the first routing scheme with O(k log â + log n)-routing tables and small additive stretch for k-chordal graphs.},
PDF = {https://hal.archives-ouvertes.fr/hal-01163494/file/CopsRouting_vHAL.pdf},
HAL_ID = {hal-01163494},
HAL_VERSION = {v1},
}
-
Joanna Moulierac and Truong Khoa Phan.
Optimizing IGP link weights for energy-efficiency in multi-period traffic matrices.
Computer Communications,
61:11,
May 2015.
[WWW
] [PDF
]
| Abstract: |
|
Recently, due to the increasing power consumption and worldwide gases emissions in ICT (Information and Communication Technology), energy efficient ways to design and operate backbone networks are becoming a new concern for network operators. Since these networks are usually overprovisioned and since traffic load has a small influence on power consumption of network equipments, the most common approach to save energy is to put unused line cards that drive links between neighboring routers into sleep mode. To guarantee QoS, all traffic demands should be routed without violating capacity constraints and the network should keep its connectivity. From the perspective of traffic engineering, we argue that stability in routing configuration also plays an important role in QoS. In details, frequent changes in network configuration (link weights, slept and activated links) to adapt with traffic fluctuation in daily time cause network oscillations. In this work, we propose a novel optimization method to adjust the link weights of Open Shortest Path First (OSPF) protocol while limiting the changes in network configurations when multi-period traffic matrices are considered. We formally define the problem and model it as Mixed Integer Linear Program (MILP). We then propose an efficient heuristic algorithm that is suitable for large networks. Simulation results with real traffic traces on three different networks show that our approach achieves high energy saving while keeping the networks in stable state (less changes in network configuration). |
@article{moulierac:hal-01162700,
TITLE = {{Optimizing IGP link weights for energy-efficiency in multi-period traffic matrices}},
AUTHOR = {Moulierac, Joanna and Phan, Truong Khoa},
URL = {https://hal.inria.fr/hal-01162700},
JOURNAL = {{Computer Communications}},
PUBLISHER = {{Elsevier}},
VOLUME = {61},
PAGES = {11},
YEAR = {2015},
MONTH = May,
DOI = {10.1016/j.comcom.2015.01.004},
ABSTRACT = {Recently, due to the increasing power consumption and worldwide gases emissions in ICT (Information and Communication Technology), energy efficient ways to design and operate backbone networks are becoming a new concern for network operators. Since these networks are usually overprovisioned and since traffic load has a small influence on power consumption of network equipments, the most common approach to save energy is to put unused line cards that drive links between neighboring routers into sleep mode. To guarantee QoS, all traffic demands should be routed without violating capacity constraints and the network should keep its connectivity. From the perspective of traffic engineering, we argue that stability in routing configuration also plays an important role in QoS. In details, frequent changes in network configuration (link weights, slept and activated links) to adapt with traffic fluctuation in daily time cause network oscillations. In this work, we propose a novel optimization method to adjust the link weights of Open Shortest Path First (OSPF) protocol while limiting the changes in network configurations when multi-period traffic matrices are considered. We formally define the problem and model it as Mixed Integer Linear Program (MILP). We then propose an efficient heuristic algorithm that is suitable for large networks. Simulation results with real traffic traces on three different networks show that our approach achieves high energy saving while keeping the networks in stable state (less changes in network configuration).},
PDF = {https://hal.inria.fr/hal-01162700/file/moulierac2014optimizing.pdf},
HAL_ID = {hal-01162700},
HAL_VERSION = {v1},
}
-
Michele Borassi,
David Coudert,
Pierluigi Crescenzi,
and Andrea Marino.
On Computing the Hyperbolicity of Real-World Graphs.
In 23rd Annual European Symposium on Algorithms (ESA),
volume 9294 of Lecture Notes in Computer Science,
Patras, Greece,
pages 215-226,
September 2015.
Springer.
[WWW
] [PDF
]
Keywords:
Hyperbolicity,
Graph,
Algorithm.
| Abstract: |
|
The (Gromov) hyperbolicity is a topological property of a graph, which has been recently applied in several different contexts, such as the design of routing schemes, network security, computational biology, the analysis of graph algorithms, and the classification of complex networks. Computing the hyperbolicity of a graph can be very time consuming: indeed, the best available algorithm has running-time O(n^{3.69}), which is clearly prohibitive for big graphs. In this paper, we provide a new and more efficient algorithm: although its worst-case complexity is O(n^4), in practice it is much faster, allowing, for the first time, the computation of the hyperbolicity of graphs with up to 200,000 nodes. We experimentally show that our new algorithm drastically outperforms the best previously available algorithms, by analyzing a big dataset of real-world networks. Finally, we apply the new algorithm to compute the hyperbolicity of random graphs generated with the Erd{\"o}s-Renyi model, the Chung-Lu model, and the Configuration Model. |
@inproceedings{borassi:hal-01199860,
TITLE = {{On Computing the Hyperbolicity of Real-World Graphs}},
AUTHOR = {Borassi, Michele and Coudert, David and Crescenzi, Pierluigi and Marino, Andrea},
URL = {https://hal.inria.fr/hal-01199860},
BOOKTITLE = {{23rd Annual European Symposium on Algorithms (ESA)}},
ADDRESS = {Patras, Greece},
PUBLISHER = {{Springer}},
SERIES = {Lecture Notes in Computer Science},
VOLUME = {9294},
PAGES = {215-226},
YEAR = {2015},
MONTH = Sep,
DOI = {10.1007/978-3-662-48350-3\_19},
ABSTRACT = {The (Gromov) hyperbolicity is a topological property of a graph, which has been recently applied in several different contexts, such as the design of routing schemes, network security, computational biology, the analysis of graph algorithms, and the classification of complex networks. Computing the hyperbolicity of a graph can be very time consuming: indeed, the best available algorithm has running-time O(n^{3.69}), which is clearly prohibitive for big graphs. In this paper, we provide a new and more efficient algorithm: although its worst-case complexity is O(n^4), in practice it is much faster, allowing, for the first time, the computation of the hyperbolicity of graphs with up to 200,000 nodes. We experimentally show that our new algorithm drastically outperforms the best previously available algorithms, by analyzing a big dataset of real-world networks. Finally, we apply the new algorithm to compute the hyperbolicity of random graphs generated with the Erd{\"o}s-Renyi model, the Chung-Lu model, and the Configuration Model.},
KEYWORDS = {Hyperbolicity ; Graph ; Algorithm},
PDF = {https://hal.inria.fr/hal-01199860/file/BCCM15.pdf},
HAL_ID = {hal-01199860},
HAL_VERSION = {v1},
}
-
Augustin Chaintreau,
Guillaume Ducoffe,
Roxana Geambasu,
and Mathias Lécuyer.
Vers une plus grande transparence du Web.
In ALGOTEL 2015 - 17èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications,
Beaune, France,
June 2015.
[WWW
] [PDF
]
Keywords:
Algorithmes d'apprentissage,
Formes normales disjonctives monotones,
Annonces publicitaires ciblées,
Sécurité de l'information (Privacy).
| Abstract: |
|
De plus en plus les g{\'e}ants du Web (Amazon, Google et Twitter en t{\^e}te) recourent a la manne des " Big data " : ils collectent une myriade de donn{\'e}es qu'ils exploitent pour leurs algorithmes de recommandation personnalis{\'e}e et leurs campagnes publicitaires. Pareilles m{\'e}thodes peuvent consid{\'e}rablement am{\'e}liorer les services rendus a leurs utilisateurs, mais leur opacit{\'e} fait d{\'e}bat. En effet, il n'existe pas a ce jour d'outil suffisamment robuste qui puisse tracer sur le Web l'usage des donn{\'e}es et des informations sur un utilisateur par des services en ligne. Motiv{\'e}s par ce manque de transparence, nous avons d{\'e}velopp{\'e} un prototype du nom d'XRay, et qui peut pr{\'e}dire quelle donn{\'e}e parmi toutes celles pr{\'e}sentes dans un compte utilisateur est responsable de la r{\'e}ception d'une publicit{\'e}. Dans cet article, nous pr{\'e}sentons son principe ainsi que les r{\'e}sultats de nos premi{\`e}res exp{\'e}rimentations. Nous introduisons dans le m{\^e}me temps le tout premier mod{\`e}le th{\'e}orique pour le probl{\`e}me de la transparence du Web, et nous interpr{\'e}tons les performances d'Xray a la lumi{\`e}re de nos r{\'e}sultats obtenus dans ce mod{\`e}le. En particulier, nous d{\'e}montrons qu'un nombre $\\theta$(log N) de comptes utilisateurs auxiliaires, remplis selon un proc{\'e}d{\'e} al{\'e}atoire , suffisent a d{\'e}terminer quelle donn{\'e}e parmi les N en pr{\'e}sence a caus{\'e} la r{\'e}ception d'une publicit{\'e}. Nous aborderons bri{\`e}vement les extensions possibles, et quelques probl{\`e}mes ouverts. |
@inproceedings{chaintreau:hal-01144787,
TITLE = {{Vers une plus grande transparence du Web}},
AUTHOR = {Chaintreau, Augustin and Ducoffe, Guillaume and Geambasu, Roxana and L{\'e}cuyer, Mathias},
URL = {https://hal.archives-ouvertes.fr/hal-01144787},
BOOKTITLE = {{ALGOTEL 2015 - 17{\`e}mes Rencontres Francophones sur les Aspects Algorithmiques des T{\'e}l{\'e}communications}},
ADDRESS = {Beaune, France},
YEAR = {2015},
MONTH = Jun,
ABSTRACT = {De plus en plus les g{\'e}ants du Web (Amazon, Google et Twitter en t{\^e}te) recourent a la manne des " Big data " : ils collectent une myriade de donn{\'e}es qu'ils exploitent pour leurs algorithmes de recommandation personnalis{\'e}e et leurs campagnes publicitaires. Pareilles m{\'e}thodes peuvent consid{\'e}rablement am{\'e}liorer les services rendus a leurs utilisateurs, mais leur opacit{\'e} fait d{\'e}bat. En effet, il n'existe pas a ce jour d'outil suffisamment robuste qui puisse tracer sur le Web l'usage des donn{\'e}es et des informations sur un utilisateur par des services en ligne. Motiv{\'e}s par ce manque de transparence, nous avons d{\'e}velopp{\'e} un prototype du nom d'XRay, et qui peut pr{\'e}dire quelle donn{\'e}e parmi toutes celles pr{\'e}sentes dans un compte utilisateur est responsable de la r{\'e}ception d'une publicit{\'e}. Dans cet article, nous pr{\'e}sentons son principe ainsi que les r{\'e}sultats de nos premi{\`e}res exp{\'e}rimentations. Nous introduisons dans le m{\^e}me temps le tout premier mod{\`e}le th{\'e}orique pour le probl{\`e}me de la transparence du Web, et nous interpr{\'e}tons les performances d'Xray a la lumi{\`e}re de nos r{\'e}sultats obtenus dans ce mod{\`e}le. En particulier, nous d{\'e}montrons qu'un nombre $\\theta$(log N) de comptes utilisateurs auxiliaires, remplis selon un proc{\'e}d{\'e} al{\'e}atoire , suffisent a d{\'e}terminer quelle donn{\'e}e parmi les N en pr{\'e}sence a caus{\'e} la r{\'e}ception d'une publicit{\'e}. Nous aborderons bri{\`e}vement les extensions possibles, et quelques probl{\`e}mes ouverts.},
KEYWORDS = {Algorithmes d'apprentissage ; Formes normales disjonctives monotones ; Annonces publicitaires cibl{\'e}es ; S{\'e}curit{\'e} de l'information (Privacy)},
PDF = {https://hal.archives-ouvertes.fr/hal-01144787/file/xRayAlgotel.pdf},
HAL_ID = {hal-01144787},
HAL_VERSION = {v1},
}
-
David Coudert,
Guillaume Ducoffe,
and Nicolas Nisse.
Structure vs métrique dans les graphes.
In ALGOTEL 2015 - 17èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications,
Beaune, France,
June 2015.
[WWW
] [PDF
]
Keywords:
Genre,
Hyperbolicité,
Graphe,
Largeur arborescente (Treewidth),
Longueur arborescente (Treelength).
| Abstract: |
|
L'{\'e}mergence de r{\'e}seaux de tr{\`e}s grande taille oblige {\`a} repenser de nombreux probl{\`e}mes sur les graphes : en apparence simples, mais pour lesquels les algorithmes de r{\'e}solution connus ne passent plus a l'{\'e}chelle. Une approche possible est de mieux comprendre les propri{\'e}t{\'e}s de ces r{\'e}seaux complexes, et d'en d{\'e}duire de nouvelles m{\'e}thodes plus efficaces. C'est dans ce but que nous d{\'e}montrons des relations g{\'e}n{\'e}rales entre les propri{\'e}t{\'e}s structurelles des graphes et leurs propri{\'e}t{\'e}s m{\'e}triques. Nos relations se d{\'e}duisent de nouvelles bornes serr{\'e}es sur le diam{\`e}tre des s{\'e}parateurs minimaux dans un graphe. Plus pr{\'e}cis{\'e}ment , nous prouvons que dans tout graphe G le diam{\`e}tre d'un s{\'e}parateur minimal S dans G est au plus (l(G)/2) · (|S| -- 1), avec l(G) la plus grande taille d'un cycle isom{\'e}trique dans G. Nos preuves reposent sur des propri{\'e}t{\'e}s de connexit{\'e} dans les puissances d'un graphe. Une cons{\'e}quence de nos r{\'e}sultats est que pour tout graphe G, sa longueur arborescente (treelength) est au plus l(G)/2 fois sa largeur arborescente (treewidth). En compl{\'e}ment de cette relation, nous bornons la largeur arborescente par une fonction de la longueur arborescente et du genre du graphe. Cette borne se g{\'e}n{\'e}ralise {\`a} la famille des graphes qui excluent un apex-graph H comme mineur. Par cons{\'e}quent , nous obtenons un algorithme tr{\`e}s simple qui, {\'e}tant donn{\'e} un graphe excluant un apex-graph fix{\'e} comme mineur, calcule sa largeur arborescente en temps O(n${}^2$) et avec facteur d'approximation O(l(G)). |
@inproceedings{coudert:hal-01144694,
TITLE = {{Structure vs m{\'e}trique dans les graphes}},
AUTHOR = {Coudert, David and Ducoffe, Guillaume and Nisse, Nicolas},
URL = {https://hal.archives-ouvertes.fr/hal-01144694},
BOOKTITLE = {{ALGOTEL 2015 - 17{\`e}mes Rencontres Francophones sur les Aspects Algorithmiques des T{\'e}l{\'e}communications}},
ADDRESS = {Beaune, France},
YEAR = {2015},
MONTH = Jun,
ABSTRACT = {L'{\'e}mergence de r{\'e}seaux de tr{\`e}s grande taille oblige {\`a} repenser de nombreux probl{\`e}mes sur les graphes : en apparence simples, mais pour lesquels les algorithmes de r{\'e}solution connus ne passent plus a l'{\'e}chelle. Une approche possible est de mieux comprendre les propri{\'e}t{\'e}s de ces r{\'e}seaux complexes, et d'en d{\'e}duire de nouvelles m{\'e}thodes plus efficaces. C'est dans ce but que nous d{\'e}montrons des relations g{\'e}n{\'e}rales entre les propri{\'e}t{\'e}s structurelles des graphes et leurs propri{\'e}t{\'e}s m{\'e}triques. Nos relations se d{\'e}duisent de nouvelles bornes serr{\'e}es sur le diam{\`e}tre des s{\'e}parateurs minimaux dans un graphe. Plus pr{\'e}cis{\'e}ment , nous prouvons que dans tout graphe G le diam{\`e}tre d'un s{\'e}parateur minimal S dans G est au plus (l(G)/2) · (|S| -- 1), avec l(G) la plus grande taille d'un cycle isom{\'e}trique dans G. Nos preuves reposent sur des propri{\'e}t{\'e}s de connexit{\'e} dans les puissances d'un graphe. Une cons{\'e}quence de nos r{\'e}sultats est que pour tout graphe G, sa longueur arborescente (treelength) est au plus l(G)/2 fois sa largeur arborescente (treewidth). En compl{\'e}ment de cette relation, nous bornons la largeur arborescente par une fonction de la longueur arborescente et du genre du graphe. Cette borne se g{\'e}n{\'e}ralise {\`a} la famille des graphes qui excluent un apex-graph H comme mineur. Par cons{\'e}quent , nous obtenons un algorithme tr{\`e}s simple qui, {\'e}tant donn{\'e} un graphe excluant un apex-graph fix{\'e} comme mineur, calcule sa largeur arborescente en temps O(n${}^2$) et avec facteur d'approximation O(l(G)).},
KEYWORDS = {Genre ; Hyperbolicit{\'e} ; Graphe ; Largeur arborescente (Treewidth) ; Longueur arborescente (Treelength)},
PDF = {https://hal.archives-ouvertes.fr/hal-01144694/file/separatorAlgotel_vFinale.pdf},
HAL_ID = {hal-01144694},
HAL_VERSION = {v1},
}
-
Frédéric Giroire,
Frédéric Havet,
and Joanna Moulierac.
Compressing two-dimensional routing tables with order.
In INOC (International Network Optimization Conference),
Varsovie, Poland,
May 2015.
[WWW
] [PDF
]
| Abstract: |
|
A communication in a network is a pair of nodes (s, t). The node s is called the source source and t the destination. A communication set is a set of distinct communications, i.e. two communications might have the same source or the same destination, but they cannot have both same source and same destination. A routing of a communication (s, t) is a path in the network from s to t. A routing of a communication set is a union of routings of its communications. At each node, there is a set X of communications whose routing path goes through this node. The node needs to be able to find for each communication (s,t) in X, the port that the routing path of (s,t) uses to leave it. An easy way of doing it is to store the list of all triples (s,t,k), where (s, t) $\in$ X and k is the port used by the (s, t)-path to leave the node. Such triples are called communication triples. However, such a list might be very large. Motivated by routing in telecommunication network using Software Defined Network Technologies, we consider the problem of compacting this list using aggregation rules. Indeed, SDN routers use specific memory which is expensive and of small capacity. Hence, in addition, we can use some additional triples, called $\star$-triples. As an example, a t-destination triple ($\star$, t, p), means that every communication with destination t leaves on port p. We carry out in this work a study of the problem complexity, providing results of NP-completeness, of Fixed-Parameter Tractability and approximation algorithms. |
@inproceedings{giroire:hal-01162724,
TITLE = {{Compressing two-dimensional routing tables with order}},
AUTHOR = {Giroire, Fr{\'e}d{\'e}ric and Havet, Fr{\'e}d{\'e}ric and Moulierac, Joanna},
URL = {https://hal.inria.fr/hal-01162724},
BOOKTITLE = {{INOC (International Network Optimization Conference)}},
ADDRESS = {Varsovie, Poland},
YEAR = {2015},
MONTH = May,
ABSTRACT = {A communication in a network is a pair of nodes (s, t). The node s is called the source source and t the destination. A communication set is a set of distinct communications, i.e. two communications might have the same source or the same destination, but they cannot have both same source and same destination. A routing of a communication (s, t) is a path in the network from s to t. A routing of a communication set is a union of routings of its communications. At each node, there is a set X of communications whose routing path goes through this node. The node needs to be able to find for each communication (s,t) in X, the port that the routing path of (s,t) uses to leave it. An easy way of doing it is to store the list of all triples (s,t,k), where (s, t) $\in$ X and k is the port used by the (s, t)-path to leave the node. Such triples are called communication triples. However, such a list might be very large. Motivated by routing in telecommunication network using Software Defined Network Technologies, we consider the problem of compacting this list using aggregation rules. Indeed, SDN routers use specific memory which is expensive and of small capacity. Hence, in addition, we can use some additional triples, called $\star$-triples. As an example, a t-destination triple ($\star$, t, p), means that every communication with destination t leaves on port p. We carry out in this work a study of the problem complexity, providing results of NP-completeness, of Fixed-Parameter Tractability and approximation algorithms.},
PDF = {https://hal.inria.fr/hal-01162724/file/compacting-camera-ready-final.pdf},
HAL_ID = {hal-01162724},
HAL_VERSION = {v1},
}
-
Frédéric Giroire and Nicolas Huin.
Study of Repair Protocols for Live Video Streaming Distributed Systems.
In IEEE GLOBECOM 2015 - Global Communications Conference,
San Diego, United States,
December 2015.
[WWW
] [PDF
]
| Abstract: |
|
-We study distributed systems for live video streaming. These systems can be of two types: structured and un-structured. In an unstructured system, the diffusion is done opportunistically. The advantage is that it handles churn, that is the arrival and departure of users, which is very high in live streaming systems, in a smooth way. On the opposite, in a structured system, the diffusion of the video is done using explicit diffusion trees. The advantage is that the diffusion is very efficient, but the structure is broken by the churn. In this paper, we propose simple distributed repair protocols to maintain, under churn, the diffusion tree of a structured streaming system. We study these protocols using formal analysis and simulation. In particular, we provide an estimation of the system metrics, bandwidth usage, delay, or number of interruptions of the streaming. Our work shows that structured streaming systems can be efficient and resistant to churn. |
@inproceedings{giroire:hal-01221319,
TITLE = {{Study of Repair Protocols for Live Video Streaming Distributed Systems}},
AUTHOR = {Giroire, Fr{\'e}d{\'e}ric and Huin, Nicolas},
URL = {https://hal.inria.fr/hal-01221319},
BOOKTITLE = {{IEEE GLOBECOM 2015 - Global Communications Conference}},
ADDRESS = {San Diego, United States},
YEAR = {2015},
MONTH = Dec,
ABSTRACT = {-We study distributed systems for live video streaming. These systems can be of two types: structured and un-structured. In an unstructured system, the diffusion is done opportunistically. The advantage is that it handles churn, that is the arrival and departure of users, which is very high in live streaming systems, in a smooth way. On the opposite, in a structured system, the diffusion of the video is done using explicit diffusion trees. The advantage is that the diffusion is very efficient, but the structure is broken by the churn. In this paper, we propose simple distributed repair protocols to maintain, under churn, the diffusion tree of a structured streaming system. We study these protocols using formal analysis and simulation. In particular, we provide an estimation of the system metrics, bandwidth usage, delay, or number of interruptions of the streaming. Our work shows that structured streaming systems can be efficient and resistant to churn.},
PDF = {https://hal.inria.fr/hal-01221319/file/gc15 amera%20ready.pdf},
HAL_ID = {hal-01221319},
HAL_VERSION = {v1},
}
-
Frédéric Giroire,
Stephane Perennes,
and Issam Tahiri.
Grid spanners with low forwarding index for energy efficient networks.
In International Network Optimization Conference (INOC),
Electronic Notes in Discrete Mathematics,
Warsaw, Poland,
May 2015.
[WWW
] [PDF
]
Keywords:
spanning subgraphs,
forwarding index,
energy saving,
routing,
grid.
| Abstract: |
|
A routing R of a connected graph G is a collection that contains simple paths connecting every ordered pair of vertices in G. The edge-forwarding index with respect to R (or simply the forwarding index with respect to R) $\pi$(G, R) of G is the maximum number of paths in R passing through any edge of G. The forwarding index $\pi$(G) of G is the minimum $\pi$(G, R) over all routings R's of G. This parameter has been studied for different graph classes [12], [1], [5], [4]. Motivated by energy efficiency, we look, for different numbers of edges, at the best spanning graphs of a square grid, namely those with a low forwarding index. |
@inproceedings{giroire:hal-01218411,
TITLE = {{Grid spanners with low forwarding index for energy efficient networks }},
AUTHOR = {Giroire, Fr{\'e}d{\'e}ric and Perennes, Stephane and Tahiri, Issam},
URL = {https://hal.inria.fr/hal-01218411},
BOOKTITLE = {{International Network Optimization Conference (INOC)}},
ADDRESS = {Warsaw, Poland},
SERIES = {Electronic Notes in Discrete Mathematics},
YEAR = {2015},
MONTH = May,
ABSTRACT = {A routing R of a connected graph G is a collection that contains simple paths connecting every ordered pair of vertices in G. The edge-forwarding index with respect to R (or simply the forwarding index with respect to R) $\pi$(G, R) of G is the maximum number of paths in R passing through any edge of G. The forwarding index $\pi$(G) of G is the minimum $\pi$(G, R) over all routings R's of G. This parameter has been studied for different graph classes [12], [1], [5], [4]. Motivated by energy efficiency, we look, for different numbers of edges, at the best spanning graphs of a square grid, namely those with a low forwarding index.},
KEYWORDS = {spanning subgraphs ; forwarding index ; energy saving ; routing ; grid},
PDF = {https://hal.inria.fr/hal-01218411/file/camera-ready-inoc.pdf},
HAL_ID = {hal-01218411},
HAL_VERSION = {v1},
}
-
Frédéric Giroire,
Stéphane Pérennes,
and Issam Tahiri.
How to design graphs with low forwarding index and limited number of edges.
In 26th International Workshop on Combinatorial Algorithms (IWOCA 2015),
Verona, Italy,
October 2015.
[WWW
] [PDF
]
Keywords:
graphs,
forwarding index,
routing,
design problem,
energy efficiency,
extremal graphs.
| Abstract: |
|
The (edge) forwarding index of a graph is the minimum, over all possible rout-ings of all the demands, of the maximum load of an edge. This metric is of a great interest since it captures the notion of global congestion in a precise way: the lesser the forwarding-index, the lesser the congestion. In this paper, we study the following design question: Given a number e of edges and a number n of vertices, what is the least congested graph that we can construct? and what forwarding-index can we achieve? Our problem has some distant similarities with the well-known (â, D) problem, and we sometimes build upon results obtained on it. The goal of this paper is to study how to build graphs with low forwarding indices and to understand how the number of edges impacts the forwarding index. We answer here these questions for different families of graphs: general graphs, graphs with bounded degree, sparse graphs with a small number of edges by providing constructions, most of them asymptotically optimal. For instance, we provide an asymptotically optimal construction for (n, n + k) cubic graphs-its forwarding index is $\sim$ n 2 3k log 2 (k). Our results allow to understand how the forwarding-index drops when edges are added to a graph and also to determine what is the best (i.e least congested) structure with e edges. Doing so, we partially answer the practical problem that initially motivated our work: If an operator wants to power only e links of its network, in order to reduce the energy consumption (or wiring cost) of its networks, what should be those links and what performance can be expected? |
@inproceedings{giroire:hal-01221650,
TITLE = {{How to design graphs with low forwarding index and limited number of edges}},
AUTHOR = {Giroire, Fr{\'e}d{\'e}ric and P{\'e}rennes, St{\'e}phane and Tahiri, Issam},
URL = {https://hal.inria.fr/hal-01221650},
BOOKTITLE = {{26th International Workshop on Combinatorial Algorithms (IWOCA 2015)}},
ADDRESS = {Verona, Italy},
YEAR = {2015},
MONTH = Oct,
ABSTRACT = {The (edge) forwarding index of a graph is the minimum, over all possible rout-ings of all the demands, of the maximum load of an edge. This metric is of a great interest since it captures the notion of global congestion in a precise way: the lesser the forwarding-index, the lesser the congestion. In this paper, we study the following design question: Given a number e of edges and a number n of vertices, what is the least congested graph that we can construct? and what forwarding-index can we achieve? Our problem has some distant similarities with the well-known (â, D) problem, and we sometimes build upon results obtained on it. The goal of this paper is to study how to build graphs with low forwarding indices and to understand how the number of edges impacts the forwarding index. We answer here these questions for different families of graphs: general graphs, graphs with bounded degree, sparse graphs with a small number of edges by providing constructions, most of them asymptotically optimal. For instance, we provide an asymptotically optimal construction for (n, n + k) cubic graphs-its forwarding index is $\sim$ n 2 3k log 2 (k). Our results allow to understand how the forwarding-index drops when edges are added to a graph and also to determine what is the best (i.e least congested) structure with e edges. Doing so, we partially answer the practical problem that initially motivated our work: If an operator wants to power only e links of its network, in order to reduce the energy consumption (or wiring cost) of its networks, what should be those links and what performance can be expected?},
KEYWORDS = {graphs ; forwarding index ; routing ; design problem ; energy efficiency ; extremal graphs},
PDF = {https://hal.inria.fr/hal-01221650/file/iwoca15-camera-ready%281 0x4df},
HAL_ID = {hal-01221650},
HAL_VERSION = {v1},
}
-
Frédéric Havet,
Nicolas Huin,
Joanna Moulierac,
and Khoa Phan.
Routage vert et compression de règles SDN.
In ALGOTEL 2015 - 17èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications,
Beaune, France,
June 2015.
[WWW
] [PDF
]
| Abstract: |
|
La technologie SDN permet de s{\'e}parer le plan de contr{\^o}le et le plan de donn{\'e}es qui cohabitent actuellement sur les routeurs dans les architectures r{\'e}seaux classiques et de r{\'e}aliser le routage par un ou plusieurs contr{\^o}leur(s) centralis{\'e}(s). Nos travaux portent sur l'utilisation de cette technologie pour minimiser la consommation d'{\'e}nergie dans les r{\'e}seaux, notamment en permettant au contr{\^o}leur d'{\'e}teindre {\`a} distance des liens non utilis{\'e}s. Une des probl{\'e}matiques est que les tables de routage SDN ne peuvent contenir qu'un nombre tr es limit{\'e} de r{\`e}gles. Ceci est d{\^u} au type particulier de m{\'e}moire utilis{\'e} pour permettre l'ajout a distance de r{\`e}gles de routage par le contr{\^o}leur SDN. Dans ce papier, nous {\'e}tudions le probl{\`e}me de compression de tables de routage bidimensionnelles avec priorit{\'e}, en particulier la complexit{\'e} algorithmique et proposons des algorithmes d'approximation. Nous proposons ensuite des algorithmes de routage vert qui effectuent en m{\^e}me temps le choix des routes, la compression des tables de routages et la mise en veille des liens non utilis{\'e}s. Ces algorithmes sont test{\'e}s sur les r{\'e}seaux de la librairie SNDLib. |
@inproceedings{havet:hal-01148471,
TITLE = {{Routage vert et compression de r{\`e}gles SDN}},
AUTHOR = {Havet, Fr{\'e}d{\'e}ric and Huin, Nicolas and Moulierac, Joanna and Phan, Khoa},
URL = {https://hal.archives-ouvertes.fr/hal-01148471},
BOOKTITLE = {{ALGOTEL 2015 - 17{\`e}mes Rencontres Francophones sur les Aspects Algorithmiques des T{\'e}l{\'e}communications}},
ADDRESS = {Beaune, France},
YEAR = {2015},
MONTH = Jun,
ABSTRACT = {La technologie SDN permet de s{\'e}parer le plan de contr{\^o}le et le plan de donn{\'e}es qui cohabitent actuellement sur les routeurs dans les architectures r{\'e}seaux classiques et de r{\'e}aliser le routage par un ou plusieurs contr{\^o}leur(s) centralis{\'e}(s). Nos travaux portent sur l'utilisation de cette technologie pour minimiser la consommation d'{\'e}nergie dans les r{\'e}seaux, notamment en permettant au contr{\^o}leur d'{\'e}teindre {\`a} distance des liens non utilis{\'e}s. Une des probl{\'e}matiques est que les tables de routage SDN ne peuvent contenir qu'un nombre tr es limit{\'e} de r{\`e}gles. Ceci est d{\^u} au type particulier de m{\'e}moire utilis{\'e} pour permettre l'ajout a distance de r{\`e}gles de routage par le contr{\^o}leur SDN. Dans ce papier, nous {\'e}tudions le probl{\`e}me de compression de tables de routage bidimensionnelles avec priorit{\'e}, en particulier la complexit{\'e} algorithmique et proposons des algorithmes d'approximation. Nous proposons ensuite des algorithmes de routage vert qui effectuent en m{\^e}me temps le choix des routes, la compression des tables de routages et la mise en veille des liens non utilis{\'e}s. Ces algorithmes sont test{\'e}s sur les r{\'e}seaux de la librairie SNDLib.},
PDF = {https://hal.archives-ouvertes.fr/hal-01148471/file/draft.pdf},
HAL_ID = {hal-01148471},
HAL_VERSION = {v1},
}
-
Mamadou Moustapha Kanté,
Fatima Zahra Moataz,
Benjamin Momège,
and Nicolas Nisse.
On paths in grids with forbidden transitions.
In ALGOTEL 2015 - 17èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications,
Beaune, France,
June 2015.
[WWW
] [PDF
]
Keywords:
Forbidden transitions,
planar graph,
grid,
asymmetric nodes.
| Abstract: |
|
Une transition dans un graphe est une paire d'ar{\^e}tes incidentes {\`a} un m{\^e}me sommet. Etant donn{\'e}s un graphe G = (V, E), deux sommets s,t $\in$ V et un ensemble associ{\'e} de transitions interdites F $\subseteq$ E Ã E, le probl{\`e}me de chemin {\'e}vitant des transitions interdites consiste {\`a} d{\'e}cider s'il existe un chemin {\'e}l{\'e}mentaire de s {\`a} t qui n'utilise aucune des transitions de F. C'est-{\`a}-dire qu'il est interdit d'emprunter cons{\'e}cutivement deux ar{\^e}tes qui soient une paire de F. Ce probl{\`e}me est motiv{\'e} par le routage dans les r{\'e}seaux routiers (o{\`u} une transition interdite repr{\'e}sente une interdiction de tourner) ainsi que dans les r{\'e}seaux optiques avec des noeuds asym{\'e}triques. Nous prouvons que le probl{\`e}me est NP-difficile dans les graphes planaires et plus particuli{\`e}rement dans les grilles. Nous montrons {\'e}galement que leprobl{\`e}me peut {\^e}tre r{\'e}solu en temps polynomial dans la classe des graphes de largeur arborescente born{\'e}e. |
@inproceedings{kante:hal-01142745,
TITLE = {{On paths in grids with forbidden transitions}},
AUTHOR = {Kant{\'e}, Mamadou Moustapha and Moataz, Fatima Zahra and Mom{\`e}ge, Benjamin and Nisse, Nicolas},
URL = {https://hal.archives-ouvertes.fr/hal-01142745},
BOOKTITLE = {{ALGOTEL 2015 - 17{\`e}mes Rencontres Francophones sur les Aspects Algorithmiques des T{\'e}l{\'e}communications}},
ADDRESS = {Beaune, France},
YEAR = {2015},
MONTH = Jun,
ABSTRACT = {Une transition dans un graphe est une paire d'ar{\^e}tes incidentes {\`a} un m{\^e}me sommet. Etant donn{\'e}s un graphe G = (V, E), deux sommets s,t $\in$ V et un ensemble associ{\'e} de transitions interdites F $\subseteq$ E Ã E, le probl{\`e}me de chemin {\'e}vitant des transitions interdites consiste {\`a} d{\'e}cider s'il existe un chemin {\'e}l{\'e}mentaire de s {\`a} t qui n'utilise aucune des transitions de F. C'est-{\`a}-dire qu'il est interdit d'emprunter cons{\'e}cutivement deux ar{\^e}tes qui soient une paire de F. Ce probl{\`e}me est motiv{\'e} par le routage dans les r{\'e}seaux routiers (o{\`u} une transition interdite repr{\'e}sente une interdiction de tourner) ainsi que dans les r{\'e}seaux optiques avec des noeuds asym{\'e}triques. Nous prouvons que le probl{\`e}me est NP-difficile dans les graphes planaires et plus particuli{\`e}rement dans les grilles. Nous montrons {\'e}galement que leprobl{\`e}me peut {\^e}tre r{\'e}solu en temps polynomial dans la classe des graphes de largeur arborescente born{\'e}e.},
KEYWORDS = {Forbidden transitions ; planar graph ; grid ; asymmetric nodes},
PDF = {https://hal.archives-ouvertes.fr/hal-01142745/file/PAFT_FinalVersion.pdf},
HAL_ID = {hal-01142745},
HAL_VERSION = {v1},
}
-
Mamadou Moustapha Kanté,
Fatima Zahra Moataz,
Benjamin Momège,
and Nicolas Nisse.
Finding Paths in Grids with Forbidden Transitions.
In WG 2015, 41st International Workshop on Graph-Theoretic Concepts in Computer Science,
Munich, Germany,
June 2015.
[WWW
] [PDF
]
| Abstract: |
|
A transition in a graph is a pair of adjacent edges. Given a graph G = (V, E), a set of forbidden transitions F $\subseteq$ E Ã E and two vertices s, t $\in$ V , we study the problem of finding a path from s to t which uses none of the forbidden transitions of F. This means that it is forbidden for the path to consecutively use two edges forming a pair in F. The study of this problem is motivated by routing in road networks in which forbidden transitions are associated to prohibited turns as well as routing in optical networks with asymmetric nodes, which are nodes where a signal on an ingress port can only reach a subset of egress ports. If the path is not required to be elementary, the problem can be solved in polynomial time. On the other side, if the path has to be elementary, the problem is known to be NP-complete in general graphs [Szeider 2003]. In this paper, we study the problem of finding an elementary path avoiding forbidden transitions in planar graphs. We prove that the problem is NP-complete in planar graphs and particularly in grids. In addition, we show that the problem can be solved in polynomial time in graphs with bounded treewidth. More precisely, we show that there is an algorithm which solves the problem in time O((3â(k + 1)) 2k+4 n)) in n-node graphs with treewidth at most k and maximum degree â. |
@inproceedings{kante:hal-01162796,
TITLE = {{Finding Paths in Grids with Forbidden Transitions}},
AUTHOR = {Kant{\'e}, Mamadou Moustapha and Moataz, Fatima Zahra and Mom{\`e}ge, Benjamin and Nisse, Nicolas},
URL = {https://hal.inria.fr/hal-01162796},
BOOKTITLE = {{WG 2015, 41st International Workshop on Graph-Theoretic Concepts in Computer Science}},
ADDRESS = {Munich, Germany},
YEAR = {2015},
MONTH = Jun,
ABSTRACT = {A transition in a graph is a pair of adjacent edges. Given a graph G = (V, E), a set of forbidden transitions F $\subseteq$ E Ã E and two vertices s, t $\in$ V , we study the problem of finding a path from s to t which uses none of the forbidden transitions of F. This means that it is forbidden for the path to consecutively use two edges forming a pair in F. The study of this problem is motivated by routing in road networks in which forbidden transitions are associated to prohibited turns as well as routing in optical networks with asymmetric nodes, which are nodes where a signal on an ingress port can only reach a subset of egress ports. If the path is not required to be elementary, the problem can be solved in polynomial time. On the other side, if the path has to be elementary, the problem is known to be NP-complete in general graphs [Szeider 2003]. In this paper, we study the problem of finding an elementary path avoiding forbidden transitions in planar graphs. We prove that the problem is NP-complete in planar graphs and particularly in grids. In addition, we show that the problem can be solved in polynomial time in graphs with bounded treewidth. More precisely, we show that there is an algorithm which solves the problem in time O((3â(k + 1)) 2k+4 n)) in n-node graphs with treewidth at most k and maximum degree â.},
PDF = {https://hal.inria.fr/hal-01162796/file/PAFT_WGV0.pdf},
HAL_ID = {hal-01162796},
HAL_VERSION = {v1},
}
-
Alvinice Kodjo,
Brigitte Jaumard,
Napoleão Nepomuceno,
Mejdi Kaddour,
and David Coudert.
Dimensioning microwave wireless networks.
In ICC 2015 : IEEE International Conference on Communications,
London, United Kingdom,
pages 2803 - 2809,
June 2015.
IEEE.
[WWW
] [PDF
]
| Abstract: |
|
We aim at dimensioning fixed broadband microwave wireless networks under unreliable channel conditions. As the transport capacity of microwave links is prone to variations due to, e.g., weather conditions, such a dimensioning requires special attention. It can be formulated as the determination of the minimum cost bandwidth assignment of the links in the network for which traffic requirements can be met with high probability, while taking into account that transport link capacities vary depending on channel conditions. The proposed optimization model represents a major step forward since we consider dynamic routing. Experimental results show that the resulting solutions can save up to 450f the bandwidth cost compared to the case where a bandwidth over-provisioning policy is uniformly applied to all links in the network planning. Comparisons with previous work also show that we can solve much larger instances in significantly shorter computing times, with a comparable level of reliability. |
@inproceedings{kodjo:hal-01198461,
TITLE = {{Dimensioning microwave wireless networks}},
AUTHOR = {Kodjo, Alvinice and Jaumard, Brigitte and Nepomuceno, Napoleão and Kaddour, Mejdi and Coudert, David},
URL = {https://hal.inria.fr/hal-01198461},
BOOKTITLE = {{ICC 2015 : IEEE International Conference on Communications}},
ADDRESS = {London, United Kingdom},
PUBLISHER = {{IEEE}},
PAGES = {2803 - 2809},
YEAR = {2015},
MONTH = Jun,
DOI = {10.1109/ICC.2015.7248751},
ABSTRACT = {We aim at dimensioning fixed broadband microwave wireless networks under unreliable channel conditions. As the transport capacity of microwave links is prone to variations due to, e.g., weather conditions, such a dimensioning requires special attention. It can be formulated as the determination of the minimum cost bandwidth assignment of the links in the network for which traffic requirements can be met with high probability, while taking into account that transport link capacities vary depending on channel conditions. The proposed optimization model represents a major step forward since we consider dynamic routing. Experimental results show that the resulting solutions can save up to 450f the bandwidth cost compared to the case where a bandwidth over-provisioning policy is uniformly applied to all links in the network planning. Comparisons with previous work also show that we can solve much larger instances in significantly shorter computing times, with a comparable level of reliability.},
PDF = {https://hal.inria.fr/hal-01198461/file/ICC_2015_Microwave_Final.pdf},
HAL_ID = {hal-01198461},
HAL_VERSION = {v1},
}
-
Bi Li,
Fatima Zahra Moataz,
Nicolas Nisse,
and Karol Suchan.
Minimum Size Tree-decompositions.
In LAGOS 2015 -- VIII Latin-American Algorithms, Graphs and Optimization Symposium,
Beberibe, Ceará, Brazil,
May 2015.
[WWW
] [PDF
]
Keywords:
Minimum size tree-decomposition,
treewidth,
NP-hard.
| Abstract: |
|
Tree-decompositions are the cornerstone of many dynamic programming algorithms for solving graph problems. Since the complexity of such algorithms generally depends exponentially on the width (size of the bags) of the decomposition, much work has been devoted to compute tree-decompositions with small width. However, practical algorithms computing tree-decompositions only exist for graphs with treewidth less than 4. In such graphs, the time-complexity of dynamic programming algorithms is dominated by the size (number of bags) of the tree-decompositions. It is then interesting to minimize the size of the tree-decompositions. In this extended abstract, we consider the problem of computing a tree-decomposition of a graph with width at most k and minimum size. We prove that the problem is NP-complete for any fixed k $\ge$ 4 and polynomial for k $\le$ 2; for k = 3, we show that it is polynomial in the class of trees and 2-connected outerplanar graphs. |
@inproceedings{li:hal-01162695,
TITLE = {{Minimum Size Tree-decompositions}},
AUTHOR = {Li, Bi and Zahra Moataz, Fatima and Nisse, Nicolas and Suchan, Karol},
URL = {https://hal.inria.fr/hal-01162695},
BOOKTITLE = {{LAGOS 2015 -- VIII Latin-American Algorithms, Graphs and Optimization Symposium}},
ADDRESS = {Beberibe, Cear{\'a}, Brazil},
YEAR = {2015},
MONTH = May,
ABSTRACT = {Tree-decompositions are the cornerstone of many dynamic programming algorithms for solving graph problems. Since the complexity of such algorithms generally depends exponentially on the width (size of the bags) of the decomposition, much work has been devoted to compute tree-decompositions with small width. However, practical algorithms computing tree-decompositions only exist for graphs with treewidth less than 4. In such graphs, the time-complexity of dynamic programming algorithms is dominated by the size (number of bags) of the tree-decompositions. It is then interesting to minimize the size of the tree-decompositions. In this extended abstract, we consider the problem of computing a tree-decomposition of a graph with width at most k and minimum size. We prove that the problem is NP-complete for any fixed k $\ge$ 4 and polynomial for k $\le$ 2; for k = 3, we show that it is polynomial in the class of trees and 2-connected outerplanar graphs.},
KEYWORDS = {Minimum size tree-decomposition ; treewidth ; NP-hard},
PDF = {https://hal.inria.fr/hal-01162695/file/MSTD.pdf},
HAL_ID = {hal-01162695},
HAL_VERSION = {v1},
}
-
Nicolas Nisse,
Alexandre Salch,
and Valentin Weber.
Comment appliquer les chaînes augmentantes pour atterrir a l'heure ?.
In ALGOTEL 2015 - 17èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications,
Beaune, France,
June 2015.
[WWW
] [PDF
]
| Abstract: |
|
Lorsqu'un avion approche d'un a{\'e}roport , il dispose d'un intervalle de temps (slot) tr{\`e}s limit{\'e} (une vingtaine de minutes) pour atterrir. Si l'avion a du retard {\`a} cause des conditions m{\'e}t{\'e}orologiques ({\`a} cause du retard d'autres avions, ou si lui-m{\^e}me a eu du retard au d{\'e}collage), il perd son slot et il faut qu'un nouveau slot lui soit attribu{\'e} par les contr{\^o}leurs des op{\'e}rations de la compagnie a{\'e}rienne. Cependant, les slots d'atterrissage sont une denr{\'e}e rare et, pour qu'un avion A puisse atterrir a l'heure, les contr{\^o}leurs doivent r{\'e}gul{\`i}{\`e}rement modifier l'attribution des slots d'autres avions afin d'affecter un slot compatible avec l'heure d'arriv{\'e}e de l'avion A. Ce probl{\`e}me peut ais{\'e}ment etre mod{\'e}lis{\'e} comme un probl{\`e}me de couplage dans un graphe biparti. Malheureusement, d{\^u} au syst{\`e}me mis en place pour permettre ces {\'e}changes, les contr{\^o}leurs a{\'e}riens ne peuvent effectuer leurs modifications qu'en effectuant deux types d'op{\'e}rations : soit attribuer {\`a} l'avion A un slot libre, soit donner {\`a} l'avion A le slot d'un avion B et attribuer un slot libre {\`a} ce dernier. Le probl{\`e}me devient donc le suivant. Soit G un graphe et M un couplage (ensemble d'ar{\^e}tes deux-{\`a}-deux disjointes) de G. Comment calculer un couplage maximum pouvant etre obtenu {\`a} partir de M en utilisant uniquement des chemins augmentants de longueur au plus k ? Ce probl{\`e}me a d{\'e}j{\`a} {\'e}t{\'e} {\'e}tudi{\'e} dans le cadre des r{\'e}seaux sans-fil car il fournit une simple approximation au probl{\`e}me de couplage maximum. Nous prouvons que, pour k = 3, ce probl{\`e}me peut {\^e}tre r{\'e}solu en temps polynomial, fournissant ainsi un algorithme efficace pour les contr{\^o}leurs a{\'e}riens. Nous prouvons ensuite que, pour tout entier impair k $\ge$ 5, le probl{\`e}me est NP-complet dans les graphes bipartis planaires de degr{\'e} au plus 3. |
@inproceedings{nisse:hal-01144674,
TITLE = {{Comment appliquer les cha{\^i}nes augmentantes pour atterrir a l'heure ?}},
AUTHOR = {Nisse, Nicolas and Salch, Alexandre and Weber, Valentin},
URL = {https://hal.archives-ouvertes.fr/hal-01144674},
BOOKTITLE = {{ALGOTEL 2015 - 17{\`e}mes Rencontres Francophones sur les Aspects Algorithmiques des T{\'e}l{\'e}communications}},
ADDRESS = {Beaune, France},
YEAR = {2015},
MONTH = Jun,
ABSTRACT = {Lorsqu'un avion approche d'un a{\'e}roport , il dispose d'un intervalle de temps (slot) tr{\`e}s limit{\'e} (une vingtaine de minutes) pour atterrir. Si l'avion a du retard {\`a} cause des conditions m{\'e}t{\'e}orologiques ({\`a} cause du retard d'autres avions, ou si lui-m{\^e}me a eu du retard au d{\'e}collage), il perd son slot et il faut qu'un nouveau slot lui soit attribu{\'e} par les contr{\^o}leurs des op{\'e}rations de la compagnie a{\'e}rienne. Cependant, les slots d'atterrissage sont une denr{\'e}e rare et, pour qu'un avion A puisse atterrir a l'heure, les contr{\^o}leurs doivent r{\'e}gul{\`i}{\`e}rement modifier l'attribution des slots d'autres avions afin d'affecter un slot compatible avec l'heure d'arriv{\'e}e de l'avion A. Ce probl{\`e}me peut ais{\'e}ment etre mod{\'e}lis{\'e} comme un probl{\`e}me de couplage dans un graphe biparti. Malheureusement, d{\^u} au syst{\`e}me mis en place pour permettre ces {\'e}changes, les contr{\^o}leurs a{\'e}riens ne peuvent effectuer leurs modifications qu'en effectuant deux types d'op{\'e}rations : soit attribuer {\`a} l'avion A un slot libre, soit donner {\`a} l'avion A le slot d'un avion B et attribuer un slot libre {\`a} ce dernier. Le probl{\`e}me devient donc le suivant. Soit G un graphe et M un couplage (ensemble d'ar{\^e}tes deux-{\`a}-deux disjointes) de G. Comment calculer un couplage maximum pouvant etre obtenu {\`a} partir de M en utilisant uniquement des chemins augmentants de longueur au plus k ? Ce probl{\`e}me a d{\'e}j{\`a} {\'e}t{\'e} {\'e}tudi{\'e} dans le cadre des r{\'e}seaux sans-fil car il fournit une simple approximation au probl{\`e}me de couplage maximum. Nous prouvons que, pour k = 3, ce probl{\`e}me peut {\^e}tre r{\'e}solu en temps polynomial, fournissant ainsi un algorithme efficace pour les contr{\^o}leurs a{\'e}riens. Nous prouvons ensuite que, pour tout entier impair k $\ge$ 5, le probl{\`e}me est NP-complet dans les graphes bipartis planaires de degr{\'e} au plus 3.},
PDF = {https://hal.archives-ouvertes.fr/hal-01144674/file/amadeusV5_revision.pdf},
HAL_ID = {hal-01144674},
HAL_VERSION = {v1},
}
-
Myriana Rifai,
Nicolas Huin,
Christelle Caillouet,
Frédéric Giroire,
Dino Lopez Pacheco,
Joanna Moulierac,
and Guillaume Urvoy-Keller.
Too many SDN rules? Compress them with MINNIE.
In IEEE GLOBECOM,
San diego, United States,
December 2015.
IEEE.
[WWW
] [PDF
]
Keywords:
Software defined networks,
experimentation,
TCAM,
number of rules.
| Abstract: |
|
Software Defined Networking (SDN) is gaining momentum with the support of major manufacturers. While it brings flexibility in the management of flows within the data center fabric, this flexibility comes at the cost of smaller routing table capacities. In this paper, we investigate compression techniques to reduce the forwarding information base (FIB) of SDN switches. We validate our algorithm, called MINNIE, on a real testbed able to emulate a 20 switches fat tree architecture. We demonstrate that even with a small number of clients, the limit in terms of number of rules is reached if no compression is performed, increasing the delay of all new incoming flows. MINNIE, on the other hand, reduces drastically the number of rules that need to be stored with a limited impact on the packet loss rate. We also evaluate the actual switching and reconfiguration times and the delay introduced by the communications with the controller. |
@inproceedings{rifai:hal-01203020,
TITLE = {{Too many SDN rules? Compress them with MINNIE}},
AUTHOR = {Rifai, Myriana and Huin, Nicolas and Caillouet, Christelle and Giroire, Fr{\'e}d{\'e}ric and Lopez Pacheco, Dino and Moulierac, Joanna and Urvoy-Keller, Guillaume},
URL = {https://hal.inria.fr/hal-01203020},
BOOKTITLE = {{IEEE GLOBECOM}},
ADDRESS = {San diego, United States},
ORGANIZATION = {{IEEE}},
YEAR = {2015},
MONTH = Dec,
ABSTRACT = {Software Defined Networking (SDN) is gaining momentum with the support of major manufacturers. While it brings flexibility in the management of flows within the data center fabric, this flexibility comes at the cost of smaller routing table capacities. In this paper, we investigate compression techniques to reduce the forwarding information base (FIB) of SDN switches. We validate our algorithm, called MINNIE, on a real testbed able to emulate a 20 switches fat tree architecture. We demonstrate that even with a small number of clients, the limit in terms of number of rules is reached if no compression is performed, increasing the delay of all new incoming flows. MINNIE, on the other hand, reduces drastically the number of rules that need to be stored with a limited impact on the packet loss rate. We also evaluate the actual switching and reconfiguration times and the delay introduced by the communications with the controller.},
KEYWORDS = {Software defined networks ; experimentation ; TCAM ; number of rules},
PDF = {https://hal.inria.fr/hal-01203020/file/gc2015 amera%20ready.pdf},
HAL_ID = {hal-01203020},
HAL_VERSION = {v1},
}
-
Fatima Zahra Moataz.
On Spectrum Assignment in Elastic Optical Tree-Networks.
In ALGOTEL 2015 - 17èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications,
Beaune, France,
June 2015.
[WWW
] [PDF
]
Keywords:
interval coloring,
routing and spectrum assignment,
optical networks,
Approximation algorithms.
| Abstract: |
|
Pour r{\'e}pondre {\`a} la demande croissante du trafic d'Internet, une nouvelle g{\'e}n{\'e}ration de r{\'e}seaux optiques est en cours de d{\'e}veloppement ; les r{\'e}seaux optiques {\'e}lastiques (EONs). La technologie EON permet d'utiliser le spectre optique de mani{\`e}re efficace et flexible. Cette flexibilit{\'e} promet de r{\'e}soudre les difficult{\'e}s li{\'e}es {\`a} la croissance et l'h{\'e}t{\'e}rog{\'e}n{\'e}it{\'e} du trafic. Toutefois, elle rend le probl{\`e}me d'allocation de ressources plus complexe. Dans ce papier, nous traitons le probl{\`e}me d'allocation de spectre dans les r{\'e}seaux optiques {\'e}lastiques en arbre. Dans ce type de r{\'e}seau , bien que le routage soit fix{\'e}, l'allocation de spectre est NP-difficile. Nous pr{\'e}sentons des r{\'e}sultats de difficult{\'e} et d'approximation pour des cas sp{\'e}ciaux o{\`u} le r{\'e}seau est une {\'e}toile ou un arbre binaire. |
@inproceedings{zahramoataz:hal-01142818,
TITLE = {{On Spectrum Assignment in Elastic Optical Tree-Networks}},
AUTHOR = {Zahra Moataz, Fatima},
URL = {https://hal.archives-ouvertes.fr/hal-01142818},
BOOKTITLE = {{ALGOTEL 2015 - 17{\`e}mes Rencontres Francophones sur les Aspects Algorithmiques des T{\'e}l{\'e}communications}},
ADDRESS = {Beaune, France},
YEAR = {2015},
MONTH = Jun,
ABSTRACT = {Pour r{\'e}pondre {\`a} la demande croissante du trafic d'Internet, une nouvelle g{\'e}n{\'e}ration de r{\'e}seaux optiques est en cours de d{\'e}veloppement ; les r{\'e}seaux optiques {\'e}lastiques (EONs). La technologie EON permet d'utiliser le spectre optique de mani{\`e}re efficace et flexible. Cette flexibilit{\'e} promet de r{\'e}soudre les difficult{\'e}s li{\'e}es {\`a} la croissance et l'h{\'e}t{\'e}rog{\'e}n{\'e}it{\'e} du trafic. Toutefois, elle rend le probl{\`e}me d'allocation de ressources plus complexe. Dans ce papier, nous traitons le probl{\`e}me d'allocation de spectre dans les r{\'e}seaux optiques {\'e}lastiques en arbre. Dans ce type de r{\'e}seau , bien que le routage soit fix{\'e}, l'allocation de spectre est NP-difficile. Nous pr{\'e}sentons des r{\'e}sultats de difficult{\'e} et d'approximation pour des cas sp{\'e}ciaux o{\`u} le r{\'e}seau est une {\'e}toile ou un arbre binaire.},
KEYWORDS = {interval coloring ; routing and spectrum assignment ; optical networks ; Approximation algorithms},
PDF = {https://hal.archives-ouvertes.fr/hal-01142818/file/SA_FinalVersion.pdf},
HAL_ID = {hal-01142818},
HAL_VERSION = {v1},
}
-
Julio Araujo,
Frédéric Havet,
Claudia Linhares Sales,
and Ana Silva.
Proper orientation of cacti.
Research Report RR-8833,
INRIA Sophia Antipolis - Méditerranée,
December 2015.
[WWW
] [PDF
]
Keywords:
proper orientation,
graph coloring,
cactus graph,
claw-free graph.
| Abstract: |
|
An orientation of a graph is proper if two adjacent vertices have different indegrees. We prove that every cactus admits a proper orientation with maximum indegree at most 7. We also prove that the bound 7 is tight by showing a cactus having no proper orientation with maximum indegree less than 7. We also prove that any planar claw-free graph has a proper orientation with maximum indegree at most 6 and that this bound can also be attained. |
@techreport{araujo:hal-01247014,
TITLE = {{Proper orientation of cacti}},
AUTHOR = {Araujo, Julio and Havet, Fr{\'e}d{\'e}ric and Linhares Sales, Claudia and Silva, Ana},
URL = {https://hal.inria.fr/hal-01247014},
TYPE = {Research Report},
NUMBER = {RR-8833},
PAGES = {17},
INSTITUTION = {{INRIA Sophia Antipolis - M{\'e}diterran{\'e}e}},
YEAR = {2015},
MONTH = Dec,
ABSTRACT = {An orientation of a graph is proper if two adjacent vertices have different indegrees. We prove that every cactus admits a proper orientation with maximum indegree at most 7. We also prove that the bound 7 is tight by showing a cactus having no proper orientation with maximum indegree less than 7. We also prove that any planar claw-free graph has a proper orientation with maximum indegree at most 6 and that this bound can also be attained.},
KEYWORDS = {proper orientation ; graph coloring ; cactus graph ; claw-free graph},
PDF = {https://hal.inria.fr/hal-01247014/file/RR-8833.pdf},
HAL_ID = {hal-01247014},
HAL_VERSION = {v1},
}
-
Jean-Claude Bermond and Fatima Zahra Moataz.
On Spectrum Assignment in Elastic Optical Tree-Networks.
Research Report,
Inria Sophia Antipolis ; Université Nice Sophia Antipolis,
February 2015.
[WWW
] [PDF
]
Keywords:
Approximation algorithms,
routing and spectrum assignment,
optical networks,
interval coloring.
| Abstract: |
|
To face the explosion of the Internet traffic, a new generation of optical networks is being developed; the Elastic optical Networks (EONs). The aim with EONs is to use the optical spectrum efficiently and flexibly. The benefit of the flexibility is, however, accompanied by more difficulty in the resource allocation problems. In this report, we study the problem of Spectrum Allocation in Elastic Optical Tree-Networks. In trees, even though the routing is fixed, the spectrum allocation is NP-hard. We survey the complexity and approximability results that have been established for the SA in trees and prove new results for stars and binary trees. |
@techreport{bermond:hal-01116321,
TITLE = {{On Spectrum Assignment in Elastic Optical Tree-Networks}},
AUTHOR = {Bermond, Jean-Claude and Moataz, Fatima Zahra},
URL = {https://hal.inria.fr/hal-01116321},
TYPE = {Research Report},
INSTITUTION = {{Inria Sophia Antipolis ; Universit{\'e} Nice Sophia Antipolis}},
YEAR = {2015},
MONTH = Feb,
ABSTRACT = {To face the explosion of the Internet traffic, a new generation of optical networks is being developed; the Elastic optical Networks (EONs). The aim with EONs is to use the optical spectrum efficiently and flexibly. The benefit of the flexibility is, however, accompanied by more difficulty in the resource allocation problems. In this report, we study the problem of Spectrum Allocation in Elastic Optical Tree-Networks. In trees, even though the routing is fixed, the spectrum allocation is NP-hard. We survey the complexity and approximability results that have been established for the SA in trees and prove new results for stars and binary trees.},
KEYWORDS = {Approximation algorithms ; routing and spectrum assignment ; optical networks ; interval coloring},
PDF = {https://hal.inria.fr/hal-01116321/file/SAinTrees.pdf},
HAL_ID = {hal-01116321},
HAL_VERSION = {v4},
}
-
David Coudert and Guillaume Ducoffe.
Data center interconnection networks are not hyperbolic.
Research Report,
Inria Sophia Antipolis ; I3S ; Université Nice Sophia Antipolis ; CNRS,
May 2015.
[WWW
] [PDF
]
| Abstract: |
|
Topologies for data center networks have been proposed in the literature through various graph classes and operations. A common trait to most existing designs is that they enhance the symmetric properties of the underlying graphs. Indeed, symmetry is a desirable property for interconnection networks because it minimizes congestion problems and it allows each entity to run the same routing protocol. However, despite sharing similarities these topologies all come with their own routing protocol. Recently, generic routing schemes have been introduced which can be implemented for any interconnection networks. The performances of such universal routing schemes are intimately related to the hyperbolicity of the topology. Roughly, graph hyperbolicity is a metric parameter which measures how close is the shortest-path metric of a graph from a tree metric (the smaller gap the better). Motivated by the good performances in practice of these new routing schemes, we propose the first general study of the hyperbolicity of data center interconnection networks. Our findings are disappointingly negative: we prove that the hyperbolicity of most data center topologies scales linearly with their diameter, that it the worst-case possible for hyperbolicity. To obtain these results, we introduce original connection between hyperbolicity and the properties of the endomorphism monoid of a graph. In particular, our results extend to all vertex and edge-transitive graphs. Additional results are obtained for de Bruijn and Kautz graphs, grid-like graphs and networks from the so-called Cayley model. |
@techreport{coudert:hal-01149203,
TITLE = {{Data center interconnection networks are not hyperbolic}},
AUTHOR = {Coudert, David and Ducoffe, Guillaume},
URL = {https://hal.inria.fr/hal-01149203},
TYPE = {Research Report},
PAGES = {23},
INSTITUTION = {{Inria Sophia Antipolis ; I3S ; Universit{\'e} Nice Sophia Antipolis ; CNRS}},
YEAR = {2015},
MONTH = May,
ABSTRACT = {Topologies for data center networks have been proposed in the literature through various graph classes and operations. A common trait to most existing designs is that they enhance the symmetric properties of the underlying graphs. Indeed, symmetry is a desirable property for interconnection networks because it minimizes congestion problems and it allows each entity to run the same routing protocol. However, despite sharing similarities these topologies all come with their own routing protocol. Recently, generic routing schemes have been introduced which can be implemented for any interconnection networks. The performances of such universal routing schemes are intimately related to the hyperbolicity of the topology. Roughly, graph hyperbolicity is a metric parameter which measures how close is the shortest-path metric of a graph from a tree metric (the smaller gap the better). Motivated by the good performances in practice of these new routing schemes, we propose the first general study of the hyperbolicity of data center interconnection networks. Our findings are disappointingly negative: we prove that the hyperbolicity of most data center topologies scales linearly with their diameter, that it the worst-case possible for hyperbolicity. To obtain these results, we introduce original connection between hyperbolicity and the properties of the endomorphism monoid of a graph. In particular, our results extend to all vertex and edge-transitive graphs. Additional results are obtained for de Bruijn and Kautz graphs, grid-like graphs and networks from the so-called Cayley model.},
PDF = {https://hal.inria.fr/hal-01149203/file/research-report-20150506.pdf},
HAL_ID = {hal-01149203},
HAL_VERSION = {v1},
}
-
Frédéric Giroire,
Stéphane Pérennes,
and Issam Tahiri.
Graphs with optimal forwarding indices: What is the best throughput you can get with a given number of edges?.
Research Report RR-8752,
INRIA Sophia Antipolis ; INRIA,
June 2015.
[WWW
] [PDF
]
Keywords:
graphs,
forwarding index,
routing,
design problem,
energy efficiency,
extremal graphs.
| Abstract: |
|
The (edge) forwarding index of a graph is the minimum, over all possible routings of all the demands, of the maximum load of an edge. This metric is of a great interest since it captures the notion of global congestion in a precise way: the lesser the forwarding-index, the lesser the congestion. In this paper, we study the following design question: Given a number e of edges and a number n of vertices, what is the least congested graph that we can construct? and what forwarding-index can we achieve? Our problem has some distant similarities with the well-known (â,D) problem, and we sometimes build upon results obtained on it. The goal of this paper is to study how to build graphs with low forwarding indices and to understand how the number of edges impacts the forwarding index. We answer here these questions for different families of graphs: general graphs, graphs with bounded degree, sparse graphs with a small number of edges by providing constructions, most of them asymptotically optimal. Hence, our results allow to understand how the forwarding-index drops when edges are added to a graph and also to determine what is the best (i.e least congested) structure with e edges. Doing so, we partially answer the practical problem that initially motivated our work: If an operator wants to power only e links of its network, in order to reduce the energy consumption (or wiring cost) of its networks, what should be those links and what performance can be expected? |
@techreport{giroire:hal-01172725,
TITLE = {{Graphs with optimal forwarding indices: What is the best throughput you can get with a given number of edges?}},
AUTHOR = {Giroire, Fr{\'e}d{\'e}ric and P{\'e}rennes, St{\'e}phane and Tahiri, Issam},
URL = {https://hal.inria.fr/hal-01172725},
TYPE = {Research Report},
NUMBER = {RR-8752},
INSTITUTION = {{INRIA Sophia Antipolis ; INRIA}},
YEAR = {2015},
MONTH = Jun,
ABSTRACT = {The (edge) forwarding index of a graph is the minimum, over all possible routings of all the demands, of the maximum load of an edge. This metric is of a great interest since it captures the notion of global congestion in a precise way: the lesser the forwarding-index, the lesser the congestion. In this paper, we study the following design question: Given a number e of edges and a number n of vertices, what is the least congested graph that we can construct? and what forwarding-index can we achieve? Our problem has some distant similarities with the well-known (â,D) problem, and we sometimes build upon results obtained on it. The goal of this paper is to study how to build graphs with low forwarding indices and to understand how the number of edges impacts the forwarding index. We answer here these questions for different families of graphs: general graphs, graphs with bounded degree, sparse graphs with a small number of edges by providing constructions, most of them asymptotically optimal. Hence, our results allow to understand how the forwarding-index drops when edges are added to a graph and also to determine what is the best (i.e least congested) structure with e edges. Doing so, we partially answer the practical problem that initially motivated our work: If an operator wants to power only e links of its network, in order to reduce the energy consumption (or wiring cost) of its networks, what should be those links and what performance can be expected?},
KEYWORDS = {graphs ; forwarding index ; routing ; design problem ; energy efficiency ; extremal graphs},
PDF = {https://hal.inria.fr/hal-01172725/file/RR-8752.pdf},
HAL_ID = {hal-01172725},
HAL_VERSION = {v1},
}
-
Frédéric Havet,
A. Karolinna Maia de Oliveira,
and Bojan Mohar.
Finding a subdivision of a prescribed digraph of order 4.
Research Report RR-8773,
INRIA,
September 2015.
[WWW
] [PDF
]
| Abstract: |
|
The problem of when a given digraph contains a subdivision of a fixed digraph F is considered.Bang-Jensen et al. [2] laid out foundations for approaching this problem from the algorithmic pointof view. In this paper we give further support to several open conjectures and speculations about algorithmiccomplexity of finding F-subdivisions. In particular, up to 5 exceptions, we completely classify forwhich 4-vertex digraphs F, the F-subdivision problem is polynomial-time solvable and for which it is NPcomplete.While all NP-hardness proofs are made by reduction from some version of the 2-linkage problemin digraphs, some of the polynomial-time solvable cases involve relatively complicated algorithms. |
@techreport{havet:hal-01202650,
TITLE = {{Finding a subdivision of a prescribed digraph of order 4}},
AUTHOR = {Havet, Fr{\'e}d{\'e}ric and Maia de Oliveira, A. Karolinna and Mohar, Bojan},
URL = {https://hal.inria.fr/hal-01202650},
TYPE = {Research Report},
NUMBER = {RR-8773},
INSTITUTION = {{INRIA}},
YEAR = {2015},
MONTH = Sep,
ABSTRACT = {The problem of when a given digraph contains a subdivision of a fixed digraph F is considered.Bang-Jensen et al. [2] laid out foundations for approaching this problem from the algorithmic pointof view. In this paper we give further support to several open conjectures and speculations about algorithmiccomplexity of finding F-subdivisions. In particular, up to 5 exceptions, we completely classify forwhich 4-vertex digraphs F, the F-subdivision problem is polynomial-time solvable and for which it is NPcomplete.While all NP-hardness proofs are made by reduction from some version of the 2-linkage problemin digraphs, some of the polynomial-time solvable cases involve relatively complicated algorithms.},
PDF = {https://hal.inria.fr/hal-01202650/file/RR-8773.pdf},
HAL_ID = {hal-01202650},
HAL_VERSION = {v1},
}
-
Seong-Gyun Jeong,
Yuliya Tarabalka,
Nicolas Nisse,
and Josiane Zerubia.
Inference of Curvilinear Structure based on Learning a Ranking Function and Graph Theory.
Research Report RR-8789,
Inria Sophia Antipolis,
2015.
[WWW
] [PDF
]
| Abstract: |
|
To detect curvilinear structures in natural images, we propose a novel rankinglearning system and an abstract curvilinear shape inference algorithm based on graph theory. Weanalyze the curvilinear structures as a set of small line segments. In this work, the rankings ofthe line segments are exploited to systematize the topological feature of the curvilinear structures.Structured Support Vector Machine is employed to learn the ranking function that predicts thecorrespondence of the given line segments and the latent curvilinear structures. We first extractcurvilinear features using morphological profiles and steerable filtering responses. Also, we proposean orientation-aware feature descriptor and a feature grouping operator to improve the structuralintegrity during the learning process. To infer the curvilinear structure, we build a graph based onthe output rankings of the line segments. We progressively reconstruct the curvilinear structureby looking for paths between remote vertices in the graph. Experimental results show that theproposed algorithm faithfully detects the curvilinear structures within various datasets. |
@techreport{jeong:hal-01214932,
TITLE = {{Inference of Curvilinear Structure based on Learning a Ranking Function and Graph Theory}},
AUTHOR = {Jeong, Seong-Gyun and Tarabalka, Yuliya and Nisse, Nicolas and Zerubia, Josiane},
URL = {https://hal.inria.fr/hal-01214932},
TYPE = {Research Report},
NUMBER = {RR-8789},
INSTITUTION = {{Inria Sophia Antipolis}},
YEAR = {2015},
ABSTRACT = {To detect curvilinear structures in natural images, we propose a novel rankinglearning system and an abstract curvilinear shape inference algorithm based on graph theory. Weanalyze the curvilinear structures as a set of small line segments. In this work, the rankings ofthe line segments are exploited to systematize the topological feature of the curvilinear structures.Structured Support Vector Machine is employed to learn the ranking function that predicts thecorrespondence of the given line segments and the latent curvilinear structures. We first extractcurvilinear features using morphological profiles and steerable filtering responses. Also, we proposean orientation-aware feature descriptor and a feature grouping operator to improve the structuralintegrity during the learning process. To infer the curvilinear structure, we build a graph based onthe output rankings of the line segments. We progressively reconstruct the curvilinear structureby looking for paths between remote vertices in the graph. Experimental results show that theproposed algorithm faithfully detects the curvilinear structures within various datasets.},
PDF = {https://hal.inria.fr/hal-01214932/file/RR-8789.pdf},
HAL_ID = {hal-01214932},
HAL_VERSION = {v1},
}
-
Mamadou Moustapha Kanté,
Fatima Zahra Moataz,
Benjamin Momège,
and Nicolas Nisse.
Finding Paths in Grids with Forbidden Transitions.
Research Report,
Inria Sophia Antipolis ; Univeristé Nice Sophia Antipolis ; CNRS,
February 2015.
[WWW
] [PDF
]
Keywords:
asymmetric nodes,
grid,
planar graphs,
forbidden transitions.
| Abstract: |
|
Une transition dans un graphe est une paire d'ar{\^e}tes incidente a un m{\^e}me sommet. Etant donn{\'e}s un graphe G = (V, E), deux sommets s, t $\in$ V et un ensemble associ{\'e} de transitions interdites F $\subseteq$ E Ã E, le probl{\`e}me de chemin {\'e}vitant des transitions interdites consiste {\`a} d{\'e}cider sâil existe un chemin {\'e}l{\'e}mentaire de s {\`a} t qui nâutilise aucune des transitions de F. Câest-{\`a}-dire quâil est interdit dâemprunter cons{\'e}cutivement deux ar{\^e}tes qui soient une paire de F. Ce probl{\`e}me est motiv{\'e} par le routage dans les r{\'e}seaux routiers (o{\`u} une transition interdite repr{\'e}sente une interdiction de tourner) ainsi que dans les r{\'e}seaux optiques avec des noeuds asym{\'e}triques. Nous prouvons que le probl{\`e}me est NP-difficile dans les graphes planaires et plus particuli{\`e}rement dans les grilles. Nous montrons {\'e}galement que le probl{\`e}me peut {\^e}tre r{\'e}solu en temps polynomial dans la classe des graphes de largeur arborescente born{\'e}e. |
@techreport{kante:hal-01115395,
TITLE = {{Finding Paths in Grids with Forbidden Transitions}},
AUTHOR = {Kant{\'e}, Mamadou Moustapha and Moataz, Fatima Zahra and Mom{\`e}ge, Benjamin and Nisse, Nicolas},
URL = {https://hal.inria.fr/hal-01115395},
TYPE = {Research Report},
INSTITUTION = {{Inria Sophia Antipolis ; Univerist{\'e} Nice Sophia Antipolis ; CNRS}},
YEAR = {2015},
MONTH = Feb,
ABSTRACT = {Une transition dans un graphe est une paire d'ar{\^e}tes incidente a un m{\^e}me sommet. Etant donn{\'e}s un graphe G = (V, E), deux sommets s, t $\in$ V et un ensemble associ{\'e} de transitions interdites F $\subseteq$ E Ã E, le probl{\`e}me de chemin {\'e}vitant des transitions interdites consiste {\`a} d{\'e}cider sâil existe un chemin {\'e}l{\'e}mentaire de s {\`a} t qui nâutilise aucune des transitions de F. Câest-{\`a}-dire quâil est interdit dâemprunter cons{\'e}cutivement deux ar{\^e}tes qui soient une paire de F. Ce probl{\`e}me est motiv{\'e} par le routage dans les r{\'e}seaux routiers (o{\`u} une transition interdite repr{\'e}sente une interdiction de tourner) ainsi que dans les r{\'e}seaux optiques avec des noeuds asym{\'e}triques. Nous prouvons que le probl{\`e}me est NP-difficile dans les graphes planaires et plus particuli{\`e}rement dans les grilles. Nous montrons {\'e}galement que le probl{\`e}me peut {\^e}tre r{\'e}solu en temps polynomial dans la classe des graphes de largeur arborescente born{\'e}e.},
KEYWORDS = {asymmetric nodes ; grid ; planar graphs ; forbidden transitions},
PDF = {https://hal.inria.fr/hal-01115395/file/PAFT.pdf},
HAL_ID = {hal-01115395},
HAL_VERSION = {v1},
}
-
Nicolas Nisse,
Alexandre Salch,
and Valentin Weber.
Recovery of disrupted airline operations using k-Maximum Matching in Graphs.
Research Report RR-8679,
Inria Sophia Antipolis ; INRIA,
February 2015.
[WWW
] [PDF
]
| Abstract: |
|
When an aircraft is approaching an airport, it gets a short time interval (called {\it slot}) that it can use to land. If the landing of the aircraft is delayed (because of bad weather, or if it arrives late, or if other aircrafts have to land first), it looses its slot and Air traffic controllers have to assign it a new slot. However, slots for landing are a scare resource of the airports and, to avoid that an aircraft waits too much time, Air traffic controllers have to regularly modify the assignment of the slots of the aircrafts. Unfortunately, for legal and economical reasons, Air traffic controllers can modify the slot-assignment only using two kind of operations: either assign to aircraft $A$ a slot that was free, or give to $A$ the slot of another aircraft $B$ and assign to $B$ a free slot. The problem is then the following.Let $k\geq 1$ be an odd integer and let $G$ be a graph and $M$ be a matching (set of pairwise disjoint edges) of $G$. What is the maximum size of a matching that can be obtained from $M$ by using only augmenting paths of length at most $k$? Moreover, how to compute such a maximum matching? This problem has already been studied in the context of wireless networks, mainly because it provides a simple approximation for the classical matching problem. We prove that this problem can be solved in polynomial-time when $k\leq 3$. Then, we show that, for any odd integer $k\geq 5$, the problem is NP-complete in planar bipartite graphs with maximum degree at most $3$. |
@techreport{nisse:hal-01116487,
TITLE = {{Recovery of disrupted airline operations using k-Maximum Matching in Graphs}},
AUTHOR = {Nisse, Nicolas and Salch, Alexandre and Weber, Valentin},
URL = {https://hal.inria.fr/hal-01116487},
TYPE = {Research Report},
NUMBER = {RR-8679},
INSTITUTION = {{Inria Sophia Antipolis ; INRIA}},
YEAR = {2015},
MONTH = Feb,
ABSTRACT = {When an aircraft is approaching an airport, it gets a short time interval (called {\it slot}) that it can use to land. If the landing of the aircraft is delayed (because of bad weather, or if it arrives late, or if other aircrafts have to land first), it looses its slot and Air traffic controllers have to assign it a new slot. However, slots for landing are a scare resource of the airports and, to avoid that an aircraft waits too much time, Air traffic controllers have to regularly modify the assignment of the slots of the aircrafts. Unfortunately, for legal and economical reasons, Air traffic controllers can modify the slot-assignment only using two kind of operations: either assign to aircraft $A$ a slot that was free, or give to $A$ the slot of another aircraft $B$ and assign to $B$ a free slot. The problem is then the following.Let $k\geq 1$ be an odd integer and let $G$ be a graph and $M$ be a matching (set of pairwise disjoint edges) of $G$. What is the maximum size of a matching that can be obtained from $M$ by using only augmenting paths of length at most $k$? Moreover, how to compute such a maximum matching? This problem has already been studied in the context of wireless networks, mainly because it provides a simple approximation for the classical matching problem. We prove that this problem can be solved in polynomial-time when $k\leq 3$. Then, we show that, for any odd integer $k\geq 5$, the problem is NP-complete in planar bipartite graphs with maximum degree at most $3$.},
PDF = {https://hal.inria.fr/hal-01116487/file/RR-8679.pdf},
HAL_ID = {hal-01116487},
HAL_VERSION = {v1},
}
