RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
General information
Latest issue
Archive

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Tr. Inst. Mat.:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Tr. Inst. Mat., 2010, Volume 18, Number 1, Pages 47–52 (Mi timb6)  

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 constant-factor 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 47--52
\mathnet{http://mi.mathnet.ru/timb6}


Linking options:
  • http://mi.mathnet.ru/eng/timb6
  • http://mi.mathnet.ru/eng/timb/v18/i1/p47

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    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:
    1. 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  mathnet  crossref  mathscinet  zmath
  • Труды Института математики
    Number of views:
    This page:400
    Full text:247
    References:18

     
    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2020