Geri Dön

A New approach in the maximum flow problem

Başlık çevirisi mevcut değil.

  1. Tez No: 6558
  2. Yazar: AYŞEN EREN
  3. Danışmanlar: PROF. DR. MUSTAFA AKGÜL
  4. Tez Türü: Yüksek Lisans
  5. Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 1989
  8. Dil: İngilizce
  9. Üniversite: İhsan Doğramacı Bilkent Üniversitesi
  10. Enstitü: Mühendislik ve Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Belirtilmemiş.
  12. Bilim Dalı: Belirtilmemiş.
  13. Sayfa Sayısı: Belirtilmemiş.

Ö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

  1. Tez No

    718296

    A policy analysis and recommendation for combating against the VAT fraud problem in Turkey

    Başlık çevirisi yok

    ERTAN GÜVENDİ

    Yüksek Lisans

    İngilizce

    İngilizce

    2019

    EkonomiDuke Unıversıty

    PROF. GANGADHAR PRASAD SHUKLA

    DOÇ. DR. SANDEEP BHATTACHARYA

  2. Tez No

    55870

    Zeolit-su ikilisini kullanan adsorpsiyon ısı pompalarında ısıve kütle iletimini geliştirmek için yeni bir yaklaşım

    A new approach to enhance heat and mass transfer in adsorption heat pumps

    MELKON TATLIER

    Yüksek Lisans

    Türkçe

    Türkçe

    1996

    Kimya Mühendisliğiİstanbul Teknik Üniversitesi

    Kimya Mühendisliği Ana Bilim Dalı

    PROF.DR. AYŞE ERDEM ŞENATALAR

  3. Tez No

    66856

    Esnek imalat istemlerinde hücre oluşturma problemine 0-1 tamsayılı programlama ile modelleme yaklaşımı

    Modeling approach with 0-1 integer programming for cell formation in flexible manufacturing systems

    SÜLEYMAN ERTAN TANSÖKER

    Yüksek Lisans

    Türkçe

    Türkçe

    1997

    İşletmeİstanbul Teknik Üniversitesi

    İşletme Mühendisliği Ana Bilim Dalı

    DOÇ. DR. SEMRA DURMUŞOĞLU

  4. Tez No

    2210

    Grup teknolojisi imalat sistemi ve bu sistemin tasarımına yönelik yeni bir metot

    Group technology manufacturing systems and a new method oriented to the design of these systems

    M. BÜLENT DURMUŞOĞLU

    Doktora

    Türkçe

    Türkçe

    1986

    Endüstri ve Endüstri Mühendisliğiİstanbul Teknik Üniversitesi

    DOÇ. DR. GÖNÜL ÖZKAYA

  5. Tez No

    637742

    Developing of a groundwater flow model for the area between Terkos lake and Canal Istanbul using GIS, remote sensing and numeric groundwater modelling

    Terkos gölü ile Kanal İstanbul arasındaki bölge için CBS, uzaktan algılama ve sayısal yöntemlerle yeraltı suyu akış modelinin geliştirilmesi

    KHANSAA ABDULELAH AHMED AHMED

    Doktora

    İngilizce

    İngilizce

    2020

    İnşaat Mühendisliğiİstanbul Teknik Üniversitesi

    İnşaat Mühendisliği Ana Bilim Dalı

    PROF. DR. ABDÜSSELAM ALTUNKAYNAK

Geri Dön