Journal
INFORMATION PROCESSING LETTERS
Volume 87, Issue 2, Pages 59-66Publisher
ELSEVIER SCIENCE BV
DOI: 10.1016/S0020-0190(03)00261-8
Keywords
algorithms; optimal embedding; one-page embedding; anchored tree
Categories
Ask authors/readers for more resources
In the minimum linear arrangement problem one wishes to assign distinct integers to the vertices of a given graph so that the sum of the differences (in absolute value) across the edges of the graph is minimized. This problem is known to be NP-complete for the class of all graphs, but polynomial for trees-algorithms of time complexity O(n(2.2)) and O(n(1.6)) were given by Shiloach [SIAM J. Comput. 8 (1979) 15-32] and Chung [Comput. Math. Appl. 10 (1984) 43-60], respectively. We present a linear-time algorithm for finding the optimal embedding (arrangement) in a restricted but important class of embeddings called one-page embeddings. (C) 2003 Elsevier Science B.V. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available