Optimal Linear Arrangement of Interval Graphs

Abstract : We study the optimal linear arrangement (OLA) problem on interval graphs. Several linear layout problems that are NP-hard on general graphs are solvable in polynomial time on interval graphs.We prove that, quite surprisingly, optimal linear arrangement of interval graphs is NP-hard. The same result holds for permutation graphs. We present a lower bound and a simple and fast 2-approximation algorithm based on any interval model of the input graph.
Type de document :
Communication dans un congrès
Rastislav Kralovic and Pawel Urzyczyn. 31st International Symposium on Mathematical Foundations of Computer Science - MFCS 2006, Aug 2006, Stara Lesna/Slovakia, Springer Verlag, 4162, pp.267-279, 2006, Lectures Notes in Computer Science. 〈10.1007/11821069〉
Liste complète des métadonnées

Littérature citée [22 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00115249
Contributeur : Gregory Kucherov <>
Soumis le : lundi 20 novembre 2006 - 17:15:34
Dernière modification le : mardi 24 avril 2018 - 13:35:22
Document(s) archivé(s) le : mardi 6 avril 2010 - 19:45:46

Fichier

CohenEtAlMFCS06.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

Collections

Citation

Johanne Cohen, Fedor Fomin, Pinar Heggernes, Dieter Kratsch, Gregory Kucherov. Optimal Linear Arrangement of Interval Graphs. Rastislav Kralovic and Pawel Urzyczyn. 31st International Symposium on Mathematical Foundations of Computer Science - MFCS 2006, Aug 2006, Stara Lesna/Slovakia, Springer Verlag, 4162, pp.267-279, 2006, Lectures Notes in Computer Science. 〈10.1007/11821069〉. 〈inria-00115249〉

Partager

Métriques

Consultations de la notice

291

Téléchargements de fichiers

258