Skip to Main content Skip to Navigation
Conference papers

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.
Document type :
Conference papers
Complete list of metadata

Cited literature [22 references]  Display  Hide  Download

https://hal.inria.fr/inria-00115249
Contributor : Gregory Kucherov <>
Submitted on : Monday, November 20, 2006 - 5:15:34 PM
Last modification on : Wednesday, December 9, 2020 - 6:02:06 PM
Long-term archiving on: : Tuesday, April 6, 2010 - 7:45:46 PM

File

CohenEtAlMFCS06.pdf
Publisher files allowed on an open archive

Identifiers

Collections

Citation

Johanne Cohen, Fedor V. Fomin, Pinar Heggernes, Dieter Kratsch, Gregory Kucherov. Optimal Linear Arrangement of Interval Graphs. 31st International Symposium on Mathematical Foundations of Computer Science - MFCS 2006, Aug 2006, Stara Lesna/Slovakia, pp.267-279, ⟨10.1007/11821069⟩. ⟨inria-00115249⟩

Share

Metrics

Record views

390

Files downloads

560