
Evènement pour le groupe Séminaire du LaBRI
Date  20110929 14:0015:00 
Titre  Girth 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, wellcovered 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 wellcovered graphs of girth 8 or more (i.e., with no cycles of length 7 or smaller) can be described essentially the same as wellcovered 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. 
Lieu  Amphi du LaBRI 
Orateur  Bert Hartnell 
Url  Saint Mary's University, Halifax, Canada 
Aucun document lié à cet événement. RetourRetour à l'index
 