Optimal Linear Arrangement of Interval Graphs
Identifieur interne : 003953 ( Hal/Corpus ); précédent : 003952; suivant : 003954Optimal Linear Arrangement of Interval Graphs
Auteurs : Johanne Cohen ; Fedor Fomin ; Pinar Heggernes ; Dieter Kratsch ; Gregory KucherovSource :
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.
Url:
DOI: 10.1007/11821069
Links to Exploration step
Hal:inria-00115249Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en">Optimal Linear Arrangement of Interval Graphs</title>
<author><name sortKey="Cohen, Johanne" sort="Cohen, Johanne" uniqKey="Cohen J" first="Johanne" last="Cohen">Johanne Cohen</name>
<affiliation><hal:affiliation type="laboratory" xml:id="struct-160" status="OLD"><orgName>Laboratoire Lorrain de Recherche en Informatique et ses Applications</orgName>
<orgName type="acronym">LORIA</orgName>
<desc><address><addrLine>Campus Scientifique BP 239 54506 Vandoeuvre-lès-Nancy Cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.loria.fr</ref>
</desc>
<listRelation><relation name="UMR7503" active="#struct-441569" type="direct"></relation>
<relation active="#struct-300009" type="direct"></relation>
<relation active="#struct-300291" type="direct"></relation>
<relation active="#struct-300292" type="direct"></relation>
<relation active="#struct-300293" type="direct"></relation>
</listRelation>
<tutelles><tutelle name="UMR7503" active="#struct-441569" type="direct"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno>
<idno type="IdRef">02636817X</idno>
<orgName>Centre National de la Recherche Scientifique</orgName>
<orgName type="acronym">CNRS</orgName>
<date type="start">1939-10-19</date>
<desc><address><country key="FR"></country>
</address>
<ref type="url">http://www.cnrs.fr/</ref>
</desc>
</org>
</tutelle>
<tutelle active="#struct-300009" type="direct"><org type="institution" xml:id="struct-300009" status="VALID"><orgName>Institut National de Recherche en Informatique et en Automatique</orgName>
<orgName type="acronym">Inria</orgName>
<desc><address><addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/en/</ref>
</desc>
</org>
</tutelle>
<tutelle active="#struct-300291" type="direct"><org type="institution" xml:id="struct-300291" status="OLD"><orgName>Université Henri Poincaré - Nancy 1</orgName>
<orgName type="acronym">UHP</orgName>
<date type="end">2011-12-31</date>
<desc><address><addrLine>24-30 rue Lionnois, BP 60120, 54 003 NANCY cedex, France</addrLine>
<country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
<tutelle active="#struct-300292" type="direct"><org type="institution" xml:id="struct-300292" status="OLD"><orgName>Université Nancy 2</orgName>
<date type="end">2011-12-31</date>
<desc><address><addrLine>91 avenue de la Libération, BP 454, 54001 Nancy cedex</addrLine>
<country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
<tutelle active="#struct-300293" type="direct"><org type="institution" xml:id="struct-300293" status="OLD"><orgName>Institut National Polytechnique de Lorraine</orgName>
<orgName type="acronym">INPL</orgName>
<date type="end">2011-12-31</date>
<desc><address><country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
</affiliation>
</author>
<author><name sortKey="Fomin, Fedor" sort="Fomin, Fedor" uniqKey="Fomin F" first="Fedor" last="Fomin">Fedor Fomin</name>
<affiliation><hal:affiliation type="laboratory" xml:id="struct-20502" status="VALID"><orgName>Department of Informatics</orgName>
<desc><address><addrLine>Institutt for informatikk Universitetet i Bergen Postboks 7803 5020 Bergen</addrLine>
<country key="NO"></country>
</address>
<ref type="url">http://www.uib.no/ii</ref>
</desc>
<listRelation><relation active="#struct-300728" type="direct"></relation>
</listRelation>
<tutelles><tutelle active="#struct-300728" type="direct"><org type="institution" xml:id="struct-300728" status="VALID"><orgName>University of Bergen</orgName>
<desc><address><country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
</affiliation>
</author>
<author><name sortKey="Heggernes, Pinar" sort="Heggernes, Pinar" uniqKey="Heggernes P" first="Pinar" last="Heggernes">Pinar Heggernes</name>
<affiliation><hal:affiliation type="laboratory" xml:id="struct-20502" status="VALID"><orgName>Department of Informatics</orgName>
<desc><address><addrLine>Institutt for informatikk Universitetet i Bergen Postboks 7803 5020 Bergen</addrLine>
<country key="NO"></country>
</address>
<ref type="url">http://www.uib.no/ii</ref>
</desc>
<listRelation><relation active="#struct-300728" type="direct"></relation>
</listRelation>
<tutelles><tutelle active="#struct-300728" type="direct"><org type="institution" xml:id="struct-300728" status="VALID"><orgName>University of Bergen</orgName>
<desc><address><country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
</affiliation>
</author>
<author><name sortKey="Kratsch, Dieter" sort="Kratsch, Dieter" uniqKey="Kratsch D" first="Dieter" last="Kratsch">Dieter Kratsch</name>
<affiliation><hal:affiliation type="laboratory" xml:id="struct-402694" status="VALID"><idno type="IdRef">109477189</idno>
<idno type="IdUnivLorraine">[UL]RSG--</idno>
<idno type="RNSR">199914410X</idno>
<orgName>Laboratoire d'Informatique Théorique et Appliquée</orgName>
<orgName type="acronym">LITA</orgName>
<date type="start">2012-01-01</date>
<desc><address><addrLine>Université de Lorraine, Ile du Saulcy, 57045 Metz Cedex 1</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.lita.univ-lorraine.fr/</ref>
</desc>
<listRelation><relation name="EA3097" active="#struct-413289" type="direct"></relation>
</listRelation>
<tutelles><tutelle name="EA3097" active="#struct-413289" type="direct"><org type="institution" xml:id="struct-413289" status="VALID"><idno type="IdRef">157040569</idno>
<idno type="IdUnivLorraine">[UL]100--</idno>
<orgName>Université de Lorraine</orgName>
<orgName type="acronym">UL</orgName>
<date type="start">2012-01-01</date>
<desc><address><addrLine>34 cours Léopold - CS 25233 - 54052 Nancy cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.univ-lorraine.fr/</ref>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
</affiliation>
</author>
<author><name sortKey="Kucherov, Gregory" sort="Kucherov, Gregory" uniqKey="Kucherov G" first="Gregory" last="Kucherov">Gregory Kucherov</name>
<affiliation><hal:affiliation type="laboratory" xml:id="struct-2546" status="VALID"><orgName>Laboratoire d'Informatique Fondamentale de Lille</orgName>
<orgName type="acronym">LIFL</orgName>
<desc><address><addrLine>Bâtiment M3 59655 Villeneuve d'Ascq Cédex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.lifl.fr/</ref>
</desc>
<listRelation><relation active="#struct-301700" type="direct"></relation>
<relation active="#struct-92973" type="direct"></relation>
<relation active="#struct-300009" type="direct"></relation>
<relation name="UMR8022" active="#struct-441569" type="direct"></relation>
</listRelation>
<tutelles><tutelle active="#struct-301700" type="direct"><org type="institution" xml:id="struct-301700" status="VALID"><idno type="IdRef">026404524</idno>
<idno type="ISNI">0000000121517701</idno>
<orgName>Université de Lille, Sciences Humaines et Sociales</orgName>
<desc><address><addrLine>Domaine universitaire du "Pont de Bois"Rue du Barreau BP 60149 59653 Villeneuve d'Ascq Cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.univ-lille3.fr/</ref>
</desc>
</org>
</tutelle>
<tutelle active="#struct-92973" type="direct"><org type="institution" xml:id="struct-92973" status="VALID"><idno type="IdRef">026404184</idno>
<orgName>Université de Lille, Sciences et Technologies</orgName>
<desc><address><addrLine>Cité Scientifique - 59655 Villeneuve d'Ascq Cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.univ-lille1.fr/</ref>
</desc>
</org>
</tutelle>
<tutelle active="#struct-300009" type="direct"><org type="institution" xml:id="struct-300009" status="VALID"><orgName>Institut National de Recherche en Informatique et en Automatique</orgName>
<orgName type="acronym">Inria</orgName>
<desc><address><addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/en/</ref>
</desc>
</org>
</tutelle>
<tutelle name="UMR8022" active="#struct-441569" type="direct"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno>
<idno type="IdRef">02636817X</idno>
<orgName>Centre National de la Recherche Scientifique</orgName>
<orgName type="acronym">CNRS</orgName>
<date type="start">1939-10-19</date>
<desc><address><country key="FR"></country>
</address>
<ref type="url">http://www.cnrs.fr/</ref>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
</affiliation>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">HAL</idno>
<idno type="RBID">Hal:inria-00115249</idno>
<idno type="halId">inria-00115249</idno>
<idno type="halUri">https://hal.inria.fr/inria-00115249</idno>
<idno type="url">https://hal.inria.fr/inria-00115249</idno>
<idno type="doi">10.1007/11821069</idno>
<date when="2006-08-28">2006-08-28</date>
<idno type="wicri:Area/Hal/Corpus">003953</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title xml:lang="en">Optimal Linear Arrangement of Interval Graphs</title>
<author><name sortKey="Cohen, Johanne" sort="Cohen, Johanne" uniqKey="Cohen J" first="Johanne" last="Cohen">Johanne Cohen</name>
<affiliation><hal:affiliation type="laboratory" xml:id="struct-160" status="OLD"><orgName>Laboratoire Lorrain de Recherche en Informatique et ses Applications</orgName>
<orgName type="acronym">LORIA</orgName>
<desc><address><addrLine>Campus Scientifique BP 239 54506 Vandoeuvre-lès-Nancy Cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.loria.fr</ref>
</desc>
<listRelation><relation name="UMR7503" active="#struct-441569" type="direct"></relation>
<relation active="#struct-300009" type="direct"></relation>
<relation active="#struct-300291" type="direct"></relation>
<relation active="#struct-300292" type="direct"></relation>
<relation active="#struct-300293" type="direct"></relation>
</listRelation>
<tutelles><tutelle name="UMR7503" active="#struct-441569" type="direct"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno>
<idno type="IdRef">02636817X</idno>
<orgName>Centre National de la Recherche Scientifique</orgName>
<orgName type="acronym">CNRS</orgName>
<date type="start">1939-10-19</date>
<desc><address><country key="FR"></country>
</address>
<ref type="url">http://www.cnrs.fr/</ref>
</desc>
</org>
</tutelle>
<tutelle active="#struct-300009" type="direct"><org type="institution" xml:id="struct-300009" status="VALID"><orgName>Institut National de Recherche en Informatique et en Automatique</orgName>
<orgName type="acronym">Inria</orgName>
<desc><address><addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/en/</ref>
</desc>
</org>
</tutelle>
<tutelle active="#struct-300291" type="direct"><org type="institution" xml:id="struct-300291" status="OLD"><orgName>Université Henri Poincaré - Nancy 1</orgName>
<orgName type="acronym">UHP</orgName>
<date type="end">2011-12-31</date>
<desc><address><addrLine>24-30 rue Lionnois, BP 60120, 54 003 NANCY cedex, France</addrLine>
<country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
<tutelle active="#struct-300292" type="direct"><org type="institution" xml:id="struct-300292" status="OLD"><orgName>Université Nancy 2</orgName>
<date type="end">2011-12-31</date>
<desc><address><addrLine>91 avenue de la Libération, BP 454, 54001 Nancy cedex</addrLine>
<country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
<tutelle active="#struct-300293" type="direct"><org type="institution" xml:id="struct-300293" status="OLD"><orgName>Institut National Polytechnique de Lorraine</orgName>
<orgName type="acronym">INPL</orgName>
<date type="end">2011-12-31</date>
<desc><address><country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
</affiliation>
</author>
<author><name sortKey="Fomin, Fedor" sort="Fomin, Fedor" uniqKey="Fomin F" first="Fedor" last="Fomin">Fedor Fomin</name>
<affiliation><hal:affiliation type="laboratory" xml:id="struct-20502" status="VALID"><orgName>Department of Informatics</orgName>
<desc><address><addrLine>Institutt for informatikk Universitetet i Bergen Postboks 7803 5020 Bergen</addrLine>
<country key="NO"></country>
</address>
<ref type="url">http://www.uib.no/ii</ref>
</desc>
<listRelation><relation active="#struct-300728" type="direct"></relation>
</listRelation>
<tutelles><tutelle active="#struct-300728" type="direct"><org type="institution" xml:id="struct-300728" status="VALID"><orgName>University of Bergen</orgName>
<desc><address><country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
</affiliation>
</author>
<author><name sortKey="Heggernes, Pinar" sort="Heggernes, Pinar" uniqKey="Heggernes P" first="Pinar" last="Heggernes">Pinar Heggernes</name>
<affiliation><hal:affiliation type="laboratory" xml:id="struct-20502" status="VALID"><orgName>Department of Informatics</orgName>
<desc><address><addrLine>Institutt for informatikk Universitetet i Bergen Postboks 7803 5020 Bergen</addrLine>
<country key="NO"></country>
</address>
<ref type="url">http://www.uib.no/ii</ref>
</desc>
<listRelation><relation active="#struct-300728" type="direct"></relation>
</listRelation>
<tutelles><tutelle active="#struct-300728" type="direct"><org type="institution" xml:id="struct-300728" status="VALID"><orgName>University of Bergen</orgName>
<desc><address><country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
</affiliation>
</author>
<author><name sortKey="Kratsch, Dieter" sort="Kratsch, Dieter" uniqKey="Kratsch D" first="Dieter" last="Kratsch">Dieter Kratsch</name>
<affiliation><hal:affiliation type="laboratory" xml:id="struct-402694" status="VALID"><idno type="IdRef">109477189</idno>
<idno type="IdUnivLorraine">[UL]RSG--</idno>
<idno type="RNSR">199914410X</idno>
<orgName>Laboratoire d'Informatique Théorique et Appliquée</orgName>
<orgName type="acronym">LITA</orgName>
<date type="start">2012-01-01</date>
<desc><address><addrLine>Université de Lorraine, Ile du Saulcy, 57045 Metz Cedex 1</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.lita.univ-lorraine.fr/</ref>
</desc>
<listRelation><relation name="EA3097" active="#struct-413289" type="direct"></relation>
</listRelation>
<tutelles><tutelle name="EA3097" active="#struct-413289" type="direct"><org type="institution" xml:id="struct-413289" status="VALID"><idno type="IdRef">157040569</idno>
<idno type="IdUnivLorraine">[UL]100--</idno>
<orgName>Université de Lorraine</orgName>
<orgName type="acronym">UL</orgName>
<date type="start">2012-01-01</date>
<desc><address><addrLine>34 cours Léopold - CS 25233 - 54052 Nancy cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.univ-lorraine.fr/</ref>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
</affiliation>
</author>
<author><name sortKey="Kucherov, Gregory" sort="Kucherov, Gregory" uniqKey="Kucherov G" first="Gregory" last="Kucherov">Gregory Kucherov</name>
<affiliation><hal:affiliation type="laboratory" xml:id="struct-2546" status="VALID"><orgName>Laboratoire d'Informatique Fondamentale de Lille</orgName>
<orgName type="acronym">LIFL</orgName>
<desc><address><addrLine>Bâtiment M3 59655 Villeneuve d'Ascq Cédex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.lifl.fr/</ref>
</desc>
<listRelation><relation active="#struct-301700" type="direct"></relation>
<relation active="#struct-92973" type="direct"></relation>
<relation active="#struct-300009" type="direct"></relation>
<relation name="UMR8022" active="#struct-441569" type="direct"></relation>
</listRelation>
<tutelles><tutelle active="#struct-301700" type="direct"><org type="institution" xml:id="struct-301700" status="VALID"><idno type="IdRef">026404524</idno>
<idno type="ISNI">0000000121517701</idno>
<orgName>Université de Lille, Sciences Humaines et Sociales</orgName>
<desc><address><addrLine>Domaine universitaire du "Pont de Bois"Rue du Barreau BP 60149 59653 Villeneuve d'Ascq Cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.univ-lille3.fr/</ref>
</desc>
</org>
</tutelle>
<tutelle active="#struct-92973" type="direct"><org type="institution" xml:id="struct-92973" status="VALID"><idno type="IdRef">026404184</idno>
<orgName>Université de Lille, Sciences et Technologies</orgName>
<desc><address><addrLine>Cité Scientifique - 59655 Villeneuve d'Ascq Cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.univ-lille1.fr/</ref>
</desc>
</org>
</tutelle>
<tutelle active="#struct-300009" type="direct"><org type="institution" xml:id="struct-300009" status="VALID"><orgName>Institut National de Recherche en Informatique et en Automatique</orgName>
<orgName type="acronym">Inria</orgName>
<desc><address><addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/en/</ref>
</desc>
</org>
</tutelle>
<tutelle name="UMR8022" active="#struct-441569" type="direct"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno>
<idno type="IdRef">02636817X</idno>
<orgName>Centre National de la Recherche Scientifique</orgName>
<orgName type="acronym">CNRS</orgName>
<date type="start">1939-10-19</date>
<desc><address><country key="FR"></country>
</address>
<ref type="url">http://www.cnrs.fr/</ref>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
</affiliation>
</author>
</analytic>
<idno type="DOI">10.1007/11821069</idno>
</biblStruct>
</sourceDesc>
</fileDesc>
<profileDesc><textClass></textClass>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en">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.</div>
</front>
</TEI>
<hal api="V3"><titleStmt><title xml:lang="en">Optimal Linear Arrangement of Interval Graphs</title>
<author role="aut"><persName><forename type="first">Johanne</forename>
<surname>Cohen</surname>
</persName>
<email>Johanne.Cohen@loria.fr</email>
<idno type="idhal">johanne-cohen</idno>
<idno type="halauthor">92180</idno>
<affiliation ref="#struct-160"></affiliation>
</author>
<author role="aut"><persName><forename type="first">Fedor</forename>
<surname>Fomin</surname>
</persName>
<email>Fedor.Fomin@ii.uib.no</email>
<idno type="halauthor">147135</idno>
<affiliation ref="#struct-20502"></affiliation>
</author>
<author role="aut"><persName><forename type="first">Pinar</forename>
<surname>Heggernes</surname>
</persName>
<email>Pinar.Heggernes@ii.uib.no</email>
<idno type="halauthor">147136</idno>
<affiliation ref="#struct-20502"></affiliation>
</author>
<author role="aut"><persName><forename type="first">Dieter</forename>
<surname>Kratsch</surname>
</persName>
<email>kratsch@sciences.univ-metz.fr</email>
<idno type="halauthor">147137</idno>
<affiliation ref="#struct-402694"></affiliation>
</author>
<author role="aut"><persName><forename type="first">Gregory</forename>
<surname>Kucherov</surname>
</persName>
<email>Gregory.Kucherov@lifl.fr</email>
<idno type="halauthor">66520</idno>
<affiliation ref="#struct-2546"></affiliation>
</author>
<editor role="depositor"><persName><forename>Gregory</forename>
<surname>Kucherov</surname>
</persName>
<email>Gregory.Kucherov@univ-mlv.fr</email>
</editor>
</titleStmt>
<editionStmt><edition n="v1" type="current"><date type="whenSubmitted">2006-11-20 17:15:34</date>
<date type="whenModified">2016-05-18 01:04:10</date>
<date type="whenReleased">2006-11-21 10:18:50</date>
<date type="whenProduced">2006-08-28</date>
<date type="whenEndEmbargoed">2006-11-20</date>
<ref type="file" target="https://hal.inria.fr/inria-00115249/document"><date notBefore="2006-11-20"></date>
</ref>
<ref type="file" subtype="greenPublisher" n="1" target="https://hal.inria.fr/inria-00115249/file/CohenEtAlMFCS06.pdf"><date notBefore="2006-11-20"></date>
</ref>
</edition>
<respStmt><resp>contributor</resp>
<name key="104025"><persName><forename>Gregory</forename>
<surname>Kucherov</surname>
</persName>
<email>Gregory.Kucherov@univ-mlv.fr</email>
</name>
</respStmt>
</editionStmt>
<publicationStmt><distributor>CCSD</distributor>
<idno type="halId">inria-00115249</idno>
<idno type="halUri">https://hal.inria.fr/inria-00115249</idno>
<idno type="halBibtex">cohen:inria-00115249</idno>
<idno type="halRefHtml">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; Mathematical Foundations of Computer Science 2006. <10.1007/11821069></idno>
<idno type="halRef">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; Mathematical Foundations of Computer Science 2006. <10.1007/11821069></idno>
</publicationStmt>
<seriesStmt><idno type="stamp" n="INRIA">INRIA - Institut National de Recherche en Informatique et en Automatique</idno>
<idno type="stamp" n="CNRS">CNRS - Centre national de la recherche scientifique</idno>
<idno type="stamp" n="INPL">Institut National Polytechnique de Lorraine</idno>
<idno type="stamp" n="LIFL">Laboratoire d'Informatique Fondamentale de Lille</idno>
<idno type="stamp" n="LORIA2">Publications du LORIA</idno>
<idno type="stamp" n="LABO-LORIA-SET" p="LORIA">LABO-LORIA-SET</idno>
<idno type="stamp" n="LORIA">LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications</idno>
<idno type="stamp" n="UNIV-LILLE3">Université de Lille Sciences humaines et sociales</idno>
<idno type="stamp" n="UNIV-LORRAINE">Université de Lorraine</idno>
</seriesStmt>
<notesStmt><note type="commentary">http://www.springerlink.com/content/wrk8346657167528/?p=a1f283d79ac14affb4d165501b84e569&pi=23</note>
<note type="audience" n="1">Not set</note>
<note type="invited" n="0">No</note>
<note type="popular" n="0">No</note>
<note type="peer" n="1">Yes</note>
<note type="proceedings" n="1">Yes</note>
</notesStmt>
<sourceDesc><biblStruct><analytic><title xml:lang="en">Optimal Linear Arrangement of Interval Graphs</title>
<author role="aut"><persName><forename type="first">Johanne</forename>
<surname>Cohen</surname>
</persName>
<email>Johanne.Cohen@loria.fr</email>
<idno type="idHal">johanne-cohen</idno>
<idno type="halAuthorId">92180</idno>
<affiliation ref="#struct-160"></affiliation>
</author>
<author role="aut"><persName><forename type="first">Fedor</forename>
<surname>Fomin</surname>
</persName>
<email>Fedor.Fomin@ii.uib.no</email>
<idno type="halAuthorId">147135</idno>
<affiliation ref="#struct-20502"></affiliation>
</author>
<author role="aut"><persName><forename type="first">Pinar</forename>
<surname>Heggernes</surname>
</persName>
<email>Pinar.Heggernes@ii.uib.no</email>
<idno type="halAuthorId">147136</idno>
<affiliation ref="#struct-20502"></affiliation>
</author>
<author role="aut"><persName><forename type="first">Dieter</forename>
<surname>Kratsch</surname>
</persName>
<email>kratsch@sciences.univ-metz.fr</email>
<idno type="halAuthorId">147137</idno>
<affiliation ref="#struct-402694"></affiliation>
</author>
<author role="aut"><persName><forename type="first">Gregory</forename>
<surname>Kucherov</surname>
</persName>
<email>Gregory.Kucherov@lifl.fr</email>
<idno type="halAuthorId">66520</idno>
<affiliation ref="#struct-2546"></affiliation>
</author>
</analytic>
<monogr><meeting><title>31st International Symposium on Mathematical Foundations of Computer Science - MFCS 2006</title>
<date type="start">2006-08-28</date>
<settlement>Stara Lesna/Slovakia</settlement>
</meeting>
<editor>Rastislav Kralovic and Pawel Urzyczyn</editor>
<imprint><publisher>Springer Verlag</publisher>
<biblScope unit="serie"></biblScope>
<biblScope unit="volume">4162</biblScope>
<biblScope unit="pp">267-279</biblScope>
<date type="datePub">2006-08-28</date>
</imprint>
</monogr>
<idno type="doi">10.1007/11821069</idno>
</biblStruct>
</sourceDesc>
<profileDesc><langUsage><language ident="en">English</language>
</langUsage>
<textClass><classCode scheme="halDomain" n="info.info-ds">Computer Science [cs]/Data Structures and Algorithms [cs.DS]</classCode>
<classCode scheme="halTypology" n="COMM">Conference papers</classCode>
</textClass>
<abstract xml:lang="en">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.</abstract>
</profileDesc>
</hal>
</record>
Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Hal/Corpus
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 003953 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Hal/Corpus/biblio.hfd -nk 003953 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien |wiki= Wicri/Lorraine |area= InforLorV4 |flux= Hal |étape= Corpus |type= RBID |clé= Hal:inria-00115249 |texte= Optimal Linear Arrangement of Interval Graphs }}
![]() | This area was generated with Dilib version V0.6.33. | ![]() |