Artificial intelligence

Abstract: New method for finding shortest paths in two-level graphs with labeled vertices and edges is proposed. It enables to find one or several optimal paths between given vertices as well as labels and quality of these paths. Method is oriented on two-level graphs where each vertex of a first-level graph in a second-level graph. The method is based on the local reduction of a graph, that is, on a successive elimination of its vertices and edges.

Keywords: method for finding shortest paths, two-level graph, local reduction of a graph.

References:

1. Roberts F.S. Diskretnyie matematicheskie modeli s prilozheniyami k sotsialnyim biologicheskim iekologicheskim zadacham / F.S. Roberts ; red. A.I. Teyman; per. s angl. A.M. Rappoport, S.I. Travkin. –M. : Nauka, 1986. – 496 р.
2. Droste M. Handbook of Weighted Automata / M. Droste, W. Kurich, H. Vogler. – Berlin, Heidelberg : SpringerVerlag,2009 – 610 p.
3. Kristofides N. Teoriya grafov: algoritmicheskiy podhod / N. Kristofides. – M. : Mir, 1978. — 430 р.
4. Aho A. Postroenie i analiz vyichislitelnyih algoritmov / A. Aho, Dzh. Hopkroft, Dzh. Ulman. – M. : Mir,1979. – 536 s.
5. Batischev D.I. Mnogourovnevaya dekompozitsiya gipergrafovyih struktur / D.I. Batischev,N.V. Starostin, A.V. Filimonov // Prilozh. k zhurnalu «Informatsionnyie tehnologii». – № 5(141). – M. :Novyie tehnologii. – 2008. – 32 s.
6. Nogina N.V. Sintez regulyarnogo vyirazheniya yazyika, porozhdennogo pomechennyim grafom,metodom ego lokalnoy reduktsii / N.V. Nogina, I.S. Grunsky // Iskusstvennyiy intellekt. – 2012. – №3. –S. 348-353.
7. Nogina N.V. Postroenie kratchayshego puti v pomechennom grafe pri pomoschi lokalnoy reduktsiigrafa / N.V. Nogina, A.V. Bilyk // Suchasna Informatsіyna Ukraina: Informatika, ekonomіka, fіlosofіya:materіali dopovіdey konferentsіi, 26 kvіtnya 2012 roku. – Donetsk, 2012. – 316 s. – S. 76-79.
8. Bіlyk G.V. Metod pobudovi naykorotshih shlyahsv u dvorivnevomu grafi / G.V. BIlyk, I.S. Grunsky,N.V. Nogina // Informatsiyni upravlyayuchi sistemi ta kompyuterniy monitoring (IUS KM – 2013) :IV Vseukrainska naukovo-tehnichna konferentsiya studentiv, aspirantIv ta molodih vchenih, 24 –25 kvitnya 2013 r., m. Donetsk : zb. dop. / Donets. natsional. tehn. un-t; redkol. V.A. Svitlichna. –Donetsk : DonNTU, 2013. – V 2 tt. – T. 1. – 765 s. – S. 474–478.
9. Bilyk G.V. Poshuk naykorotshih shlyahiv v grafi dvorivnevoji strukturi. / G.V. Bilyk, I.S. Grunsky,N.V. Nogina // Intelektualni sistemi v promislovosti i osviti : tezi dopovidey Chetvertoji mizhnarodnojinaukovo-praktichnoji konferentsiji. – Sumi : Vid-vo SumDU, 2013. – (u drutsi).