Français Anglais
Accueil Annuaire Plan du site
Accueil > Evenements > Séminaires
Séminaire d'équipe(s)
Crystal trees
Rafael Castro

23 November 2012, 10h30 - 23 November 2012, 11h30
Salle/Bat : 475/PCRI-N
Contact : rafael.castro@lri.fr

Activités de recherche :

Résumé :
Consider an undirected and connected graph $G=(V,E)$ of node set $V$ and edge set $E$, with $c_{uv}>0$ being the energy associated with an edge $uv in E$. Let $T$ be a pending spanning tree of $G$ rooted at a distinguished node $kin V$, where each node $vin V-{k}$ accumulates the information of the energy of the edges in the path from the root node $k$ until $v$ in $T$. We say that two nodes $u$ and $v$ present stable potential equilibrium in $T$ if any edge $uv in E$ not in $T$ have greater energy than the edge with larger energy in the direct path from $u$ to $v$ in $T$. Two nodes $u$ and $v$, with $uv in E$ and $uv notin T$, have instable potential equilibrium in $T$ if the paths from $u$ and $v$ to their first common ancestor in their paths to $k$ contain exactly (each path) the same edge energies having larger values than the one of $uv$ and all the remaining edges in the direct
path from $u$ to $v$ in $T$ have not greater energy than $c_{uv}$. A
$k$-rooted pending spanning tree of $G$ with equilibrated potentials is a crystal tree. In this work we present some properties of crystal trees and discuss their relations/differences with respect to spanning trees of minimum energy and $k$-rooted shortest path trees. We introduce a potential function allowing to describe the complete set of crystal trees of a graph $G$ as solutions of a polynomially bounded system of linear inequalities.

Pour en savoir plus :
Séminaires
A Two-level Auction for Resource Allocation in Mul
Réseaux sans fil et mobiles
Friday 09 March 2018 - 14h30
Salle : 445 - PCRI-N
Mira Morcos .............................................

Binary pattern of length greater than 14 are abeli
Combinatoire
Friday 09 February 2018 - 14h30
Salle : 445 - PCRI-N
Matthieu Rosenfeld .............................................

Approximate Bayesian Computation and Random Forest
Thursday 08 February 2018 - 00h00
Salle : 455 - PCRI-N
Valentin Thouzeau .............................................

A concurrent lock-free algorithm for computing a f
Combinatoire
Friday 12 January 2018 - 14h30
Salle : 445 - PCRI-N
James Mitchell .............................................

Acyclic Partitioning of Large Directed Acyclic Gra
Calcul à haute performance
Tuesday 09 January 2018 - 10h30
Salle : 465 - PCRI-N
Julien Herrmann .............................................