Knuth's Simpath algorithm

Simpath is an algorithm introduced by Donald Knuth that constructs a zero-suppressed decision diagram (ZDD) representing all simple paths between two vertices in a given graph.[1][2]

References

Knuth, Donald (2011). The Art of Computer Programming, Volume 4A. Addison-Wesley Professional: Boston, MA, USA. p. 254,275.
Yoshinaka, Ryo; Saitoh, Toshiki; Kawahara, Jun; Tsuruma, Koji; Iwashita, Hiroaki; Minato, Shin-Ichi (2012). "Finding All Solutions and Instances of Numberlink and Slitherlink by ZDDs". Algorithms. 5 (2): 176–213. doi:10.3390/a5020176.

Graphillion library which implements the algorithm for manipulating large sets of paths and other structures.
, A CWEB implementation by Donald Knuth.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

Donald Knuth
Publications	The Art of Computer Programming "The Complexity of Songs" Computers and Typesetting Concrete Mathematics Surreal Numbers Things a Computer Scientist Rarely Talks About Selected papers series
Software	TeX Metafont MIXAL (MIX MMIX GNU MDK)
Fonts	AMS Euler Computer Modern Concrete Roman
Literate programming	WEB CWEB
Algorithms	Knuth's Algorithm X Knuth–Bendix completion algorithm Knuth–Morris–Pratt algorithm Knuth shuffle Robinson–Schensted–Knuth correspondence Trabb Pardo–Knuth algorithm Generalization of Dijkstra's algorithm Knuth's Simpath algorithm
Other	Dancing Links Knuth reward check Knuth Prize Man or boy test Quater-imaginary base -yllion Potrzebie system of weights and measures