מבחן מועד א

arisha84

unread,

Aug 8, 2009, 4:08:25 AM8/8/09

to Complexity Course, Spring 2009, Tel Aviv University

מישהו יכול להסביר את הפתרון לשאלה 2 ב (gap-5-coloring) מהמבחן של מועד
א'?

daniel...@gmail.com

unread,

Aug 8, 2009, 5:40:11 AM8/8/09

to Complexity Course, Spring 2009, Tel Aviv University

החלק הראשון נלמד בשיעור 11
רדוקציה מ 5צביע לבעיית IS

בעיית 5צביע היא מקרה פרטי של 5CSG ולכן יש אליה רדוקציה.

רדוקציה מ 5CSG אל IS:
במהלך הרדוקציה כל קודקוד הופך לקליק בגודל 5, לכן ב IS יכול להיות רק
קודקוד אחד מכל קליק
כלום אם יכולת לצבוע an. קודקודים, עכשיו ה IS המקסימלי יהיה an/5.

רדוקציה מ IS אל VC:
רדוקצית הזהות:
נניח שמצאת VC בגרף, אז הקודקודים בו נוגעים בכל קשתות הגרף
שאר הקודקודים שלא ב VC, לא מקושרים ביניהם, ולכן הם IS.
לכן, אם מצאת VC בגודל an מצאת IS בגודל n-an.

Anna

unread,

Aug 8, 2009, 7:54:23 AM8/8/09

to Complexity Course, Spring 2009, Tel Aviv University

יש באתר פתרונות:
וזה פתרון של שאלה 2
http://www.cs.tau.ac.il/~odedr/teaching/complexity_spring_2009/cc09b-a-sol2%5B1%5D.doc

Reply all

Reply to author

Forward