Ageev, A. A.; Il’ev, V. P.; Kononov, A. V.; Televnin, A. S. Computational complexity of the graph approximation problem. (Russian) Zbl 1249.68085 Diskretn. Anal. Issled. Oper., Ser. 1 13, No. 1, 3-15 (2006). Summary: The computational complexity of the graph approximation problem is investigated. It is shown that 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. Cited in 10 Documents MSC: 68Q25 Analysis of algorithms and problem complexity 05C85 Graph algorithms (graph-theoretic aspects) 68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) Keywords:non-oriented graph; oriented graph PDFBibTeX XMLCite \textit{A. A. Ageev} et al., Diskretn. Anal. Issled. Oper., Ser. 1 13, No. 1, 3--15 (2006; Zbl 1249.68085) Full Text: DOI