The shortest path problem for a multiple graph

A. V. Smirnov

Modelirovanie i analiz informacionnyh sistem, Tome 24 (2017) no. 6, pp. 788-801.

Résumé

In the article, the definition of an undirected multiple graph of any natural multiplicity $k>1$ is stated. There are edges of three types: ordinary edges, multiple edges and multi-edges. Each edge of the last two types is the union of $k$ linked edges, which connect 2 or $k+1$ vertices, correspondingly. The linked edges should be used simultaneously. If a vertex is incident to a multiple edge, it can be also incident to other multiple edges and it can be the common ending vertex to $k$ linked edges of some multi-edge. If a vertex is the common end of some multi-edge, it cannot be the common end of any other multi-edge. Also, a class of the divisible multiple graphs is considered. The main peculiarity of them is a possibility to divide the graph into $k$ parts, which are adjusted on the linked edges and which have no common edges. Each part is an ordinary graph. The following terms are generalized: the degree of a vertex, the connectedness of a graph, the path, the cycle, the weight of an edge, and the path length. There is stated the definition of the reachability set for the ordinary and multiple edges. The adjacency property is defined for a pair of reachability sets. It is shown, that we can check the connectedness of some multiple graph with the polynomial algorithm based on the search for the reachability sets and testing their adjacency. There is considered a criterion of the existence of a multiple path between two given vertices. The shortest multiple path problem is stated. Then we suggest an algorithm of finding the shortest path in a multiple graph. It uses Dijkstra's algorithm of finding the shortest paths in subgraphs, which correspond to different reachability sets.

Détail

Keywords: multiple graph, reachability set, connectedness, multiple path, shortest path.
Mots-clés : divisible graph

Bibliographie

[1] Cormen T. H., Leiserson C. E., Rivest R. L., Stein C., Introduction to Algorithms, 3rd ed., The MIT Press, McGraw-Hill Book Company, 2009 | MR

[2] Berge C., Graphs and Hypergraphs, North-Holland Publishing Company, 1973 | MR | Zbl

[3] Basu A., Blanning R. W., “Metagraphs in workflow support systems”, Decision Support Systems, 25:3 (1999), 199–208 | DOI | MR

[4] Basu A., Blanning R. W., Metagraphs and Their Applications, Integrated Series in Information Systems, 15, Springer US, 2007 | Zbl

[5] Rublev V. S., Smirnov A. V., “Flows in Multiple Networks”, Yaroslavsky Pedagogichesky Vestnik, 3:2 (2011), 60–68 (in Russian)

[6] Smirnov A. V., “The Problem of Finding the Maximum Multiple Flow in the Divisible Network and its Special Cases”, Automatic Control and Computer Sciences, 50:7 (2016), 527–535 | DOI

[7] Ford L. R., Fulkerson D. R., Flows in Networks, Princeton University Press, 1962 | MR | Zbl

[8] Roublev V. S., Smirnov A. V., “The Problem of Integer-Valued Balancing of a Three-Dimensional Matrix and Algorithms of Its Solution”, Modeling and Analysis of Information Systems, 17:2 (2010), 72–98 (in Russian)

[9] Smirnov A. V., “Some Solvability Classes for the Problem of Integer Balancing of a Three-Dimensional Matrix with Constraints of the Second Type”, Automatic Control and Computer Sciences, 48:7 (2014), 543–553 | DOI

[10] Smirnov A. V., “Network Model for The Problem of Integer Balancing of a Four-dimensional Matrix”, Modeling and Analysis of Information Systems, 23:4 (2016), 466–478 (in Russian) | MR

[11] Korbut A. A., Finkelstein J. J., Diskretnoe programmirovanie, Nauka, M., 1969 (in Russian) | MR

[12] Raskin L. G., Kirichenko I. O., Mnogoindeksnye zadachi lineynogo programmirovaniya, Radio i svyaz, M., 1982 (in Russian) | MR

[13] Spieksma F. C. R., “Multi index assignment problems: complexity, approximation, applications”, Nonlinear Assignment Problems. Algorithms and Applications, eds. P. M. Pardalos, L. S. Pitsoulis, Kluwer Academic Publishers, 2000, 1–11 | MR

[14] Roublev V. S., Smirnov A. V., “$NP$-Completeness of the Integer Balancing Problem for a Three-Dimensional Matrix”, Doklady Mathematics, 82:3 (2010), 912–914 | DOI | MR | Zbl

[15] Dijkstra E. W., “A Note on Two Problems in Connexion with Graphs”, Numerische Mathematik, 1:1 (1959), 269–271 | DOI | MR | Zbl