An optimal time algorithm for minimum linear arrangement of chord graphs

作者：Raoufi Pariya; Rostami Habib^*; Bagherinezhad Hessam

来源：Information Sciences, 2013, 238: 212-220.

DOI：10.1016/j.ins.2013.02.037

• Minimum linear arrangement
• Graph layout
• Labeling
• Chord graph

A linear arrangement phi of an undirected graph G = (V,E) with vertical bar V vertical bar = n nodes is a bijective function phi:V -%26gt; {0, ... , n - 1}. The cost function is cost(G, phi) = Sigma(uv is an element of E)vertical bar(phi(u) - phi(v))vertical bar and opt(G) = min(for all phi)cost(G,phi). The problem of finding opt(G) is called minimum linear arrangement (MINLA). The Minimum Linear Arrangement is an NP-hard problem in general. But there are some classes of graphs optimally solvable in polynomial time. In this paper, we show that the label of each node equals to the reverse of binary representation of its id in the optimal arrangement. Then, we design an O(n) algorithm to solve the minimum linear arrangement problem of Chord graphs.

• 出版日期2013-7-20