본문 바로가기
  • Home

Optimal Solution Algorithms for Delivery Problem on Trees

  • Journal of The Korea Society of Computer and Information
  • Abbr : JKSCI
  • 2014, 19(2), pp.143-150
  • Publisher : The Korean Society Of Computer And Information
  • Research Area : Engineering > Computer Science

Lee Kwang Eui 1

1동의대학교

Accredited

ABSTRACT

In this paper, we propose the delivery problem on trees and two algorithms for the problem. Thedelivery problem on trees is that of minimizing the object delivery time from one node to anothernode using n various speed robots. Our first algorithm generates an optimal solution with somerestrictions in handover places. In this algorithm, we assume that the handover can be made at avertex of given tree. We try to find the handover places and the robots participate in handoverfrom the start node to the destination node. The second algorithm extends the first one to removethe restriction about the handover places. The second algorithm still generates an optimal solution. The time complexities of both algorithms are O((n+m)²) where n is the number of robots and m isthe number of nodes.

Citation status

* References for papers published after 2022 are currently being built.