Finding a minimum size 2-vertex connected spanning subgraph of a k-vertex connected graph G = (V,E) with n vertices and m edges is known to be NP-hard and APX-hard, as well as approximable in O(n 2 m) time within a factor of 4/3. Interestingly, the problem remains NP-hard even if a Hamiltonian path of G is given as part of the input. For this input-enriched version of the problem, we provide in this paper a linear time and space algorithm which approximates the optimal solution by a factor of no more than min {54,2k−12(k−1)} .

A 5/4-Approximation Algorithm for Biconnecting a Graph with a Given Hamiltonian Path / Bilò, Davide; Proietti, Guido. - 3351:(2005), pp. 181-196. ((Intervento presentato al convegno 2nd International Workshop on Approximation and Online Algorithms tenutosi a Bergen, Norway nel September 14-16, 2004 [10.1007/978-3-540-31833-0_16].

A 5/4-Approximation Algorithm for Biconnecting a Graph with a Given Hamiltonian Path

BILÒ, Davide;
2005

Abstract

Finding a minimum size 2-vertex connected spanning subgraph of a k-vertex connected graph G = (V,E) with n vertices and m edges is known to be NP-hard and APX-hard, as well as approximable in O(n 2 m) time within a factor of 4/3. Interestingly, the problem remains NP-hard even if a Hamiltonian path of G is given as part of the input. For this input-enriched version of the problem, we provide in this paper a linear time and space algorithm which approximates the optimal solution by a factor of no more than min {54,2k−12(k−1)} .
3-540-24574-X
A 5/4-Approximation Algorithm for Biconnecting a Graph with a Given Hamiltonian Path / Bilò, Davide; Proietti, Guido. - 3351:(2005), pp. 181-196. ((Intervento presentato al convegno 2nd International Workshop on Approximation and Online Algorithms tenutosi a Bergen, Norway nel September 14-16, 2004 [10.1007/978-3-540-31833-0_16].
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11388/72812
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 0
social impact