Publications of Anna Galluccio

This page shows all publications that appeared in the IASI annual research reports. Authors currently affiliated with the Institute are always listed with the full name.

You can browse through them using either the links of the following line or those associated with author names.

Show all publications of the year  1999, with author Galluccio A., in the category IASI Research Reports (or show them all):


IASI Research Report n. 506  (Next)  

Anna Galluccio, Guido Proietti

Towards a 4/3-approximation algorithm for biconnectivity

ABSTRACT
Finding a minimum size 2-vertex connected spanning subgraph of a graph G with n vertices and m edges is known to be NP-hard even if a Hamiltonian path of G is given as part of the input. In this paper we propose an O(n + m) time and space algorithm which approximates the optimal solution for the above problem by a factor of no more than 4/3. The best known algorithm for the case in which a Hamiltonian path is not given is due to Garg et al., and has an approximation guarantee of 3/2. The ratio of their algorithm does not decrease when it is applied to the special case in which a Hamiltonian path is given as part of the input.
back
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -