Fully polynomial-time computation of maximum likelihood trajectories in Markov chains

DOI10.1016/j.ipl.2016.09.012zbMath1392.68203OpenAlexW2528195968MaRDI QIDQ344537

Yuri Grinberg, Theodore J. Perkins

Publication date: 23 November 2016

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2016.09.012

zbMATH Keywords

computational complexityMarkov chainsgraph algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Graph algorithms (graph-theoretic aspects) (05C85)

Cites Work

• A characterization of the minimum cycle mean in a digraph
• Viterbi sequences and polytopes
• Error bounds for convolutional codes and an asymptotically optimum decoding algorithm

This page was built for publication: Fully polynomial-time computation of maximum likelihood trajectories in Markov chains