Ağaç Türü Çizgelerde Maksimal Eşleme Politopu

Date

2015-09-09

Author

Tural, Mustafa Kemal

Metadata

Show full item record

Item Usage Stats

184
views

0
downloads

Verilen ağırlıklı bir çizge için, minimum ağırlıklı maksimal eşleme (MAME) problemi, çizgede en az ağırlığa sahip bir maksimal eşleme bulma problemidir. MAME problemi genel olarak NP-hard bir problem olmasına rağmen özel bazı çizge sınıflarında polinom zamanda çözülebilmektedir. Örneğin, ağaç türü çizgelerde bütün kenar ağırlıkların bir olduğu durumda MAME probleminin lineer zamanda çözülebildiği gösterilmiştir. Bu çalışmada, ağaç türü çizgeler için maksimal eşlemelerin insidans vektörlerinin konveks örtüsünün (yani maksimal eşleme politopunun)yakın zamanda önerilen bir tam sayılı programlama formülasyonunun doğrusal programlama gevşetmesi tarafından tanımlanan politopa eşit olduğu minimum karşı örnek yaklaşımı kullanılarak gösterilmiştir. Bunun sonucu olarak MAME probleminin ağaç türü çizgelerde kenar ağırlıkların farklı olduğu durumlarda da polinom zamanda çözülebildiği ortaya konulmuştur.

Subject Keywords

Çizge teorisi, Tam sayılı programlama, Eşleme, Doğrusal programlama

URI

https://hdl.handle.net/11511/71788
https://doczz.biz.tr/doc/83747/1-9-eyl%C3%BCl-%C3%A7ar%C5%9Famba-oturumlar%C4%B1

Conference Name

35. Yöneylem Araştırması ve Endüstri Mühendisliği (YAEM) Ulusal Kongresi (09 - 11 September 2015 )

Collections

Department of Industrial Engineering, Conference / Seminar

Suggestions

OpenMETU
Core

Exact solution approaches for the directed bi-objective chinese postman problem Eroglu, Ezgi; Azizoğlu, Meral (2018-06-01) In this study, we consider a directed bi-objective Chinese Postman Problem with two additive objectives (like total cost and total distance) and propose two solution approaches to generate all non-dominated objective vectors. The first approach, namely classical approach, uses the optimal solutions of the mixed integer linear programs and generates the non-dominated objective vectors’ set sequentially. The second approach, namely branch and bound algorithm takes its spirit from the optimal solutions of the ...
Minimum Ağırlıklı Maksimum Eşleme Problemi İçin Polihedral Yaklaşımlar Tural, Mustafa Kemal(2016-12-31) Bizim bu çalışmada ele alacağımız problem NP-hard kategorisinde bulunan Minimum Ağırlıklı Maksimal Eşleme (MAME) problemidir. Çalışmamızda, MAME problemlerini çözmek için kullanılan bilinen bir tam sayılı programlama formülasyonunu ele alıp daha da geliştirmeyi planlıyoruz. Formülasyonu şu ana kadar çözülebilenlerden daha büyük boyutlu problemleri çözebilecek şekilde güçlendirmeyi amaçlıyoruz. Problem için güçlü geçerli eşitsizlikler (strong valid inequalities) bularak bunların formülasyona eklenmesi ile çö...
Investigation of variations in performance properties of asphalt concrete using image-based finite element model Karakaya, Yalçın; Güler, Murat; Department of Civil Engineering (2022-7-20) The objective of this study is to evaluate variations in performance properties of asphalt concrete using a two-dimensional image-based finite element model. Two different asphalt mixtures are used in both laboratory tests and in FEM analyses representing different conditions. A flatbed scanner is then used to capture cross-sectional images of the samples and various image processing techniques are applied to prepare the images for FEM. A unique image vectorization method has been developed to transform cro...
Parallel production lines with sequence-dependent setup times and side constraints Sargut, Zeynep; Azizoğlu, Meral (TMMOB Makina Mühendisleri Odası, 2017-01-01)
Terapi İlişkisinin Terapist ve Danışanın Kaçınma Örüntüleri Açısından İncelenmesi: Bir Konuşma Analizi Çalışması Sarı, Sevda (Orta Doğu Teknik Üniversitesi (Ankara, Turkey), 2019-6-20) Nitel araştırma yöntemlerinin kullanıldığı psikoterapi araştırmaları ile terapi ilişkisi, duygular terapide değişim süreci ve terapist danışan etkileşimi gibi konularda psikoterapide süreç araştırmaları yapılabilmektedir (McLeod, 2001). Konuşma analizi, dilin etkileşimsel dinamiğine odaklandığı için terapi ilişkisinin araştırılmasında tercih edilmektedir (Perakyla, 2004). Bu çalışmanın amacı, bir psikoterapi süreç araştırması olarak, kaçınmanın terapist ve danışan etkileşim sürecinde nasıl ortaya çıktığının...

Citation Formats

M. K. Tural, “Ağaç Türü Çizgelerde Maksimal Eşleme Politopu,” Ankara, Türkiye, 2015, p. 225, Accessed: 00, 2021. [Online]. Available: https://hdl.handle.net/11511/71788.