Computational complexity of the graph approximation problem |
| |
| Authors: | A A Ageev V P Il’ev A V Kononov A S Talevnin |
| |
| Institution: | (1) Sobolev Institute of Mathematics, pr. Akad. Koptyuga 4, Novosibirsk, 630090, Russia;(2) Omsk State University, pr. Mira 55a, Omsk, 644077, Russia |
| |
| 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. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
