Minimum linear arrangement of Chord graphs

摘要

The minimum linear arrangement (MINLA) is a NP-hard problem in general. But there are some classes of graphs optimally solvable in polynomial time. In this paper, we solve the minimum linear arrangement problem for a new class of graphs (Chord graphs) in polynomial time. Also, we present a closed formula for the cost of optimal arrangement. Our motivation to solve the problem for this class of graphs is its application in optimization of peer-to-peer overlay networks.