An Efficient A* Algorithm for the Directed Linear Arrangement Problem

NHUIR > College of Science and Technology > Department of Computer Science and Information Engineering > Periodical Articles > Item 987654321/27350

Please use this identifier to cite or link to this item: http://nhuir.nhu.edu.tw/handle/987654321/27350

Title:	An Efficient A* Algorithm for the Directed Linear Arrangement Problem
Authors:	張介耀;Chang, Chieh-yao
Contributors:	資訊工程學系
Keywords:	Directed Linear Arrangement;Directed Clustering;A* Search
Date:	2008-12
Issue Date:	2019-11-20 10:57:01 (UTC+8)
Abstract:	In this paper we present an efficient A* algorithm to solve the Directed Linear Arrangement Problem. By using a branch and bound technique to embed a given directed acyclic graph into a layerwise partition search graph, the optimal directed ordering is then be identified through a A* shortest path search in the embedding graph. We developed a hybrid DC+BDS algorithm to approximate the optimal linear arrangement solution, which includes directed clustering and bidirectional sort technique. Along with a lower bound based on the maximum flow technique, this approximation solution is used as an upper bound to prune the state space during the A* search. In order to reduce the memory requirement of the A* search, we also discuss a implementation of the relay node technique from Zhou and Hansen.
Relation:	WSEAS TRANSACTIONS on COMPUTERS vol. 7, no. 12 pp.1958-1967
Appears in Collections:	[Department of Computer Science and Information Engineering] Periodical Articles

Files in This Item:

File	Description	Size	Format
An Efficient A.pdf		472Kb	Adobe PDF	395	View/Open