Directed graphs, Hamiltonicity and doubly stochastic matrices

Borkar, Vivek S. ; Ejov, Vladimir ; Filar, Jerzy A. (2004) Directed graphs, Hamiltonicity and doubly stochastic matrices Random Structures & Algorithms, 25 (4). pp. 376-395. ISSN 1042-9832

Full text not available from this repository.

Official URL:

Related URL:


We consider the Hamiltonian cycle problem embedded in singularly perturbed (controlled) Markov chains. We also consider a functional on the space of stationary policies of the process that consists of the (1,1)-entry of the fundamental matrices of the Markov chains induced by the same policies. In particular, we focus on the subset of these policies that induce doubly stochastic probability transition matrices, which we refer to as the "doubly stochastic policies." We show that when the perturbation parameter ε is sufficiently small the minimum of this functional over the space of the doubly stochastic policies is attained very close to a Hamiltonian cycle, provided that the graph is Hamiltonian. We also derive precise analytical expressions for the elements of the fundamental matrix that lend themselves to probabilistic interpretation as well as asymptotic expressions for the first diagonal element, for a variety of deterministic policies that are of special interest, including those that correspond to Hamiltonian cycles.

Item Type:Article
Source:Copyright of this article belongs to John Wiley and Sons.
Keywords:Hamiltonian Cycle; Controlled Markov Chains; Optimal Policy; Singular Perturbation
ID Code:81457
Deposited On:06 Feb 2012 05:22
Last Modified:06 Feb 2012 05:22

Repository Staff Only: item control page