×

zbMATH — the first resource for mathematics

Computational complexity of the graph approximation problem. (Russian) Zbl 1249.68085
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.

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.)
PDF BibTeX XML Cite