Knuth's Simpath algorithm: Difference between revisions

Content deleted Content added

Inline

Revision as of 23:19, 17 April 2020

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.

External links

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

This algorithms or data structures-related article is a stub. You can help Wikipedia by expanding it.

[1] Knuth, Donald (2011). The Art of Computer Programming, Volume 4A. Addison-Wesley Professional: Boston, MA, USA. p. 254,275.

[2] 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.

[1]

[2]

Revision as of 06:56, 16 August 2019 edit Citation bot (talk \| contribs) Bots 5,650,308 edits m Add: issue, author pars. 1-6. \| You can use this bot yourself. Report bugs here.\| Activated by User:Corvusphalanx ← Previous edit		Revision as of 23:19, 17 April 2020 edit undo OAbot (talk \| contribs) Bots 596,200 edits m Open access bot: doi added to citation with #oabot. Next edit →
Line 1:		Line 1:
	'''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.<ref>{{cite book\|last1=Knuth\|first1=Donald\|title=The Art of Computer Programming, Volume 4A\|date=2011\|publisher=Addison-Wesley Professional: Boston, MA, USA\|page=254,275}}</ref><ref>{{cite journal\|title=Finding All Solutions and Instances of Numberlink and Slitherlink by ZDDs\|journal=Algorithms\|date=2012\|volume=5\|issue=2\|pages=176–213\|doi=10.3390/a5020176\|last1=Yoshinaka\|first1=Ryo\|last2=Saitoh\|first2=Toshiki\|last3=Kawahara\|first3=Jun\|last4=Tsuruma\|first4=Koji\|last5=Iwashita\|first5=Hiroaki\|last6=Minato\|first6=Shin-Ichi}}</ref>		'''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.<ref>{{cite book\|last1=Knuth\|first1=Donald\|title=The Art of Computer Programming, Volume 4A\|date=2011\|publisher=Addison-Wesley Professional: Boston, MA, USA\|page=254,275}}</ref><ref>{{cite journal\|title=Finding All Solutions and Instances of Numberlink and Slitherlink by ZDDs\|journal=Algorithms\|date=2012\|volume=5\|issue=2\|pages=176–213\|doi=10.3390/a5020176\|last1=Yoshinaka\|first1=Ryo\|last2=Saitoh\|first2=Toshiki\|last3=Kawahara\|first3=Jun\|last4=Tsuruma\|first4=Koji\|last5=Iwashita\|first5=Hiroaki\|last6=Minato\|first6=Shin-Ichi\|doi-access=free}}</ref>

	==References==		==References==

v t e 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)
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 Knuth's up-arrow notation Man or boy test Quater-imaginary base -yllion Potrzebie system of weights and measures