Prikladnaya Diskretnaya Matematika. Supplement
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Prikl. Diskr. Mat. Suppl.:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Prikladnaya Diskretnaya Matematika. Supplement, 2019, Issue 12, Pages 186–191
DOI: https://doi.org/10.17223/2226308X/12/52
(Mi pdma467)
 

Applied Theory of Automata and Graphs

Approximate algorithm for searching shortest path in multiservice network with constrained resource

A. A. Soldatenko

Institute of Mathematics and Computer Science, Siberian Federal University, Krasnoyarsk
References:
Abstract: In the paper, we consider the Resource Constrained Shortest Path problem (RCSP). This problem is NP-hard extension of a well-known shortest path problem in the directed graph $G = (V, E)$. In the RCSP problem each arc $e$ from $E$ has a cost $w(e)$ and additional weight functions $r_i(e)$, $i = 1, \dots, k$, which specifying its requirements from a finite set of resource. The RCSP problem has various practical applications, including design and operation of multi-service network. Nowadays, multi-service networks grow at a rapid pace. Therefore, it is relevant to search for a new approximation algorithms that can solve the RCSP problem quickly. This paper reviews existing approximation algorithms for the RCSP problem. A polynomial time $\varepsilon$-approximation algorithm RevTree based on node labeling method is presented in the paper. The main advantage of the RevTree algorithm over existing ones is its ability to produce $\varepsilon$ approximation of the RCSP problem in $\mathcal{O}(\mathopen|V\mathclose|^2)$ time. For real networks, $\varepsilon$ can be calculate using values of $w(e)$ and $r_i(e)$, $e \in E$. The paper provides a description of the RevTree algorithm and results of computational experiments, which justify the effectiveness of proposed algorithm.
Keywords: resource constrained shortest path, graph-based algorithm, optimal routing, computer and multi-service networks.
Bibliographic databases:
Document Type: Article
UDC: 519.7
Language: Russian
Citation: A. A. Soldatenko, “Approximate algorithm for searching shortest path in multiservice network with constrained resource”, Prikl. Diskr. Mat. Suppl., 2019, no. 12, 186–191
Citation in format AMSBIB
\Bibitem{Sol19}
\by A.~A.~Soldatenko
\paper Approximate algorithm for searching shortest path in multiservice network with constrained resource
\jour Prikl. Diskr. Mat. Suppl.
\yr 2019
\issue 12
\pages 186--191
\mathnet{http://mi.mathnet.ru/pdma467}
\crossref{https://doi.org/10.17223/2226308X/12/52}
\elib{https://elibrary.ru/item.asp?id=41153927}
Linking options:
  • https://www.mathnet.ru/eng/pdma467
  • https://www.mathnet.ru/eng/pdma/y2019/i12/p186
  • Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Prikladnaya Diskretnaya Matematika. Supplement
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024