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

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Prikl. Diskr. Mat.:
Year:
Volume:
Issue:
Page:
Find






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


Prikl. Diskr. Mat., 2013, Number 3(21), Pages 86–92 (Mi pdm427)  

Applied Graph Theory

Two problems of weighted graphs approximation and their solution algorithms

A. R. Urakov, T. V. Timeryaev

Ufa State Aviation Technical University, Ufa, Russia

Abstract: Two approximation problems for weighted sparse graphs are considered. By the approximation error is meant the absolute value of the difference of the distances between the vertices in graph and the corresponding vertices in an approximation graph. The first problem is to minimize the approximation error under a given dimension of the approximation graph. The second problem is to minimize the dimension of the approximation graph under a given approximation error threshold. For both problems, their solution algorithms are proposed and their presentation in the form of a graph partitioning problem are presented.

Keywords: graph approximation, graph partitioning, sparse graphs, problem complexity reduction.

Full text: PDF file (623 kB)
References: PDF file   HTML file
UDC: 519.176

Citation: A. R. Urakov, T. V. Timeryaev, “Two problems of weighted graphs approximation and their solution algorithms”, Prikl. Diskr. Mat., 2013, no. 3(21), 86–92

Citation in format AMSBIB
\Bibitem{UraTim13}
\by A.~R.~Urakov, T.~V.~Timeryaev
\paper Two problems of weighted graphs approximation and their solution algorithms
\jour Prikl. Diskr. Mat.
\yr 2013
\issue 3(21)
\pages 86--92
\mathnet{http://mi.mathnet.ru/pdm427}


Linking options:
  • http://mi.mathnet.ru/eng/pdm427
  • http://mi.mathnet.ru/eng/pdm/y2013/i3/p86

    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
  • Прикладная дискретная математика
    Number of views:
    This page:138
    Full text:51
    References:29
    First page:1

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