|
Diskretnyi Analiz i Issledovanie Operatsii, Ser. 1, 2006, Volume 13, Issue 1, Pages 3–15
(Mi da20)
|
|
|
|
This article is cited in 30 scientific papers (total in 30 papers)
Computational complexity of the graph approximation problem
A. A. Ageeva, V. P. Il'evb, A. V. Kononova, A. S. Televninb 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.
Received: 20.09.2005
Citation:
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, 13:1 (2006), 3–15; J. Appl. Industr. Math., 1:1 (2007), 1–8
Linking options:
https://www.mathnet.ru/eng/da20 https://www.mathnet.ru/eng/da/v13/s1/i1/p3
|
Statistics & downloads: |
Abstract page: | 448 | Full-text PDF : | 265 | References: | 54 |
|