[-] שאלת קיטבג בקשר ל-"אלג' שזמן ריצתו הינו פחות מריבועי"
by rotemrei - Wednesday, 13 June 2012 16:47:47
מקוה שלא אצטער ששאלתי את זה:

בשאלה 1.ג:
האם ניתן להשתמש ברדוקציה בקופסא שחורה לפתרון בעית זרימה שמשתמשת באחד האלג' שלמדנו -  שרצים תוך זמן ריבועי בגודל קבוצת הקדקודים או קבוצת הצלעות בגרף?
או שצריך לעשות שינוי באלג' לבעיית הזרימה (ואז זו לא באמת רדוקציה) 

תודה
thread
[-] Re: שאלת קיטבג בקשר ל-"אלג' שזמן ריצתו הינו פחות מריבועי"
by fedidash - Wednesday, 13 June 2012 17:48:40
לא מבינה על מה יש להצטער. ממה שאני הבנתי אתה צריך להשתמש ברדוקציה שכתבת בשלבים הקודמים ולבחור אלגוריתם למציאת זרימה מקסימלית כזה שירוץ בזמן קטן מ ריבועי ביחס לגודל הקלט.
thread
[-] האלגוריתמים שלמדנו למציאת זרימה מקסימלית:
by rotemrei - Wednesday, 13 June 2012 20:31:09
Dinitz: O(V^2E)
Edmond's crap: O(VE^2)
Ford-Fulkerson: O(Ef)

מכיון שאנחנו צריכים להפוך את החתנים, הכלות והדירות לקדקודים בגרף, ונניח שכל דירה וחתן מופיעים לפחות ברשימה אחת, כל האלג' הנ"ל ירוצו על קבוצת הקדקודים (או על קבוצת הצלעות שבהכרח גדולה ממנה) לפחות באופן ריבועי.

 ולכן, שאלת הקיטבג שלי נשארת בעינה.

thread
Re: האלגוריתמים שלמדנו למציאת זרימה מקסימלית:
by rotemgol - Wednesday, 13 June 2012 21:42:08
זמני הריצה הרשומים לעיל נכונים עבור רשת זרימה כלשהיא.
בשאלה אתה מתבקש לתאר אלג' המוצא זרימה מקסימלית ברשת המתקבלת מהרדוקציה.
ניתן להשתמש בחומר הנלמד במהלך הקורס.

thread