Article ID Journal Published Year Pages File Type
4633399 Applied Mathematics and Computation 2008 10 Pages PDF
Abstract

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.

Related Topics
Physical Sciences and Engineering Mathematics Applied Mathematics
Authors
, ,