0000000001229954
AUTHOR
Pēteris Lediņš
Fast and Simple Approximation of the Diameter and Radius of a Graph
The increasing amount of data to be processed by computers has led to the need for highly efficient algorithms for various computational problems. Moreover, the algorithms should be as simple as possible to be practically applicable. In this paper we propose a very simple approximation algorithm for finding the diameter and the radius of an undirected graph. The algorithm runs in $O(m\sqrt{n})$ time and gives an additive error of $O(\sqrt{n})$ for a graph with n vertices and m edges. Practical experiments show that the results of our algorithm are close to the optimum and compare favorably to the 2/3-approximation algorithm for the diameter problem by Aingworth et al [1].
Grafu klasterēšanas algoritmi un to pielietojums pļavu grupēšanā
Darba tēma ir grafu klasterēšana, kas ir apakšgadījums vispārīgai klasterēšanai. Darbā tiek pētīti grafu klasterēšanas algoritmi no teorētiskās puses un to pielietojums pļavu klasteru veidošanā. Autors izveido laba grafu klasterēšanas algoritma aksiomas un salīdzina dažādus algoritmus pēc to atbilstības dotajām aksiomām. Tāpat šie algoritmi tiek salīdzināti pēc dažiem to klasterējumus raksturojošiem skaitliskiem lielumiem, kas iegūti, klasterējot dažādus ģenerētus grafus. Darba praktiskajā daļā autors mēģina klasterēt pļavas, lai iegūtu iepriekš iegūtam klasterējumam līdzīgu rezultātu. Šīs daļas rezultāts ir negatīvs -- tiek secināts, ka tas nav iespējams ar dotiem datiem bez eksperta iejau…