The following information was submitted:
Transactions: WSEAS TRANSACTIONS ON COMPUTERS
Transactions ID Number: 28-651
Full Name: Guang-Ming Wu
Position: Professor
Age: ON
Sex: Male
Address: 32 Chung Keng Li, Dalin, Chiayi
Country: TAIWAN
Tel: 886-5-2427130
Tel prefix: 886
Fax: 886-5-2427131
E-mail address: gmwu@mail.nhu.edu.tw
Other E-mails:
Title of the Paper: An Efficient A* Algorithm for the Directed Linear Arrangement Problem
Authors as they appear in the Paper: Derchian Tsaih, Guang-ming Wu, Chiehyao Chang, Shaoshin Hung, Chinshan Wu, Huiling Lin
Email addresses of all the authors: dtsaih@mail.nhu.edu.tw, gmwu@mail.nhu.edu.tw, cychangs@mail.nhu.edu.tw, hss@cs.ccu.edu.tw, jackwu@mail.wfc.edu.tw, ljoyce@mail.ltu.edu.tw
Number of paper pages: 10
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 [22].
Keywords: Directed Linear Arrangement, Directed Clustering, A* Search
EXTENSION of the file: .pdf
Special (Invited) Session: using A* Algorithm for Directed Linear Arrangement Problem
Organizer of the Session: 593670
How Did you learn about congress:
IP ADDRESS: 203.72.1.8
