Mathematics and Statistics Vol. 8(6), pp. 699 - 704
DOI: 10.13189/ms.2020.080610
Reprint (PDF) (300Kb)

Generalization of the Reachability Problem on Directed Graphs

Vladimir A. Skorokhodov ^*
Institute of Mathematics, Mechanics and Computer Science, Southern Federal University, Rostov-on-Don, Milchakova 8a, 344090, Russia

ABSTRACT

The problem of reachability on graphs with restriction is studied. Such restrictions mean that only those paths that satisfy certain conditions are valid paths on the graph. Because of this, for classical optimization problems one has to consider only a subset of feasible paths on the graph, which significantly complicates their solution. Reachability constraints arise naturally in various applied problems, for example, in the problem of navigation in telecommunication networks with areas of strong signal attenuation or when modeling technological processes in which there is a condition for the order of actions or the compatibility of operations. General concepts of a graph with non-standard reachability and a valid path on it are introduced. It is shown that the classical graphs, as well as graphs with restrictions on passing through the selected arcs subsets are special cases of graphs with non-standard reachability. General approach to solving the shortest path problem on a graph with non-standard achievability is developed. This approach consists in constructing an auxiliary graph and reducing the shortest path problem on a graph with non-standard reachability to a similar problem on an auxiliary graph. The theorem on the correspondence of the paths of the original and auxiliary graphs is proved.

KEYWORDS
Graphs, Reachability, Shortests Path Problem, Non-Standard Reachability, Auxiliary Graph, Reachability Constraints

Cite This Paper in IEEE or APA Citation Styles
(a). IEEE Format:
[1] Vladimir A. Skorokhodov , "Generalization of the Reachability Problem on Directed Graphs," Mathematics and Statistics, Vol. 8, No. 6, pp. 699 - 704, 2020. DOI: 10.13189/ms.2020.080610.

(b). APA Format:
Vladimir A. Skorokhodov (2020). Generalization of the Reachability Problem on Directed Graphs. Mathematics and Statistics, 8(6), 699 - 704. DOI: 10.13189/ms.2020.080610.