Show simple item record

dc.contributor Graduate Program in Industrial Engineering.
dc.contributor.advisor Aşıcı, Tınaz Ekim.
dc.contributor.author Çelebi, Cemre.
dc.date.accessioned 2024-03-12T14:52:05Z
dc.date.available 2024-03-12T14:52:05Z
dc.date.issued 2022
dc.identifier.other IE 2022 C45
dc.identifier.uri http://digitalarchive.boun.edu.tr/handle/123456789/21452
dc.description.abstract The aim of this thesis is to develop exact and heuristic methods to solve the Maximum Acyclic Matching problem, which deals with obtaining maximum matching such that the subgraph induced by saturated vertices is acyclic. The maximum matching problem tries to find the most extensive possible matching set. it is a well-studied problem that can be solved with combinatorial algorithms. However, for the maximum acyclic matching problem, we are searching for not only a maximum size matching but also we require that the subgraph induced by saturated vertices does not contain any cycles. For this purpose, an additional acyclicity constraint is needed. Even though some exact and approximate algorithms are established for particular graph classes, there is no such algorithm applicable for general graphs to find a maximum acyclic matching. In this study, four algorithms are suggested. Randomly generated graphs with different density levels and sizes are used to analyze their performance. Two of the algorithms are exact algorithms, which are extensive and cutting plane formulations. Based on experimental results, the cutting plane approach performs better since it works also with larger graphs. The other two algorithms are heuristics, which are modification and construction approaches. It is observed that the construction approach performs better than the modification approach in terms of both time efficiency and quality. The construction approach yields feasible and close-to-optimal results in a shorter period. When the results of the best exact and heuristics are compared, the cutting plane algorithm performs better based on optimality. However, it is not applicable for large graphs compared to the construction algorithm. Additionally, it is seen that the effect of acyclicity constraint is increasing while graph size and density are getting larger.
dc.format.extent 111:001:PDF:b2795643:038383:0:0:0:0:0:0tFull text electronic versionvn
dc.publisher Thesis (M.S.) - Bogazici University. Institute for Graduate Studies in Science and Engineering, 2022.
dc.subject.lcsh Matching theory.
dc.subject.lcsh Acyclic models.
dc.title The maximum acyclic matching problem
dc.format.pages x, 27 leaves


Files in this item

This item appears in the following Collection(s)

Show simple item record

Search Digital Archive


Browse

My Account