×

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.)
PDFBibTeX XMLCite
Full Text: DOI