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
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.
graph approximation, graph partitioning, sparse graphs, problem complexity reduction.
PDF file (623 kB)
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
\by A.~R.~Urakov, T.~V.~Timeryaev
\paper Two problems of weighted graphs approximation and their solution algorithms
\jour Prikl. Diskr. Mat.
Citing articles on Google Scholar:
Related articles on Google Scholar:
|Number of views:|