Return to results
Conference Proceedings (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

ALFANDARI Laurent , PASCHOS V.

We define a new class of optimization problems, called M-ST (Master-Slave Tractable), which consist in covering or partitioning the vertex-set (or the edge-set) of a weighted graph by subgraphs. These NP-hard problems can be approximated within logarithmic ratio by an instanciation of the classical greedy algorithm for the Set Covering problem. Several applications are presented in the field of 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.