Tek kaynaktan çıkan maksimum sayıdaki tepe ayrık yolların bulunması probleminin sayımlama tekniği ile etkin çözümü

Murat Erşen Berberler, Zeynep Nihan Berberler
1.712 678

Öz


Tepe ve ayrıt olmak üzere iki türe ayrılan ayrık yolların bulunması problemi ile gerçek zamanlı iletişim, çok geniş
ölçekli tümleşim, çizelgeleme, bidon paketleme ve yük dengeleme gibi birçok yöneylem araştırması probleminde alt
problem olarak karşılaşılmaktadır. Bu çalışmada uygulama alanlarının bolluğu nedeniyle çok önemli bir yere sahip
olan tepe ayrık yolların bulunması probleminin NP_tam karmaşıklık sınıfına ait eniyileme (optimizasyon) versiyonu
ele alınacaktır. Ait olduğu problem sınıfının zorluğundan dolayı sezgisel algoritmalar ile yaklaşık çözümler üretilerek
üstesinden gelinmeye çalışılan bu probleme tam ve etkin bir çözüm getirebilmek için sayımlama tekniğine dayanan
bir algoritma önerilecek ve yöntemin ayrıntılı analizi yapılacaktır.


Anahtar kelimeler


tepe ayrık yollar, maksimum bağımsız küme, sayımlama tekniği

Tam metin:

PDF


DOI: http://dx.doi.org/10.16984/saufenbilder.37306

Referanslar


Xie, Z., Chen, Z., Leng, H., Zhang, J., “Finding Arc and Vertex-Disjoint Paths in Networks“, 2009 Eighth IEEE International Conference on Dependable, Autonomic and Secure Computing, Chengdu, China, 539-544, December 12-14, 2009.

Kocay, W., Kreher, D.L., Graphs, Algorithms, and Optimization, Chapman&Hall/CRC, Florida, A.B.D., 2005.

Karp R., Complexity of Computer Computations, Plenum Press, New York, A.B.D., 1972.

Dahshan, M.H., “Maximum-Bandwidth Node-Disjoint Paths”, (IJACSA) International Journal of Advanced Computer Science and Applications, Vol. 3, No. 3, 48-56, 2012.

Lipták, L., Cheng, E., Kim, J.S., Kim, S.W., "One-to-many node-disjoint paths of hyper-star networks", Discrete Applied Mathematics, Vol. 16, Issue: 13-14, 2006-2014, SEP 2012.

Lai, C.N., “Optimal Construction of All Shortest Node-Disjoint Paths in Hypercubes with Applications”, IEEE Transactions on Parallel and Distributed Systems, Vol. 23, No. 6, 1129-1134, June 2012.

Xiang, Y., Stewart, I.A., “One-to-many node-disjoint paths in (n,k)-star graphs”, Discrete Applied Mathematics, Vol. 158, Issue 1, Volume 158, Issue 1, 6 January 2010, 62–70, January 2010.

Kaneko, K., Suzuki, Y., “Node-to-Set Disjoint Paths Problem in Pancake Graphs”, IEICE TRANSACTIONS on Information and Systems, Vol. E-86D, No. 9, 1628-1633, September 2003.

Bondy, J.A., Murty, U.S.R., Graph Theory with Applications, Elsevier Science, North Holland, 1982.

Nasibov, E., Berberler, M.E., Atılgan, C., “An Efficient Algorithm for Exact Solution of Maximum Independent Set Problem in Dense Graphs”, 3rd International Symposium on Computing in Science and Engineering, Kuşadası, Aydın, 24 October 2013.






Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 License.

Sakarya Üniversitesi Fen Bilimleri Enstitüsü Dergisi (SAÜFenBilDer), ISSN: 1301-4048 e-ISSN: 2147-835X