All a b c d e f g h i j k l m n o p q r s t u v w x y z Other

Page 1

Displaying 1 – 4 of 4

Showing per page

Labeled shortest paths in digraphs with negative and positive edge weights

Phillip G. Bradford, David A. Thomas (2009)

RAIRO - Theoretical Informatics and Applications

This paper gives a shortest path algorithm for CFG (context free grammar) labeled and weighted digraphs where edge weights may be positive or negative, but negative-weight cycles are not allowed in the underlying unlabeled graph. These results build directly on an algorithm of Barrett et al. [SIAM J. Comput.30 (2000) 809–837]. In addition to many other results, they gave a shortest path algorithm for CFG labeled and weighted digraphs where all edges are nonnegative. Our algorithm is based closely...

Linear and metric maps on trees via Markov graphs

Sergiy Kozerenko (2018)

Commentationes Mathematicae Universitatis Carolinae

The main focus of combinatorial dynamics is put on the structure of periodic points (and the corresponding orbits) of topological dynamical systems. The first result in this area is the famous Sharkovsky's theorem which completely describes the coexistence of periods of periodic points for a continuous map from the closed unit interval to itself. One feature of this theorem is that it can be proved using digraphs of a special type (the so-called periodic graphs). In this paper we use Markov graphs...

Currently displaying 1 – 4 of 4

Page 1