InforLorV4, Hal, Corpus, bibRecord, 003953

Optimal Linear Arrangement of Interval Graphs

Identifieur interne : 003953 ( Hal/Corpus ); précédent : 003952; suivant : 003954

Optimal Linear Arrangement of Interval Graphs

Auteurs : Johanne Cohen ; Fedor Fomin ; Pinar Heggernes ; Dieter Kratsch ; Gregory Kucherov

Source :

RBID : Hal:inria-00115249

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:

https://hal.inria.fr/inria-00115249

DOI: 10.1007/11821069

Links to Exploration step

Hal:inria-00115249

Le 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

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.
Data generation: Mon Jun 10 21:56:28 2019. Site generation: Fri Feb 25 15:29:27 2022

	Serveur d'exploration sur la recherche en informatique en Lorraine
	Attention, ce site est en cours de développement ! Attention, site généré par des moyens informatiques à partir de corpus bruts. Les informations ne sont donc pas validées.

Serveur d'exploration sur la recherche en informatique en Lorraine

Optimal Linear Arrangement of Interval Graphs

Optimal Linear Arrangement of Interval Graphs

Source :

Abstract

Links to Exploration step

Le document en format XML

Pour manipuler ce document sous Unix (Dilib)

Pour mettre un lien sur cette page dans le réseau Wicri