Bookcover of Algorithmes à mémoire limitée pour le traitement de grands graphes
Booktitle:

Algorithmes à mémoire limitée pour le traitement de grands graphes

Le problème du Vertex Cover

Presses Académiques Francophones (2012-05-30 )

Books loader

Omni badge eligible for voucher
ISBN-13:

978-3-8381-8819-5

ISBN-10:
3838188195
EAN:
9783838188195
Book language:
French
Blurb/Shorttext:
Lorsque l’on traite de façon classique un problème d’optimisation sur un graphe, celui-ci est le plus souvent disponible dans sa totalité sur la machine de traitement. Il peut être modifié, mis à jour (les sommets peuvent être marqués, les arêtes supprimées, etc.) et la solution peut être conservée en mémoire. Cependant, de plus en plus d’applications produisent des quantités de données qui sont trop importantes et qui ne peuvent pas être stockées ni traitées dans ce modèle. Nous nous sommes intéressés à la résolution d'un problème d'optimisation, le Vertex Cover, sur de grands graphes. Nous avons défini pour cela un modèle de traitement basé sur des contraintes liées principalement à la quantité de mémoire limitée, modèle qui reprenait des propriétés issues de plusieurs modèles existants dans la littérature (online, streaming...). Nous avons étudié plusieurs algorithmes adaptés à ce modèle : nous avons analysé, tout d'abord de façon théorique, la qualité de leurs solutions ainsi que leurs complexités (en pire cas et en moyenne). Nous avons ensuite mené une étude expérimentale sur de très gros graphes.
Publishing house:
Presses Académiques Francophones
Website:
https://www.presses-academiques.com
By (author) :
Romain Campigotto
Number of pages:
148
Published on:
2012-05-30
Stock:
Available
Category:
Informatics
Price:
49.00 €
Keywords:
Optimisation, Approximation, Graphes, Algorithmes, Vertex Cover, grandes instances, mémoire limitée

Books loader

Adyen::diners Adyen::jcb Adyen::discover Adyen::amex Adyen::mc Adyen::visa Adyen::cup Adyen::alipay Adyen::unionpay Adyen::paypal Paypal Wire Transfer

  0 products in the shopping cart
Edit cart
Loading frontend
LOADING