
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
Abstract:
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 constantfactor approximation algorithms for two versions of the graph approximation problem are proposed.
Full text:
PDF file (208 kB)
References:
PDF file
HTML file
UDC:
519.8 Received: 12.02.2010
Citation:
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
\Bibitem{IleIle10}
\by V.~P.~Il'ev, S.~D.~Il'eva
\paper Approximation algorithms for approximating graphs with bounded numberof connected components
\jour Tr. Inst. Mat.
\yr 2010
\vol 18
\issue 1
\pages 4752
\mathnet{http://mi.mathnet.ru/timb6}
Linking options:
http://mi.mathnet.ru/eng/timb6 http://mi.mathnet.ru/eng/timb/v18/i1/p47
Citing articles on Google Scholar:
Russian citations,
English citations
Related articles on Google Scholar:
Russian articles,
English articles
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: 
This page:  400  Full text:  247  References:  18 
