A 2-Approximation Algorithm for Finding an Optimum 3-Vertex-Connected Spanning Subgraph

Author： Auletta V.   Dinitz Y.   Nutov Z.   Parente D.  

Publisher： Academic Press

ISSN： 0196-6774

Source： Journal of Algorithms, Vol.32, Iss.1, 1999-07, pp. : 21-30

Disclaimer: Any content in publications that violate the sovereignty, the constitution or regulations of the PRC is not accepted or approved by CNPIEC.

Previous Menu Next

Abstract

Related content

A 3-Approximation Algorithm for Finding Optimum 4,5-Vertex-Connected Spanning Subgraphs

By Dinitz Y.   Nutov Z.  

Journal of Algorithms, Vol. 32, Iss. 1, 1999-07 ,pp. : 31-40

Academic Press

Access to resources Recommend Favorite

Finding 2-edge connected spanning subgraphs

By Huh W.T.  

Operations Research Letters, Vol. 32, Iss. 3, 2004-05 ,pp. : 212-216

Elsevier

Access to resources Recommend Favorite

A Better Approximation Ratio for the Minimum Size k-Edge-Connected Spanning Subgraph Problem

By Fernandes C.G.  

Journal of Algorithms, Vol. 28, Iss. 1, 1998-07 ,pp. : 105-124

Academic Press

Access to resources Recommend Favorite

The 2-Edge-Connected Subgraph Polyhedron

By Vandenbussche Dieter   Nemhauser George  

Journal of Combinatorial Optimization, Vol. 9, Iss. 4, 2005-06 ,pp. : 357-379

Springer Publishing Company

Access to resources Recommend Favorite

Hardness of k-Vertex-Connected Subgraph Augmentation Problem

By Ma Changcun   Kim Donghyun   Wang Yuexuan   Wang Wei   Sohaee Nassim   Wu Weili  

Journal of Combinatorial Optimization, Vol. 20, Iss. 3, 2010-10 ,pp. : 249-258

Springer Publishing Company

Access to resources Recommend Favorite