Araştırma Makalesi
BibTex RIS Kaynak Göster

Finding an efficient solution for the maximum number of single source node disjoint paths by enumeration

Yıl 2015, Cilt: 19 Sayı: 2, 213 - 219, 09.08.2015
https://doi.org/10.16984/saufenbilder.37306

Öz

The problem of finding node or edge disjoint paths is encountered as a sub problem in many operations research problems such as real time communication, very large scale integration, scheduling, bin packing and load balancing etc. In this paper, due to the majority of application fields, the optimization version for the problem of finding node disjoint paths related to NP_complete class is handled. An algorithm is proposed based on enumeration technique in order to find an exact and efficient solution for the problem of finding maximum number of single source node disjoint paths that is recently tried to overcome by generating approximate solutions by heuristic algorithms due to the complexity class that it belongs to and the method is analyzed in detail.

Kaynakça

  • 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.

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

Yıl 2015, Cilt: 19 Sayı: 2, 213 - 219, 09.08.2015
https://doi.org/10.16984/saufenbilder.37306

Ö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.


Kaynakça

  • 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.
Toplam 10 adet kaynakça vardır.

Ayrıntılar

Birincil Dil Türkçe
Konular Mühendislik
Bölüm Araştırma Makalesi
Yazarlar

Murat Berberler

Zeynep Berberler

Yayımlanma Tarihi 9 Ağustos 2015
Gönderilme Tarihi 22 Temmuz 2014
Kabul Tarihi 26 Mart 2015
Yayımlandığı Sayı Yıl 2015 Cilt: 19 Sayı: 2

Kaynak Göster

APA Berberler, M., & Berberler, Z. (2015). Tek kaynaktan çıkan maksimum sayıdaki tepe ayrık yolların bulunması probleminin sayımlama tekniği ile etkin çözümü. Sakarya University Journal of Science, 19(2), 213-219. https://doi.org/10.16984/saufenbilder.37306
AMA Berberler M, Berberler Z. Tek kaynaktan çıkan maksimum sayıdaki tepe ayrık yolların bulunması probleminin sayımlama tekniği ile etkin çözümü. SAUJS. Temmuz 2015;19(2):213-219. doi:10.16984/saufenbilder.37306
Chicago Berberler, Murat, ve Zeynep Berberler. “Tek Kaynaktan çıkan Maksimum sayıdaki Tepe ayrık yolların Bulunması Probleminin sayımlama tekniği Ile Etkin çözümü”. Sakarya University Journal of Science 19, sy. 2 (Temmuz 2015): 213-19. https://doi.org/10.16984/saufenbilder.37306.
EndNote Berberler M, Berberler Z (01 Temmuz 2015) Tek kaynaktan çıkan maksimum sayıdaki tepe ayrık yolların bulunması probleminin sayımlama tekniği ile etkin çözümü. Sakarya University Journal of Science 19 2 213–219.
IEEE M. Berberler ve Z. Berberler, “Tek kaynaktan çıkan maksimum sayıdaki tepe ayrık yolların bulunması probleminin sayımlama tekniği ile etkin çözümü”, SAUJS, c. 19, sy. 2, ss. 213–219, 2015, doi: 10.16984/saufenbilder.37306.
ISNAD Berberler, Murat - Berberler, Zeynep. “Tek Kaynaktan çıkan Maksimum sayıdaki Tepe ayrık yolların Bulunması Probleminin sayımlama tekniği Ile Etkin çözümü”. Sakarya University Journal of Science 19/2 (Temmuz 2015), 213-219. https://doi.org/10.16984/saufenbilder.37306.
JAMA Berberler M, Berberler Z. Tek kaynaktan çıkan maksimum sayıdaki tepe ayrık yolların bulunması probleminin sayımlama tekniği ile etkin çözümü. SAUJS. 2015;19:213–219.
MLA Berberler, Murat ve Zeynep Berberler. “Tek Kaynaktan çıkan Maksimum sayıdaki Tepe ayrık yolların Bulunması Probleminin sayımlama tekniği Ile Etkin çözümü”. Sakarya University Journal of Science, c. 19, sy. 2, 2015, ss. 213-9, doi:10.16984/saufenbilder.37306.
Vancouver Berberler M, Berberler Z. Tek kaynaktan çıkan maksimum sayıdaki tepe ayrık yolların bulunması probleminin sayımlama tekniği ile etkin çözümü. SAUJS. 2015;19(2):213-9.

30930 This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.