0000000000147063
AUTHOR
Rūdolfs Opmanis
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].
Planāra un kompakta koku izvietošana
Grafu izvietojumiem, kas iegūti automātiski, ir ļoti dažādi pielietojumi, taču kvalitāte ir nepieciešama visiem izvietojumiem. Lai arī vieni no svarīgākajiem izvietojuma kvalitātes kritērijiem ir objektu nepārklāšanās un zīmējuma kompaktums, daudzi izvietotāji nespēj garantēt šādu izvietojumu pat kokiem. Darbā aplūkoti dažādi koku izvietošanas algoritmi, izvietošanas kvalitātes kritēriji un koku klases. Piedāvāts koku izvietošanas algoritms, kas atbalsta vairākus praksē nozīmīgus ierobežojumus un izvieto kokus planāri un kompakti. Iegūtie grafu izvietojumi atgādina izvietojumus, kuri iegūti ar simetriskā stila izvietotāju, kas pašlaik ir viens no estētiskuma etaloniem. Piedāvātais izvietotā…
Root cause analysis of large scale application testing results
In this paper we present a new root cause analysis algorithm for discovering the most likely causes of the differences found in testing results of two versions of the same software. The problematic points in test and environment attribute hierarchies are presented to the user in compact way which in turn allows to save time on test result processing. We have proven that for clearly separated problem causes our algorithm gives exact solution. Practical application of described method is discussed.
Retinātu grafu hierarhiska izvietošana
Spēja izvietot kvalitatīvi retinātus grafus ir svarīga jebkuram izvietotājam, jo ar šādiem grafiem nākas ļoti bieži sastapties un katrs lieks krustojums izvietotajā grafa zīmējumā ir ļoti viegli pamanāms un traucējošs. Darbā aplūkoti grafu hierarhiskā izvietotāja darbības principi un piedāvāts virsotņu secības noteikšanas algoritms, kas piemērots retinātu grafu apstrādei. Uzmanība pievērsta grafu izvietotāju testēšanai un grafu ģenerēšanai. Piedāvātā algoritma pārbaudei izstrādāts līmeņplanāru grafu ģenerators. Darbā aprakstīta PQ-koka datu struktūrā un tās pielietojums jaunajā retināto grafu izvietošanas algoritmā. Jaunā algoritma darbības rezultāti salīdzināti ar pašreizējo, citu autoru, …