Christelle Caillouet, Florian Huc, Nicolas Nisse, Stéphane Pérennes, Hervé Rivano
Abstract—In this work, we study the problem of routing packets between undifferentiated sources and sinks in a network modeled by a multigraph. We consider a distributed and local algorithm that...
Improper colouring of weighted grid and hexagonal graphs (2010)
Bermond, Jean-Claude, Havet, Frédéric, Huc, Florian, Linhares Sales, Claudia
We study a weighted improper colouring problem on graph, and in particular of triangular and hexagonal grid graphs. This problem is motivated by a frequency allocation problem. We propose...
Improper colouring of weighted grid and hexagonal graphs (2010)
Bermond, Jean-Claude, Havet, Frédéric, Huc, Florian, Linhares Sales, Claudia
We study a weighted improper colouring problem on graph, and in particular of triangular and hexagonal grid graphs. This problem is motivated by a frequency allocation problem. We propose...
Minimal selectors and fault tolerant networks (2010)
Amini, Omid, Giroire, Frédéric, Huc, Florian, Pérennes, Stéphane
In this paper we study a combinatorial optimization problem issued from on-board networks in satellites. In this kind of networks the entering signals (inputs) should be routed to amplifiers...
Minimal selectors and fault tolerant networks (2010)
Amini, Omid, Giroire, Frédéric, Huc, Florian, Pérennes, Stéphane
In this paper we study a combinatorial optimization problem issued from on-board networks in satellites. In this kind of networks the entering signals (inputs) should be routed to amplifiers...
Subgraphs of quasi-random oriented graphs (2009)
Amini, Omid, Griffiths, Simon, Huc, Florian
One cannot guarantee the presence of an oriented four-cycle in an oriented graph $D$ simply by demanding it has many edges, as an acyclic orientation of the complete graph on $n$ vertices has...
VRAC: Simulation Results #1 (2009)
In order to make full use of geographic routing techniques developed for large scale networks, nodes must be localized. However, localization and virtual localization techniques in sensor networks...
In order to make full use of geographic routing techniques developed for large scale networks, nodes must be localized. However, localization and virtual localization techniques in sensor networks...
Stability of a local greedy distributed routing algorithm (2009)
Huc, Florian, Molle, Christelle, Nisse, Nicolas, Pérennes, Stéphane, Rivano, Hervé
In this work, we study the problem of routing packets between undifferentiated sources and sinks in a network modeled by a multigraph. We provide a distributed and local algorithm that transmits...
Stability of a local greedy distributed routing algorithm (2009)
Huc, Florian, Molle, Christelle, Nisse, Nicolas, Pérennes, Stéphane, Rivano, Hervé
In this work, we study the problem of routing packets between undifferentiated sources and sinks in a network modeled by a multigraph. We provide a distributed and local algorithm that transmits...
Reconfiguration dans les réseaux optiques (2009)
Coudert, David, Huc, Florian, Mazauric, Dorian, Nisse, Nicolas, Sereni, Jean-Sébastien
L'évolution permanente du trafic, les opérations de maintenance et l'existence de pannes dans les réseaux WDM, obligent à rerouter régulièrement des connexions. Les nouvelles demandes de...
Reconfiguration dans les réseaux optiques (2009)
Coudert, David, Huc, Florian, Mazauric, Dorian, Nisse, Nicolas, Sereni, Jean-Sébastien
L'évolution permanente du trafic, les opérations de maintenance et l'existence de pannes dans les réseaux WDM, obligent à rerouter régulièrement des connexions. Les nouvelles demandes de...
Stability of a local greedy distributed routing algorithm (2009)
Huc, Florian, Molle, Christelle, Nisse, Nicolas, Pérennes, Stéphane, Rivano, Hervé
In this work, we study the problem of routing packets between undifferentiated sources and sinks in a network modeled by a multigraph. We provide a distributed and local algorithm that transmits...
Stability of a local greedy distributed routing algorithm (2009)
Huc, Florian, Molle, Christelle, Nisse, Nicolas, Pérennes, Stéphane, Rivano, Hervé
In this work, we study the problem of routing packets between undifferentiated sources and sinks in a network modeled by a multigraph. We provide a distributed and local algorithm that transmits...
Stability of a local greedy distributed routing algorithm (2009)
Huc, Florian, Molle, Christelle, Nisse, Nicolas, Pérennes, Stéphane, Rivano, Hervé
In this work, we study the problem of routing packets between undifferentiated sources and sinks in a network modeled by a multigraph. We provide a distributed and local algorithm that transmits...
Reconfiguration dans les réseaux optiques (2009)
Coudert, David, Huc, Florian, Mazauric, Dorian, Nisse, Nicolas, Sereni, Jean-Sébastien
L'évolution permanente du trafic, les opérations de maintenance et l'existence de pannes dans les réseaux WDM, obligent à rerouter régulièrement des connexions. Les nouvelles demandes de...
Stability of a local greedy distributed routing algorithm (2009)
Huc, Florian, Molle, Christelle, Nisse, Nicolas, Pérennes, Stéphane, Rivano, Hervé
In this work, we study the problem of routing packets between undifferentiated sources and sinks in a network modeled by a multigraph. We provide a distributed and local algorithm that transmits...
Reconfiguration dans les réseaux optiques (2009)
Coudert, David, Huc, Florian, Mazauric, Dorian, Nisse, Nicolas, Sereni, Jean-Sébastien
L'évolution permanente du trafic, les opérations de maintenance et l'existence de pannes dans les réseaux WDM, obligent à rerouter régulièrement des connexions. Les nouvelles demandes de...
(l, k)-routing on plane grids. (2009)
Huc, Florian, Sau Walls, Ignasi, Žerovnik, Janez
The packet routing problem plays an essential role in communication networks. It involves how to transfer data from some origins to some destinations within a reasonable amount of time. In the...
Conception de Réseaux Dynamiques Tolérants aux Pannes (2008)
Cette thèse aborde différents aspects de la conception d'un réseau de télécommunications. Un tel réseau utilise des technologies hétérogènes : liens antennes-satellites, radio, fibres...
Conception de Réseaux Dynamiques Tolérants aux Pannes (2008)
Cette thèse aborde différents aspects de la conception d'un réseau de télécommunications. Un tel réseau utilise des technologies hétérogènes : liens antennes-satellites, radio, fibres...
Conception de Réseaux Dynamiques Tolérants aux Pannes (2008)
Cette thèse aborde différents aspects de la conception d'un réseau de télécommunications. Un tel réseau utilise des technologies hétérogènes : liens antennes-satellites, radio, fibres...
A distributed algorithm for computing and updating the process number of a forest (2008)
Coudert, David, Huc, Florian, Mazauric, Dorian
In this paper, we present a distributed algorithm to compute various parameters of a tree such as the process number, the edge search number or the node search number and so the pathwidth. This...
$(\ell,k)$-Routing on Plane Grids (2008)
Amini, Omid, Huc, Florian, Sau Valls, Ignasi, Zerovnik, Janez
The packet routing problem plays an essential role in communication networks. It involves how to transfer data from some origins to some destinations within a reasonable amount of time. In the...
$(\ell,k)$-Routing on Plane Grids (2008)
Amini, Omid, Huc, Florian, Sau Valls, Ignasi, Zerovnik, Janez
The packet routing problem plays an essential role in communication networks. It involves how to transfer data from some origins to some destinations within a reasonable amount of time. In the...
(l,k)-Routing on Plane Grids (2008)
Huc, Florian, Valls, Ignasi Sau, Zerovnik, Janez
The packet routing problem plays an essential role in communication networks. It involves how to transfer data from some origins to some destinations within a reasonable amount of time. In the...
The Proportional Colouring Problem: Optimizing Buffers in Radio Mesh Networks (2008)
Huc, Florian, Linhares Sales, Claudia, Rivano, Hervé
In this paper, we consider a new edge colouring problem: the proportional edge-colouring. Given a graph $G$ with positive weights associated to its edges, we want to find a colouring which preserves...
The Proportional Colouring Problem: Optimizing Buffers in Radio Mesh Networks (2008)
Huc, Florian, Linhares Sales, Claudia, Rivano, Hervé
In this paper, we consider a new edge colouring problem: the proportional edge-colouring. Given a graph $G$ with positive weights associated to its edges, we want to find a colouring which preserves...
$(\ell,k)$-Routing on Plane Grids (2008)
Amini, Omid, Huc, Florian, Sau Valls, Ignasi, Zerovnik, Janez
The packet routing problem plays an essential role in communication networks. It involves how to transfer data from some origins to some destinations within a reasonable amount of time. In the...
$(\ell,k)$-Routing on Plane Grids (2008)
Amini, Omid, Huc, Florian, Sau Valls, Ignasi, Zerovnik, Janez
The packet routing problem plays an essential role in communication networks. It involves how to transfer data from some origins to some destinations within a reasonable amount of time. In the...
A distributed algorithm for computing and updating the process number of a forest (2008)
Coudert, David, Huc, Florian, Mazauric, Dorian
In this paper, we present a distributed algorithm to compute various parameters of a tree such as the process number, the edge search number or the node search number and so the pathwidth. This...
A distributed algorithm for computing and updating the process number of a forest (2008)
Coudert, David, Huc, Florian, Mazauric, Dorian
In this paper, we present a distributed algorithm to compute various parameters of a tree such as the process number, the edge search number or the node search number and so the pathwidth. This...
Routing Reconfiguration/Process Number: Coping wih Two Classes of Services (2008)
Coudert, David, Huc, Florian, Mazauric, Dorian, Nisse, Nicolas, Sereni, Jean-Sebastien
In WDM backbone networks, the traffic pattern evolves constantly due to the nature of the demand itself or because of equipment failures leading to reroute affected connections. In this context,...
Routing Reconfiguration/Process Number: Coping wih Two Classes of Services (2008)
Coudert, David, Huc, Florian, Mazauric, Dorian, Nisse, Nicolas, Sereni, Jean-Sebastien
In WDM backbone networks, the traffic pattern evolves constantly due to the nature of the demand itself or because of equipment failures leading to reroute affected connections. In this context,...
A distributed algorithm for computing and updating the process number of a forest (2008)
Coudert, David, Huc, Florian, Mazauric, Dorian
In this paper, we present a distributed algorithm to compute various parameters of a tree such as the process number, the edge search number or the node search number and so the pathwidth. This...
A distributed algorithm for computing and updating the process number of a forest (2008)
Coudert, David, Huc, Florian, Mazauric, Dorian
In this paper, we present a distributed algorithm to compute various parameters of a tree such as the process number, the edge search number or the node search number and so the pathwidth. This...
Algorithme générique pour les jeux de capture dans les arbres (2008)
Coudert, David, Huc, Florian, Mazauric, Dorian
Nous présentons un algorithme distribué simple calculant le process number des arbres en n étapes, avec un nombre total d'opérations en O(nlog(n)) et un total de O(nlog(n)) bits échangés. De...
Algorithme générique pour les jeux de capture dans les arbres (2008)
Coudert, David, Huc, Florian, Mazauric, Dorian
Nous présentons un algorithme distribué simple calculant le process number des arbres en n étapes, avec un nombre total d'opérations en O(nlog(n)) et un total de O(nlog(n)) bits échangés. De...
Computing and updating the process number in trees (2008)
Coudert, David, Huc, Florian, Mazauric, Dorian
The process number is the minimum number of requests that have to be simultaneously disturbed during a routing reconfiguration phase of a connection oriented network. From a graph theory point of...
Computing and updating the process number in trees (2008)
Coudert, David, Huc, Florian, Mazauric, Dorian
The process number is the minimum number of requests that have to be simultaneously disturbed during a routing reconfiguration phase of a connection oriented network. From a graph theory point of...
The Proportional Colouring Problem: Optimizing Buffers in Radio Mesh Networks (2008)
Huc, Florian, Linhares Sales, Claudia, Rivano, Hervé
In this paper, we consider a new edge colouring problem: the proportional edge-colouring. Given a graph $G$ with positive weights associated to its edges, we want to find a colouring which preserves...
The Proportional Colouring Problem: Optimizing Buffers in Radio Mesh Networks (2008)
Huc, Florian, Linhares Sales, Claudia, Rivano, Hervé
In this paper, we consider a new edge colouring problem: the proportional edge-colouring. Given a graph $G$ with positive weights associated to its edges, we want to find a colouring which preserves...
The Proportional Colouring Problem: Optimizing Buffers in Radio Mesh Networks (2008)
Huc, Florian, Linhares Sales, Claudia, Rivano, Hervé
In this paper, we consider a new edge colouring problem: the proportional edge-colouring. Given a graph $G$ with positive weights associated to its edges, we want to find a colouring which preserves...
Computing and updating the process number in trees (2008)
Coudert, David, Huc, Florian, Mazauric, Dorian
The process number is the minimum number of requests that have to be simultaneously disturbed during a routing reconfiguration phase of a connection oriented network. From a graph theory point of...
Algorithme générique pour les jeux de capture dans les arbres (2008)
Coudert, David, Huc, Florian, Mazauric, Dorian
Nous présentons un algorithme distribué simple calculant le process number des arbres en n étapes, avec un nombre total d'opérations en O(nlog(n)) et un total de O(nlog(n)) bits échangés. De...
A distributed algorithm for computing and updating the process number of a forest (2008)
Coudert, David, Huc, Florian, Mazauric, Dorian
In this paper, we present a distributed algorithm to compute various parameters of a tree such as the process number, the edge search number or the node search number and so the pathwidth. This...
Routing Reconfiguration/Process Number: Coping wih Two Classes of Services (2008)
Coudert, David, Huc, Florian, Mazauric, Dorian, Nisse, Nicolas, Sereni, Jean-Sebastien
In WDM backbone networks, the traffic pattern evolves constantly due to the nature of the demand itself or because of equipment failures leading to reroute affected connections. In this context,...
A distributed algorithm for computing and updating the process number of a forest (2008)
Coudert, David, Huc, Florian, Mazauric, Dorian
In this paper, we present a distributed algorithm to compute various parameters of a tree such as the process number, the edge search number or the node search number and so the pathwidth. This...
$(\ell,k)$-Routing on Plane Grids (2008)
Amini, Omid, Huc, Florian, Sau Valls, Ignasi, Zerovnik, Janez
The packet routing problem plays an essential role in communication networks. It involves how to transfer data from some origins to some destinations within a reasonable amount of time. In the...
Computing and updating the process number in trees (2008)
Coudert, David, Huc, Florian, Mazauric, Dorian
The process number is the minimum number of requests that have to be simultaneously disturbed during a routing reconfiguration phase of a connection oriented network. From a graph theory point of...
Algorithme générique pour les jeux de capture dans les arbres (2008)
Coudert, David, Huc, Florian, Mazauric, Dorian
Nous présentons un algorithme distribué simple calculant le process number des arbres en n étapes, avec un nombre total d'opérations en O(nlog(n)) et un total de O(nlog(n)) bits échangés. De...
A distributed algorithm for computing and updating the process number of a forest (2008)
Coudert, David, Huc, Florian, Mazauric, Dorian
In this paper, we present a distributed algorithm to compute various parameters of a tree such as the process number, the edge search number or the node search number and so the pathwidth. This...
Routing Reconfiguration/Process Number: Coping wih Two Classes of Services (2008)
Coudert, David, Huc, Florian, Mazauric, Dorian, Nisse, Nicolas, Sereni, Jean-Sebastien
In WDM backbone networks, the traffic pattern evolves constantly due to the nature of the demand itself or because of equipment failures leading to reroute affected connections. In this context,...
A distributed algorithm for computing and updating the process number of a forest (2008)
Coudert, David, Huc, Florian, Mazauric, Dorian
In this paper, we present a distributed algorithm to compute various parameters of a tree such as the process number, the edge search number or the node search number and so the pathwidth. This...
$(\ell,k)$-Routing on Plane Grids (2008)
Amini, Omid, Huc, Florian, Sau Valls, Ignasi, Zerovnik, Janez
The packet routing problem plays an essential role in communication networks. It involves how to transfer data from some origins to some destinations within a reasonable amount of time. In the...
Conception de Réseaux Dynamiques Tolérants aux Pannes (2008)
Cette thèse aborde différents aspects de la conception d'un réseau de télécommunications. Un tel réseau utilise des technologies hétérogènes : liens antennes-satellites, radio, fibres...
Conception de Réseaux Dynamiques Tolérants aux Pannes (2008)
Cette thèse aborde différents aspects de la conception d'un réseau de télécommunications. Un tel réseau utilise des technologies hétérogènes : liens antennes-satellites, radio, fibres...
Conception de Réseaux Dynamiques Tolérants aux Pannes (2008)
Cette thèse aborde différents aspects de la conception d'un réseau de télécommunications. Un tel réseau utilise des technologies hétérogènes : liens antennes-satellites, radio, fibres...
WDM and Directed Star Arboricity (2007)
Amini, Omid, Havet, Frederic, Huc, Florian, Thomasse, Stephan
A digraph is {\it $m$-labelled} if every arcs is labelled by an integer in $\{1, \dots ,m\}$. Motivated by wavelength assignment for multicasts in optical star networks, we study {\it $n$-fiber...
WDM and Directed Star Arboricity (2007)
Amini, Omid, Havet, Frederic, Huc, Florian, Thomasse, Stephan
A digraph is {\it $m$-labelled} if every arcs is labelled by an integer in $\{1, \dots ,m\}$. Motivated by wavelength assignment for multicasts in optical star networks, we study {\it $n$-fiber...
WDM and Directed Star Arboricity (2007)
Amini, Omid, Havet, Frederic, Huc, Florian, Thomasse, Stephan
A digraph is $m$-labelled if every arc is labelled by an integer in $\{1, \dots,m\}$. Motivated by wavelength assignment for multicasts in optical networks, we introduce and study $n$-fibre...
WDM and Directed Star Arboricity (2007)
Amini, Omid, Havet, Frederic, Huc, Florian, Thomasse, Stephan
A digraph is {\it $m$-labelled} if every arcs is labelled by an integer in $\{1, \dots ,m\}$. Motivated by wavelength assignment for multicasts in optical star networks, we study {\it $n$-fiber...
WDM and Directed Star Arboricity (2007)
Amini, Omid, Havet, Frederic, Huc, Florian, Thomasse, Stephan
A digraph is {\it $m$-labelled} if every arcs is labelled by an integer in $\{1, \dots ,m\}$. Motivated by wavelength assignment for multicasts in optical star networks, we study {\it $n$-fiber...
WDM and Directed Star Arboricity (2007)
Amini, Omid, Havet, Frederic, Huc, Florian, Thomasse, Stephan
A digraph is {\it $m$-labelled} if every arcs is labelled by an integer in $\{1, \dots ,m\}$. Motivated by wavelength assignment for multicasts in optical star networks, we study {\it $n$-fiber...
WDM and Directed Star Arboricity (2007)
Amini, Omid, Havet, Frederic, Huc, Florian, Thomasse, Stephan
A digraph is {\it $m$-labelled} if every arcs is labelled by an integer in $\{1, \dots ,m\}$. Motivated by wavelength assignment for multicasts in optical star networks, we study {\it $n$-fiber...
Coudert, David, Huc, Florian, Peix, Fabrice, Voge, Marie-Emilie
The notion of Shared Risk Resource Groups (SRRG) has been introduced to capture survivability issues when a set of resources may fail simultaneously. Applied to Wavelength Division Multiplexing...
Coudert, David, Huc, Florian, Peix, Fabrice, Voge, Marie-Emilie
The notion of Shared Risk Resource Groups (SRRG) has been introduced to capture survivability issues when a set of resources may fail simultaneously. Applied to Wavelength Division Multiplexing...
Allocation de fréquences et coloration impropre des graphes hexagonaux pondérés (2007)
Bermond, Jean-Claude, Havet, Frederic, Huc, Florian, Linhares-Sales, Claudia
Motivés par un problème d'allocation de fréquences, nous étudions la coloration impropre des graphes pondérés et plus particulièrement des graphes hexagonaux pondérés. Nous donnons des...
Allocation de fréquences et coloration impropre des graphes hexagonaux pondérés (2007)
Bermond, Jean-Claude, Havet, Frederic, Huc, Florian, Linhares-Sales, Claudia
Motivés par un problème d'allocation de fréquences, nous étudions la coloration impropre des graphes pondérés et plus particulièrement des graphes hexagonaux pondérés. Nous donnons des...
Path-width of Outerplanar Graphs (2007)
David Coudert, Florian Huc, Jean-sébastien Sereni
We are interested in the relation between the pathwidth of a biconnected outerplanar graph and the pathwidth of its (geometric) dual. Bodlaender and Fomin [3], after having proved that the pathwidth...
Coudert, David, Huc, Florian, Peix, Fabrice, Voge, Marie-Emilie
The notion of Shared Risk Resource Groups (SRRG) has been introduced to capture survivability issues when a set of resources may fail simultaneously. Applied to Wavelength Division Multiplexing...
WDM and Directed Star Arboricity (2007)
Amini, Omid, Havet, Frederic, Huc, Florian, Thomasse, Stephan
A digraph is {\it $m$-labelled} if every arcs is labelled by an integer in $\{1, \dots ,m\}$. Motivated by wavelength assignment for multicasts in optical star networks, we study {\it $n$-fiber...
Allocation de fréquences et coloration impropre des graphes hexagonaux pondérés (2007)
Bermond, Jean-Claude, Havet, Frederic, Huc, Florian, Linhares-Sales, Claudia
Motivés par un problème d'allocation de fréquences, nous étudions la coloration impropre des graphes pondérés et plus particulièrement des graphes hexagonaux pondérés. Nous donnons des...
Coudert, David, Huc, Florian, Peix, Fabrice, Voge, Marie-Emilie
The notion of Shared Risk Resource Groups (SRRG) has been introduced to capture survivability issues when a set of resources may fail simultaneously. Applied to Wavelength Division Multiplexing...
WDM and Directed Star Arboricity (2007)
Amini, Omid, Havet, Frederic, Huc, Florian, Thomasse, Stephan
A digraph is {\it $m$-labelled} if every arcs is labelled by an integer in $\{1, \dots ,m\}$. Motivated by wavelength assignment for multicasts in optical star networks, we study {\it $n$-fiber...
Allocation de fréquences et coloration impropre des graphes hexagonaux pondérés (2007)
Bermond, Jean-Claude, Havet, Frederic, Huc, Florian, Linhares-Sales, Claudia
Motivés par un problème d'allocation de fréquences, nous étudions la coloration impropre des graphes pondérés et plus particulièrement des graphes hexagonaux pondérés. Nous donnons des...
Pathwidth of outerplanar graphs (2006)
Coudert, David, Huc, Florian, Sereni, Jean-Sébastien
We are interested in the relation between the pathwidth of a biconnected outerplanar graph and the pathwidth of its (geometric) dual. Bodlaender and Fomin, after having proved that the pathwidth of...
Pathwidth of outerplanar graphs (2006)
Coudert, David, Huc, Florian, Sereni, Jean-Sébastien
We are interested in the relation between the pathwidth of a biconnected outerplanar graph and the pathwidth of its (geometric) dual. Bodlaender and Fomin, after having proved that the pathwidth of...
On the Pathwidth of Planar Graphs (2006)
Amini, Omid, Huc, Florian, Pérennes, Stéphane
Fomin and Thilikos in \cite{FoTh06} conjectured that there is a constant $c$ such that, for every $2$-connected planar graph $G$, $\text{pw}(G^*) \leq 2\text{pw}(G)+c$ (the same question was asked...
Minimal Selectors and Fault Tolerant Networks (2006)
Amini, Omid, Giroire, Frédéric, Huc, Florian, Pérennes, Stéphane
Un r\'eseau $\plk$ est un graphe non orient\'e avec $p + \lambda$ entr\'ees, $p + k$ sorties et des noeuds internes de degr\'e $4$. Un r\'eseau $\plk$ est valide si pour n'importe quel choix de $p$...
On the Pathwidth of Planar Graphs (2006)
Amini, Omid, Huc, Florian, Pérennes, Stéphane
Fomin and Thilikos in [5] conjectured that there is a constant $c$ such that, for every $2$-connected planar graph $G$, {pw}(G^*) \leq 2\text{pw}(G)+c$ (the same question was asked simutaneously by...
Minimal Selectors and Fault Tolerant Networks (2006)
Amini, Omid, Giroire, Frédéric, Huc, Florian, Pérennes, Stéphane
Un reseau $\plk$ est un graphe non oriente avec $p + \lambda$ entrees, $p + k$ sorties et des noeuds internes de degre $4$. Un reseau $\plk$ est valide si pour n'importe quel choix de $p$ entrees et...
Pathwidth of outerplanar graphs (2006)
Coudert, David, Huc, Florian, Sereni, Jean-Sébastien
We are interested in the relation between the pathwidth of a biconnected outerplanar graph and the pathwidth of its (geometric) dual. Bodlaender and Fomin, after having proved that the pathwidth of...
On the Pathwidth of Planar Graphs (2006)
Amini, Omid, Huc, Florian, Pérennes, Stéphane
Fomin and Thilikos in [5] conjectured that there is a constant $c$ such that, for every $2$-connected planar graph $G$, {pw}(G^*) \leq 2\text{pw}(G)+c$ (the same question was asked simutaneously by...
Minimal Selectors and Fault Tolerant Networks (2006)
Amini, Omid, Giroire, Frédéric, Huc, Florian, Pérennes, Stéphane
Un reseau $\plk$ est un graphe non oriente avec $p + \lambda$ entrees, $p + k$ sorties et des noeuds internes de degre $4$. Un reseau $\plk$ est valide si pour n'importe quel choix de $p$ entrees et...
Minimal selectors and fault tolerant networks (2006)
Omid Amini, Frédéric Giroire, Florian Huc, Stéphane Pérennes
In this paper we study a combinatorial optimization problem arising from on-board networks in satellites. In these kind of networks the entering signals (inputs) should be routed to amplifiers...
Pathwidth of outerplanar graphs (2006)
Coudert, David, Huc, Florian, Sereni, Jean-Sebastien
We are interested in the relation between the pathwidth of a biconnected outerplanar graph and the pathwidth of its (geometric) dual. Bodlaender and Fomin [3], after having proved that the pathwidth...
Pathwidth of outerplanar graphs (2006)
Coudert, David, Huc, Florian, Sereni, Jean-Sebastien
We are interested in the relation between the pathwidth of a biconnected outerplanar graph and the pathwidth of its (geometric) dual. Bodlaender and Fomin [3], after having proved that the pathwidth...
Pathwidth of outerplanar graphs (2006)
Coudert, David, Huc, Florian, Sereni, Jean-Sébastien
We are interested in the relation between the pathwidth of a biconnected outerplanar graph and the pathwidth of its (geometric) dual. Bodlaender and Fomin, after having proved that the pathwidth of...
On the Pathwidth of Planar Graphs (2006)
Amini, Omid, Huc, Florian, Pérennes, Stéphane
Fomin and Thilikos in [5] conjectured that there is a constant $c$ such that, for every $2$-connected planar graph $G$, {pw}(G^*) \leq 2\text{pw}(G)+c$ (the same question was asked simutaneously by...
Minimal Selectors and Fault Tolerant Networks (2006)
Amini, Omid, Giroire, Frédéric, Huc, Florian, Pérennes, Stéphane
Un reseau $\plk$ est un graphe non oriente avec $p + \lambda$ entrees, $p + k$ sorties et des noeuds internes de degre $4$. Un reseau $\plk$ est valide si pour n'importe quel choix de $p$ entrees et...
Pathwidth of outerplanar graphs (2006)
Coudert, David, Huc, Florian, Sereni, Jean-Sebastien
We are interested in the relation between the pathwidth of a biconnected outerplanar graph and the pathwidth of its (geometric) dual. Bodlaender and Fomin [3], after having proved that the pathwidth...
Pathwidth of outerplanar graphs (2006)
Coudert, David, Huc, Florian, Sereni, Jean-Sébastien
We are interested in the relation between the pathwidth of a biconnected outerplanar graph and the pathwidth of its (geometric) dual. Bodlaender and Fomin, after having proved that the pathwidth of...
On the Pathwidth of Planar Graphs (2006)
Amini, Omid, Huc, Florian, Pérennes, Stéphane
Fomin and Thilikos in [5] conjectured that there is a constant $c$ such that, for every $2$-connected planar graph $G$, {pw}(G^*) \leq 2\text{pw}(G)+c$ (the same question was asked simutaneously by...
Minimal Selectors and Fault Tolerant Networks (2006)
Amini, Omid, Giroire, Frédéric, Huc, Florian, Pérennes, Stéphane
Un reseau $\plk$ est un graphe non oriente avec $p + \lambda$ entrees, $p + k$ sorties et des noeuds internes de degre $4$. Un reseau $\plk$ est valide si pour n'importe quel choix de $p$ entrees et...