Evènement pour le groupe Séminaire du LaBRI

Date 2011-09-29  14:00-15:00
TitreGirth and the greedy algorithm 
RésuméFinding an efficient algorithm to decide if a given graph or network has a certain property is often difficult or very unlikely. Thus there is some interest in graphs with the characteristic that a simple, such as the greedy, algorithm produces a set with the desired property efficiently. For example, well-covered graphs (every maximal independent set of vertices is of one size and, hence, maximum) fall into this category. Many such problems have the rather curious feature that if one knows the structure of trees in the collection, then this characterization is essentially the same even with cycles present as long as they are not too small. For instance, the well-covered graphs of girth 8 or more (i.e., with no cycles of length 7 or smaller) can be described essentially the same as well-covered trees. A similar situation arises with the problem of where to locate undesirable objects (garbage dumps, nuclear sites) so that we have no more that k in the neighbourhood of anyone. A number of problems of this type will be outlined.  
LieuAmphi du LaBRI 
OrateurBert Hartnell 
UrlSaint Mary's University, Halifax, Canada 

Aucun document lié à cet événement.

Retour à l'index