Minimum spanning tree problems with conflict constraints

Çatışma kısıtlı enküçük kapsar ağaç problemi, enbüyük ağırlıklı kapsar küme ile enküçük kapsar ağaç problemlerinin bir birleşimidir ve NP-zor olduğu kanıtlanmıştır. Bu tez, çatışma kısıtları nedeniyle belirli kenar çiftlerinin aynı anda çözümde yer alamadığı çizgelerde bu problemi ele almaktadır. Çatışma kısıtları özellikle kaynak kısıtlamaları, düzenleyici kurallar veya fiziksel kısıtlamaların belli bağlantıların bir arada var olmasını engellediği senaryolarda, ağ tasarımı uygulamaları için çok önemlidir. Problemin karmaşık çözüm uzayını etkili bir şekilde taramak için dört farklı dal-sınır algoritması geliştirildi. Her algoritma, yenilikçi stratejiler kullanarak hesaplama verimliliğini artırmayı ve kısa sürede etkili çözümler sunmayı hedeflemektedir. Deneysel sonuçlar geliştirilen algoritmaların çok hızlı olduklarını ve yaygın olarak kullanılan bir ticari yazılımı bu açıdan geride bıraktıklarını söyleyebiliriz. Ayrıca bu tezde çatışma kısıtlarının yapısal özellikleri ve bunların çözüm uzayı üzerindeki etkileri kapsamlı biçimde çözümlenmektedir. Bulgular karmaşık kısıtlamalar altında eniyilemenin önemli olduğu telekomünikasyon, ulaştırma ve enerji dağıtım ağları gibi alanlarda geniş kapsamlı uygulama olanakları sunmaktadır. Geliştirilen yöntemler ve elde edilen bulgular hem kuramsal çalışmalarda hem de uygulamalarda karşılaşılan zorluklara yanıt vererek çatışma kısıtlı enküçük kapsar ağaç problemleri için sağlam bir temel oluşturmaktadır. Önerilen yöntemler, var olan çözüm yaklaşımlarını aşmakla kalmayıp, bilinen en iyi çözümleri iyileştirerek ayırıcı koşullar altında eniyileme ve ağ tasarımı yapmak için gelecekteki ilerlemelere de zemin hazırlamaktadır.