Actes d'une conférence (1998), Advances in Computer and Information Sciences '98. 13th International Symposium on Computer and Information Sciences (ISCIS), IOS Press, pp. 574-581
On the Approximation of Some Spanning Arborescence Problems
Nous présentons une classe de problèmes d'optimisation, appelée M-ST (Master-Slave Tractable), consistant à couvrir ou partitionner les sommets ou les arêtes d'un graphe par des sous-graphes. Ces problèmes, en général NP-difficiles, sont tous approximables à rapport logarithmique par une instanciation de l'algorithme glouton classique par le problème de Set Covering. Des applications sont présentées dans le domaine du dimensionnement de réseau (Network Design).
ALFANDARI, L. and PASCHOS, V. (1998). On the Approximation of Some Spanning Arborescence Problems. In: Advances in Computer and Information Sciences '98. 13th International Symposium on Computer and Information Sciences (ISCIS). IOS Press, pp. 574-581.