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
Programmation mathématique multi-objectif pour la
Thursday 13 December 2018 - 14h30
Salle : unknown - unknown
Audrey Legendre .............................................

Redundancy in Distributed Proofs
Algorithmique distribuée
Tuesday 04 December 2018 - 00h00
Salle : 465 - PCRI-N
Ami Paz .............................................

Some recent results on the integer linear programm
Théorie des graphes
Friday 30 November 2018 - 00h00
Salle : 445 - PCRI-N
Hung Nguyen .............................................

Scalable and exhaustive screening of metabolic fun
Wednesday 28 November 2018 - 11h00
Salle : 465 - PCRI-N
Clémence Frioux .............................................

Studying the three-dimensional structure of DNA fr
Thursday 22 November 2018 - 15h00
Salle : unknown - unknown
Nelle Varoquaux .............................................