The Minimum Linear Arrangement Problem
Description:
The MINLA problem is a classified NP-hard optimization problem. It can be defined as:
Input:
-Undirected and unweighted graph G = (V,E).
Output:
-A one to one function 
.
Question
In the MINLA problem, the goal is to arrange the vertices
of a given graph on an integer line ( 
-label
assignment) , so as to minimize the following cost formuma C:
Problem Instances
In order to define an instance of this problem we need to provide all the information about the Graph. This means: his Vertex Set and the associated Edge Set between pairs of vertexs. The edges are unweighted.
Related Bibliography and Papers
|
TextBook
|
Computers and Intractability: A Guide to the Theory of Np-Completeness by Michael R. Garey, David S. Johnson |
|
TextBook
|
How to Solve It: Modern Heuristics by Zbigniew Michalewicz, David B. Fogel |
| URL |
Aproximation Heuristics and Benchmarkings for the MinLA
Problem |
|
URL
|
A compendium of NP optimization problems http://www.nada.kth.se/~viggo/problemlist/compendium.html |
Last Updated:
5/06/03
For
any question or suggestion, click here
to contact with us.