
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 8692
\mathnet{http://mi.mathnet.ru/pdm427}
Linking options:
http://mi.mathnet.ru/eng/pdm427 http://mi.mathnet.ru/eng/pdm/y2013/i3/p86
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 
