Graph with attenuation on arcs and amplifification in vertices and routing in information networks

Abstract

Graph with attenuation on arcs and amplifification in vertices and routing in information networks

Erusalimskiy Ya.M.

Incoming article date: 28.01.2015

Considered routing problem in information network in which there are arcs that does not affect the signal quality - neutral and reduce the signal quality - regressive, as well as vertices which improves signal quality - active, and vertices does not affect the signal quality - neutral. The problem reduces to finding the shortest path on the set of paths satisfying the additional restriction - on any segment of the path enclosed between two consecutive active vertices contains no more than a predetermined number of regressive arcs (the same applies to the segment from the beginning of the path to the first active vertex and from the last active vertex to the end of the path, as well as to the ways without active vertices). For such graphs described construction of the reamer - auxiliary graph that allows to find the solution of the problem with restrictions on the original graph as the solution of the corresponding problem without restrictions on the reamer.

Keywords: graph, path, reachability, reamer of graph, routing