V. P. Il'ev, S. D. Il'eva, A. A. Navrotskaya, “Approximation algorithms for graph approximation problems”, Diskretn. Anal. Issled. Oper., 2011, Volume 18, Issue 1,Pages <nobr>41

This article is cited in 7 papers

Approximation algorithms for graph approximation problems

V. P. Il'ev^a, S. D. Il'eva^b, A. A. Navrotskaya^a

^a Omsk State University, Omsk, Russia
^b Omsktelecom, Omsk, Russia

Abstract: Some versions of the graph approximation problem are studied. Approximation algorithms for these problems are proposed and performance guarantees of the algorithms are obtained. In particular, it is shown that the problem of approximation by graphs with a bounded number of connected components belongs to the class APX. Ill. 1, bibliogr. 12.

Keywords: graph approximation problem, approximation algorithm, performance guarantee.

UDC: 519.8

Received: 20.07.2010
Revised: 29.11.2010