Solving the longest path problem in directed acyclic graphs based on amoeba algorithm

Qing Wang, Xiaoge Zhang, Sankaran Mahadevan, Yong Deng

Research output: Journal article publicationJournal articleAcademic researchpeer-review

4 Citations (Scopus)

Abstract

The longest path problem (LPP) is to find a simple path with maximum length in a given graph, which plays an important role in many real-world applications, such as job shop scheduling problem, route planning. LPP in directed acyclic graphs (DAG) has important applications, such as finding the critical path in scheduling problems. In this paper, we present an amoeba algorithm, inspired by the plasmodium of Physarum polycephalum, to solve the longest path problem in the DAG. The proposed method is composed of two parts: (1) a fictional rule is constructed to replace ohm’s law. Based on this mechanism, the current tends to pass through the conductor with more resistance. (2) The original amoeba model is adjusted to work in a special circuit based on our fictional rule. As a topological sorting is necessary in model calculations, it can only deal with LPP in DAG. In addition, the evolving processes of the proposed model have been introduced in detail in this paper. A numerical example is used to show the efficiency of the proposed method.

Original languageEnglish
Pages (from-to)147-163
Number of pages17
JournalInternational Journal of Unconventional Computing
Volume11
Issue number2
Publication statusPublished - 2015
Externally publishedYes

Keywords

  • Directed acyclic graphs
  • Longest path problem
  • Optimization
  • Physarum polycephalum

ASJC Scopus subject areas

  • Computer Science(all)

Cite this