K shortest-paths in Vcsn

From LRDE

Revision as of 17:06, 9 January 2018 by Bot (talk | contribs) (Created page with "{{CSIReport | authors = Sébastien Piat | title = K shortest-paths in Vcsn | year = 2017 | number = 1701 | abstract = The K shortest paths computation can be very time consumi...")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

Abstract

The K shortest paths computation can be very time consuming especially when applied to the enormous automata used in linguistics. Hence, after having implemented one of the state-of-the-art solution to the problem (namely Yen's algorithm) in Vcsn, the next step was to implement the best known solution for automata with cycles: Eppstein. This work will describe our different implementations and compare their performances.