Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4633399 | Applied Mathematics and Computation | 2008 | 10 Pages |
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.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Applied Mathematics
Authors
Habib Rostami, Jafar Habibi,