14376

12994

كارشناسي ارشد

رياضي

اصفهان : دانشگاه صنعتي اصفهان

1397

[نه]، ۱۴۸ص.: مصور، جدول

بهناز عمومي

حامد فهيمي

انگليسي به فارسي ; فارسي به انگليسي

غلامرضا اميدي، رامين جوادي

1397/12/04

كتابنامه

رياضي

رياضي

1397/12/06

ID12994

The Impact of the Structure of Directed Graphs on Designing Optimal Algorithms Yasaman Yektaeian Master of Science Thesis in Farsi Departement of Mathematical Sciences Isfahan University of Technology Isfahan 84156 8311 IranSupervisor Prof Behnaz Omoomi bomoomi@cc iut ac irAdvisor Dr Hamed Fahimi2000 MSC 68R10 05C10 05C20 05C83 05C85Keywords Algorithmic Structural Graph Theory Algorithmic Meta Theorem Directed Width Measure Tree Width CLique Width Path Width Directed Tree Width D Width DAG Width Kelly Width Di rected Path Width Directed Clique WidthAbstract This M Sc thesis is based on the following papers Ganian R Hlin n P Kneis J Meister D Obdr lek J Rossmanith P Sikdar S Are there any good digraph width measures Journal of Combinatorial Theory Series B 116 250 86 2016 Graphs are important tools for modeling the real problems in science Many Np hard problems can be expressed inthe language of Graph Problems There are different approaches such as approximation algorithm fixed parameteralgorithm randomize algorithm and heuristic method to overcome hard problems and designing optimal algorithmsbut 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 indesigning optimal algorithms Tree width is a useful structural parameter in the class of undirected graphs that has asignificant effect on structural and algorithmic graph theory Intuitively tree width measures the similarity betweenan undirected graph and a tree Since many of Np hard problems in the class of trees become tractable this parameteris used to design optimal algorithms for those class of undirected graphs with bounded tree width Despite the existence of different definitions for the directed width parameter in the class of directed graphs no usefulparameter has been found yet The most important directed width parameters that have been defined so far are 1 directed tree width 2 directed path width 3 d width 4 DAG width 5 kelly width 6 directed clique width Parameters 1 2 3 4 and 5 have nice structural properties and intuitively they measure similarity betweena directed graph and a DAG parameter 6 is useful for algorithmic purposes By using directed clique width it ispossible to designe fixed parameter algorithm for a large class of special problems the problems that are definablein second order logic MSO MSO is suitable for defining properties and problems in graph theory The ability ofdesigning optimal algorithms by using a directed width parameter for MSO definable problems is a criterion forthe algorithmic usefulness Based on the success of the tree width parameter the following properties have beenconsidered as good properties for a directed width parameter Nice structural properties Algorithmic usefulnessIt is essential for a directed width parameter to have these properties because it should be at least as effective as tree width and the lack of a parameter that has both of these properties suggests this question Is there a good directionalparameter Unfortunately the answer is negative In this thesis first we will introduce the structural algorithmicgraph theory then some of the important directed width parameters are defined In the end we study the reason whydirected width parameters fail

بهناز عمومي

حامد فهيمي

غلامرضا اميدي، رامين جوادي