On shortest path problems with “non-markovian” link contribution to path lengths

Arunabha Sen, Kasim Candan, Afonso Ferreira, Bruno Beauquier, Stephane Perennes

Research output: Chapter in Book/Report/Conference proceedingConference contribution

9 Scopus citations


In this paper we introduce a new class of shortest path problems, where the contribution of a link to the path length computation depends not only on the weight of that link but also on the weights of the links already traversed. This class of problems may be viewed as "non-Markovian". We consider a specific problem that belong to this class, which is encountered in the multimedia data transmission domain. We consider this problem under different conditions and develop algorithms. The shortest path problem in multimedia data transmission environment can be solved in O(n2) or O(n3) computational time.

Original languageEnglish (US)
Title of host publicationNETWORKING 2000
Subtitle of host publicationBroadband Communications, High Performance Networking, and Performance of Communication Networks - IFIP-TC6/European Commission International Conference, Proceedings
EditorsGuy Pujolle, Harry Perros, Serge Fdida, Ulf Korner, Ioannis Stavrakakis
PublisherSpringer Verlag
Number of pages12
ISBN (Print)354067506X, 9783540675068
StatePublished - 2000
EventIFIP-TC6/European Commission International Conference on Networking, NETWORKING 2000 - Paris, France
Duration: May 14 2000May 19 2000

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


OtherIFIP-TC6/European Commission International Conference on Networking, NETWORKING 2000

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'On shortest path problems with “non-markovian” link contribution to path lengths'. Together they form a unique fingerprint.

Cite this