An optimal time algorithm for minimum linear arrangement of chord graphs

摘要

A linear arrangement φ of an undirected graph G = (V, E) with |V| = n nodes is a bijective function φ:V → {0, ..., n - 1}. The cost function is cost(G,φ)=∑_(uv∈E)|(φ(u)-φ(v))| and opt(G) = min_(?φ)cost(G, φ). 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.