string matching

http://www.cadmo.ethz.ch/education/lectures/HS07/acmlab/11_string_matching.pdf

قضیه کوک

مسأله‌ی تصدیق دودویی ان‌پی-کامل است.

http://en.wikipedia.org/wiki/Cook%E2%80%93Levin_theorem

کاربردهای شارش شبکه

*matching

(یک یال مجاور هر رأس انتخاب شود)

در حالت دوبخشی می‌توانیم آن را با وصل کردن یک بخش به مبدا و دیگری به مقصد حل کنیم.

الگوریتم‌های تطابق (به جز این موردی که گفتم)

http://www.dis.uniroma1.it/~sankowski/lecture2.pdf

*assignment

(اختصاص دادن کار به ماشین‌ها)

http://www.comp.nus.edu.sg/~rahul/CS3230-12_files/lectures/pearson/07assignment.pdf

http://www.me.utexas.edu/~jensen/models/network/net9.html

*transportation

(رساندن کالا به مشتری)

http://www.me.utexas.edu/~jensen/models/network/net8.html

*جایابی؟ (من مطمئن نبودم این چه مسأله‌ای است!)

http://people.orie.cornell.edu/dpw/techreports/cornell-flow.pdf

network flow: relabel to front

مرجع: http://people.scs.carleton.ca/~maheshwa/courses/5703COMP/Talks/Preflow/present.pdf

network flow: pre-flow push algorithm

مرجع: http://cseweb.ucsd.edu/classes/sp11/cse202-a/lecture8-final.pdf

http://cseweb.ucsd.edu/classes/sp11/cse202-a/lecture9-final.pdf