This article is cited in 1 scientific paper (total in 1 paper)
Approximation algorithms for approximating graphs with bounded numberof connected components
V. P. Il'ev, S. D. Il'eva
Omsk State University
The following graph approximation problem is studied: given an undirected graph, one has to find the nearest graph on the same vertex set all connected components of which are the complete graphs. The distance between graphs is equal to the number of noncoinciding edges. The brief survey of the known results is given. The constant-factor approximation algorithms for two versions of the graph approximation problem are proposed.
PDF file (208 kB)
V. P. Il'ev, S. D. Il'eva, “Approximation algorithms for approximating graphs with bounded numberof connected components”, Tr. Inst. Mat., 18:1 (2010), 47–52
Citation in format AMSBIB
\by V.~P.~Il'ev, S.~D.~Il'eva
\paper Approximation algorithms for approximating graphs with bounded numberof connected components
\jour Tr. Inst. Mat.
Citing articles on Google Scholar:
Related articles on Google Scholar:
This publication is cited in the following articles:
V. P. Il'ev, S. D. Il'eva, A. A. Navrotskaya, “Approximation algorithms for graph approximation problems”, J. Appl. Industr. Math., 5:4 (2011), 569–581
|Number of views:|