A New approach in the maximum flow problem
Başlık çevirisi mevcut değil.
- Tez No: 6558
- Danışmanlar: PROF. DR. MUSTAFA AKGÜL
- Tez Türü: Yüksek Lisans
- Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 1989
- Dil: İngilizce
- Üniversite: İhsan Doğramacı Bilkent Üniversitesi
- Enstitü: Mühendislik ve Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Belirtilmemiş.
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 56
Özet
ÖZET MAKSİMUM AKIŞ PROBLEMİNE YEN± B±R YAKLAŞIM Ayşen Eren Endüstri Mühendisliği Bölümü Yüksek Lisans Tez Yöneticisi: Doç. Mustafa Akgül Temmuz, 1989 Bu çalışmada, maksimum akış problemine değişik bir görüş noktasından yaklaşmayı denedik. Bu uğraş, bizi yeni bir maksimum akış algoritmasını geliştirmeye götürdü. Algoritma, serimin her ayrıtındaki ilk akışımsının, ayrıtın üst kapasitesine eşitlendiği zaman, bunun kapasite ile eksi olmama kısıtlarını sağlarken, düğüm denge eşitliklerini bozması fikrini temel alır. Olurlu ve en iyi bir akış elde etmek için, bazı ayrıtlar üzerindeki akışımsılar azaltılmalıdır. Verilen bir ilk akışımsıya göre, artı ve eksi fazlalık ile dengelenmiş düğümler belirlenir. Algoritma, artı fazlalık düğümlerini eksi fazlalık düğümlerine bağlayan artık yollarını bulup, bu yollar boyunca fazlalıkları göndererek, dengelenmemiş olan düğümlerin fazlalıklarını sıfıra indirir. îlk önce, en küçük kesit belirlenir ve sonra verilen kesitin maksimum akışı bulunur. Algoritmanın zamansal karmaşıklığı 0(n2m)'dir. Sleator ile Tarjan'ın Dinamik Ağaç yapısının değiştirilmiş şeklinin uygulanması bunu 0(nm logn)'e düşürür. iv
Özet (Çeviri)
ABSTRACT A NEW APPROACH IN THE MAXIMUM FLOW PROBLEM AYSEN EREN M.S. in Industrial Engineering Supervisor: Assoc. Prof. Mustafa Akgul July, 1989 In this study, we tried to approach the maximum flow problem from a different point of view. This effort has led us to the development of a new maximum flow algorithm. The algorithm is based on the idea that when initial quasi-flow on each edge of the graph is equated to the upper capacity of the edge, it violates node balance equations, while satisfying capacity and non-negativity constraints. In order to obtain a feasible and optimum flow, quasi-flow on some of the edges have to be reduced. Given an initial quasi-flow, positive and negative excess, and, balanced nodes are determined. Algorithm reduces excesses of unbalanced nodes to zero by finding residual paths joining positive excess nodes to negative excess nodes and sending excesses along these paths. Minimum cut is determined first, and then maximum flow of the given cut is found. Time complexity of the algorithm is o(n m). The application of the modified version of the Dynamic Tree structure of Sleator and Tarjan reduces it to o(nmlogn). iii
Benzer Tezler
- Bisiklet öncelikli kavşak işletiminde yeni bir yaklaşım
A new approach for operation of intersections with presedence of bicycle
CİHAT KALYONCUOĞLU
Doktora
Türkçe
2017
Ulaşımİstanbul Teknik Üniversitesiİnşaat Mühendisliği Ana Bilim Dalı
DOÇ. DR. MURAT ERGÜN
- Sıralı akış çizelgeleme problemlerinin arı algoritmasıyla çözümü
Ordered flowshop schedule problems solving by bee algorithm
MUHAMMED PARLAK
Yüksek Lisans
Türkçe
2012
Endüstri ve Endüstri MühendisliğiYıldız Teknik ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ. DR. ALİ FUAT GÜNERİ
- Biyokütlenin piroliz reaktivitesinin farklı yöntemler kullanılarak incelenmesi
Determination of biomass pyrolysis reactivity by using different methods
MERVE ÖZFİDAN
Yüksek Lisans
Türkçe
2019
Kimya Mühendisliğiİstanbul Teknik ÜniversitesiKimya Mühendisliği Ana Bilim Dalı
PROF. DR. HANZADE AÇMA
- Çoklu kavşaklar için ayarlanabilir ve ağırlık tabanlı adaptif trafik sinyal kontrolü
Adjustable and weight-based adaptive traffic signal control for multiple intersections
ZÜLAL HİLAL YILDIZ BUDAK
Yüksek Lisans
Türkçe
2024
Elektrik ve Elektronik MühendisliğiKonya Teknik ÜniversitesiElektrik ve Elektronik Mühendisliği Ana Bilim Dalı
DOÇ. DR. AKİF DURDU
DR. ÖĞR. ÜYESİ SEYİT ALPEREN ÇELTEK
- Dağıtım şebekelerinin PSO kullanılarak yeniden yapılandırılması
Reconstruction of distribution networks using PSO
ASLI ÇAKIR
Yüksek Lisans
Türkçe
2019
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiElektrik Mühendisliği Ana Bilim Dalı
DR. ÖĞR. ÜYESİ HATİCE LALE ZEYNELGİL