Çizgelerde baskın kümeyi bulmak için Malatya merkezilik değerlerini kullanan yeni bir yöntem önerisi
| dc.contributor.advisor | Okumuş, Üyesı? Fatı?h | |
| dc.contributor.author | Karcı, Şeyda | |
| dc.date.accessioned | 2024-08-11T19:26:05Z | |
| dc.date.available | 2024-08-11T19:26:05Z | |
| dc.date.issued | 2023 | |
| dc.department | Enstitüler, Fen Bilimleri Enstitüsü, Bilgisayar Mühendisliği Ana Bilim Dalı | en_US |
| dc.description.abstract | Baskın küme problemi (dominating set problem), çizge teorisinde üzerinde oldukça çalışılan bir problem olup karmaşıklık olarak NP-Tam problemler grubuna girmektedir. Bundan dolayı günümüze kadar bu problemin çözümü için yapılan çalışmalar üç grupta toplanabilir. Sezgisel yöntemler, tam yöntemler ve yaklaşık yöntemler şeklinde gruplandırılabilirler. Sezgisel yöntemler sağlam olmayan her zaman aynı çizge için aynı sonucu veremeyen yöntemlerdir ve bu yöntemler olasılık tabanlı olup karmaşıklık analizleri çoğunlukla yapılmaz. İkinci grupta yer alan tam yöntemlerde ise, çözüm olabilecek bütün durumlar denenir ve ondan sonra çözüm ortaya konulur. Bu yöntemler çalışabildikleri çizgeler için minimum çözümü garanti ederler fakat zaman veya uzay karmaşıklıkları üstel olan yöntemlerdir. Son grupta yer alan yöntemler ise, minimum çözüm iddiaları olmayan yaklaşık çözüm noktasında da kesin iddiaları olmayan yöntemlerdir. Bu tez çalışmasında Malatya Merkezilik kavramının ikincisinin çizge teorisi problemlerinden olan Baskın Küme probleminin çözümü için kullanılabileceği iddiası ortaya konuldu. Malatya Merkezilik yönteminin kullanılması önerilecek yöntemin zaman ve uzay karmaşıklıklarının polinomsal olmasını sağlayacaktır. Aynı zamanda önerilen yöntemin bazı çizge grupları için minimum çözümü elde ettiği ortaya konuldu ve geriye kalan çizgelerde ise, minimum çözüme çok yakın sonuçlar elde edebildiği ortaya konulmuştur (minimum çözümden bir fazla düğümlü çözüm bulması gibi). Tez çalışmasında İkinci Malatya Merkezilik kavramı kullanıldı ve bu yöntemin ilk kullanıldığı tez çalışması oldu. İkinci Malatya Merkezilik kavramının baskın küme probleminin çözümü için kullanılabileceği yorumlarla gösterildikten sonra önerilen yöntemin kodlamaları gerçekleştirildi ve sonuçlar kodlaması gerçekleştirilen yöntemden elde edilmiştir. | en_US |
| dc.description.abstract | The dominating set problem is a widely studied problem in graph theory and falls into the group of NP-Complete problems in terms of complexity. Therefore, the studies carried out to date to solve this problem can be grouped into three groups. They can be grouped as heuristic methods, exact methods, and approximate methods. The heuristic methods are methods that are not robust and cannot always give the same result for the same graph, and these methods are probability*based and complexity analyses are often not performed. In the exact methdos, all feasible solutions are tried and then the solution is presented. These methods guarantee a minimum solution for the graphs they work with, but their time or space complexity is exponential. The methods in the last group are methods that do not have minimum solution claims, nor do they make definitive claims about the approximate solution. The concept of Second Malatya Centrality was used in the this thesis study, and it was the first thesis study in which this method was used. After showing with comments that the Second Malatya Centrality concept can be used to solve the dominating set problem, the implementation of the proposed method was carried out and the results were obtained from the implementation. In this thesis, is is claimed that the Second Malatya Centrality concept can be used to solve the Dominating Set Problem, which is one of the graph theory problems. It will ensure that the proposed method which is based on the Second Malatya Centrality conept, the time and space complexities of the propoed method are polynomial. It was revealed that the proposed method obtained the minimum solution for some graph groups, and in the remaining graphs, it was revealed that it could obtain results very close to the minimum solution (such as finding a solution with one more node than the minimum solution). | en_US |
| dc.identifier.endpage | 44 | en_US |
| dc.identifier.startpage | 1 | en_US |
| dc.identifier.uri | https://tez.yok.gov.tr/UlusalTezMerkezi/TezGoster?key=weFMBHaUra8rsS5wi2bmHGTJ3ELbp0mDv-chbfDLg53udrtCI3ejFFk5tbQZJ60p | |
| dc.identifier.uri | https://hdl.handle.net/11616/104932 | |
| dc.identifier.yoktezid | 844534 | en_US |
| dc.language.iso | tr | en_US |
| dc.publisher | İnönü Üniversitesi | en_US |
| dc.relation.publicationcategory | Tez | en_US |
| dc.rights | info:eu-repo/semantics/openAccess | en_US |
| dc.subject | Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol | en_US |
| dc.subject | Computer Engineering and Computer Science and Control | en_US |
| dc.title | Çizgelerde baskın kümeyi bulmak için Malatya merkezilik değerlerini kullanan yeni bir yöntem önerisi | en_US |
| dc.title.alternative | A new method proposed using Malatya centrality values to find the dominating set in graphs | en_US |
| dc.type | Master Thesis | en_US |
