BSU Bulletin. Mathematics, Informatics
Bibliographic description:
, ALGORITHM FOR TRANSFORMING AN ORIENTED GRAPH INTO AN ACYCLIC ONE // BSU Bulletin. Mathematics, Informatics. - 2019. №1. . - С. 13-21.
Title:
ALGORITHM FOR TRANSFORMING AN ORIENTED GRAPH INTO AN ACYCLIC ONE
Financing:
Codes:
Annotation:
Over the past five years together with experts in various fields of knowledge we have solved a number of urgent problems. Using elements of graph theory, we con- structed original economic algorithms to study the models under consideration and tested them on real data. The article is a continuation of researches in this field, and the current task has been formulated by experts in bioengineering.
At the first stage, a factorization by equivalence relation was carried out in the di- graph, we identified input and output vertices (of inward and outward edges) in each cluster using the previously developed by us economic algorithm. At the sec- ond stage, each cluster was replaced by means of an algorithm of wave front with its acyclic subgraph connecting the input vertices with the output paths of the minimal length. Further, the initial digraph was replaced by an acyclic digraph without feedbacks connecting input and output vertices of clusters.
At the first stage, a factorization by equivalence relation was carried out in the di- graph, we identified input and output vertices (of inward and outward edges) in each cluster using the previously developed by us economic algorithm. At the sec- ond stage, each cluster was replaced by means of an algorithm of wave front with its acyclic subgraph connecting the input vertices with the output paths of the minimal length. Further, the initial digraph was replaced by an acyclic digraph without feedbacks connecting input and output vertices of clusters.
Keywords:
digraph; cyclic equivalence; cluster; partial order; feedback; acyclic graph; wavefront algorithm; input vertices; output vertices; weekend peaks; graph path.
List of references:
Tsitsiashvili G. Sh., Osipova M. A., Losev A. S. Algoritmy klasterizatsii grafov [Graph Clustering Algorithms]. Vestnik Voronezhskogo gosudarstvennogo universi- teta. Seriya: fizika i matematika. 2016. No. 1. Pp. 145–149.
Tsitsiashvili G. Sh., V. P. Bulgakov, A. S. Losev. Hierarchical Classification of Directed Graph Nodes and Application of Protein Networks. Biostat. Biometrics Open Acc. J. 2017. V. 1, iss. 4. DOI: 10.19080/BBOAJ.2017.01.555567.
Tsitsiashvili G. Sh., Bulgakov V. P., Losev A. S. Hierarchical Classification of Directed Graph with Cyclically Equivalent Nodes. Applied Mathematical Sciences. 2016. V. 10, no. 51. Pp. 2529–2536.
Tsitsiashvili G. Sh., Bulgakov V. P., Losev A. S., Osipova M. A., Yu. N. Khar- chenko. Analysis of Hubs Loads in Biological Networks. Reliability: Theory and Ap- plications. 2014. V. 9, no. 2. Pp. 7–10.
Tsitsiashvili G. Sh., Bulgakov V. P., Losev A. S., Osipova M. A., Kharchenko Yu. N. Construction of Subgraph from Graph Shortest Way. Applied Mathematical Sciences. 2015. V. 9, no. 79. Pp. 3911–3916.
Tsitsiashvili G., Bulgakov V., Losev A. Replacement of Directed Graph by Acyclic Directed Graph and Its Application in Biostatistics. Journal of Biometrics & Biostatistics. 2018. V. 9, no. 1. DOI: 10.4172/2155-6180.1000390.
Tsitsiashvili G. Sh., V. P. Bulgakov, A. S. Losev. Hierarchical Classification of Directed Graph Nodes and Application of Protein Networks. Biostat. Biometrics Open Acc. J. 2017. V. 1, iss. 4. DOI: 10.19080/BBOAJ.2017.01.555567.
Tsitsiashvili G. Sh., Bulgakov V. P., Losev A. S. Hierarchical Classification of Directed Graph with Cyclically Equivalent Nodes. Applied Mathematical Sciences. 2016. V. 10, no. 51. Pp. 2529–2536.
Tsitsiashvili G. Sh., Bulgakov V. P., Losev A. S., Osipova M. A., Yu. N. Khar- chenko. Analysis of Hubs Loads in Biological Networks. Reliability: Theory and Ap- plications. 2014. V. 9, no. 2. Pp. 7–10.
Tsitsiashvili G. Sh., Bulgakov V. P., Losev A. S., Osipova M. A., Kharchenko Yu. N. Construction of Subgraph from Graph Shortest Way. Applied Mathematical Sciences. 2015. V. 9, no. 79. Pp. 3911–3916.
Tsitsiashvili G., Bulgakov V., Losev A. Replacement of Directed Graph by Acyclic Directed Graph and Its Application in Biostatistics. Journal of Biometrics & Biostatistics. 2018. V. 9, no. 1. DOI: 10.4172/2155-6180.1000390.
Article.pdf