Skip to main content
SUPERVISOR
بهناز عمومی (استاد راهنما) حامد فهیمی (استاد مشاور)
 
STUDENT
Yasaman Yektaeian
یاسمن یکتائیان

FACULTY - DEPARTMENT

دانشکده ریاضی
DEGREE
Master of Science (MSc)
YEAR
1395

TITLE

The Impact of the Structures of Directed Graphs on Designing Optimal Algorithms
Graphs are important tools for modeling the real problems in science. Many Np-hard problems can be expressed in the language of Graph Problems. There are different approaches such as approximation algorithm, fixed parameter algorithm, randomize algorithm and heuristic method to overcome hard problems and designing optimal algorithms but these aproches can not find the optimal answer in the shortest possible time. One of the most beautiful approaches to overcome hard problems is the use of structural properties of graphs in designing optimal algorithms. Tree-width is a useful structural parameter in the effect on structural and algorithmic graph theory.
یکی از رویکرد‌های غلبه بر مسائل سخت گرافی استفاده از ویژگی‌های ساختاری گراف در حوزه طراحی الگوریتم است. در کلاس گراف‌های بدون جهت پارامتر عرض درختی مهمترین مفهومی است که نظریه ساختاری و الگوریتمی گراف‌ را به هم مرتبط می‌سازد. این پارامتر به‌طور شهودی میزان شباهت گراف‌های بدون جهت را به درخت مشخص می‌کند. از آنجایی که برای بسیاری از مسائل سخت گرافی در کلاس درخت‌ها الگوریتم‌های بهینه وجود دارد، از این پارامتر در راستای طراحی الگوریتم در کلاس‌های گسترده‌تر گرافی استفاده می‌شود. در کلاس گراف‌های جهت‌دار علی رغم وجود تعاریف متعدد برای پارامترهای ساختاری تاکنون پارامتری تأثیرگذار در حوزه طراحی الگوریتم یافته نشده است. در این پایان نامه ابتدا نظریه ساختاری و الگوریتمی گراف‌های بدون جهت را معرفی می‌کنیم. سپس به معرفی مهمترین پارامتر‌های جهت‌دار می‌پردازیم و علت ناکامی در یافتن تعریفی مناسب برای پارامتر جهت‌دار را بررسی می‌کنیم.

ارتقاء امنیت وب با وف بومی