Maximum Linear Arrangement: exact algorithms for specific classes of graphs and approximation algorithms for wide classes of graphs

Lluís Alemany-Puig, Juan Luis Esteban, Ramon Ferrer-i-Cancho

Linear arrangements of graphs are a well-known type of graph labeling and are found in many important computational problems. A linear arrangement is usually defined as a permutati…