A. A. Ageev, V. P. Il'ev, A. V. Kononov, A. S. Televnin, “Computational complexity of the graph approximation problem”, Diskretn. Anal. Issled. Oper., Ser. 1, 2006, Volume 13, Issue 1,Pages <nobr>3

This article is cited in 30 papers

Computational complexity of the graph approximation problem

A. A. Ageev^a, V. P. Il'ev^b, A. V. Kononov^a, A. S. Televnin^b

^a Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences
^b Omsk State University

Abstract: The computational complexity of the graph approximation problem is investigated. It is shown that the different variants of this problem are NP-hard both for undirected and directed graphs. A polynomial-time approximation scheme (PTAS) for one of the variants is presented.

UDC: 519.8

Received: 20.09.2005