Optimal linear arrangement of interval graphs
Identifieur interne :
000350 ( PascalFrancis/Corpus );
précédent :
000349;
suivant :
000351
Optimal linear arrangement of interval graphs
Auteurs : Johanne Cohen ;
Fedor Fomin ;
Pinar Heggemes ;
Dieter Kratsch ;
Gregory KucherovSource :
-
Lecture notes in computer science [ 0302-9743 ] ; 2006.
RBID : Pascal:08-0029305
Descripteurs français
- Pascal (Inist)
- Informatique théorique,
Temps polynomial,
Permutation,
Graphe linéaire,
Graphe intervalle,
Théorie graphe,
Problème agencement,
Problème NP difficile,
Intervalle temps,
Borne inférieure,
Algorithme rapide,
Algorithme approximation,
Arithmétique intervalle.
English descriptors
- KwdEn :
- Approximation algorithm,
Computer theory,
Fast algorithm,
Graph theory,
Interval arithmetic,
Interval graph,
Layout problem,
Linear graph,
Lower bound,
NP hard problem,
Permutation,
Polynomial time,
Time interval.
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.
Notice en format standard (ISO 2709)
Pour connaître la documentation sur le format Inist Standard.
| pA |
| A01 | 01 | 1 | | @0 0302-9743 |
|---|
| A05 | | | | @2 4162 |
|---|
| A08 | 01 | 1 | ENG | @1 Optimal linear arrangement of interval graphs |
|---|
| A09 | 01 | 1 | ENG | @1 Mathematical foundations of computer science 2006 : 31st international symposium, MFCS 2006, Stará Lesná, Slovakia, August 28-September 1, 2006 : proceedings |
|---|
| A11 | 01 | 1 | | @1 COHEN (Johanne) |
|---|
| A11 | 02 | 1 | | @1 FOMIN (Fedor) |
|---|
| A11 | 03 | 1 | | @1 HEGGEMES (Pinar) |
|---|
| A11 | 04 | 1 | | @1 KRATSCH (Dieter) |
|---|
| A11 | 05 | 1 | | @1 KUCHEROV (Gregory) |
|---|
| A12 | 01 | 1 | | @1 KRALOVIC (Rastislav) @9 ed. |
|---|
| A12 | 02 | 1 | | @1 URZYCZYN (Pawel) @9 ed. |
|---|
| A14 | 01 | | | @1 LORIA @2 54506 Vandoeuvre-lès-Nancy @3 FRA @Z 1 aut. |
|---|
| A14 | 02 | | | @1 Department of Informatics, University of Bergen @2 5020 Bergen @3 NOR @Z 2 aut. @Z 3 aut. |
|---|
| A14 | 03 | | | @1 LITA, Université de Metz @2 57045 Metz @3 FRA @Z 4 aut. |
|---|
| A14 | 04 | | | @1 LIFL/CNRS @2 59655 Villeneuve d'Ascq @3 FRA @Z 5 aut. |
|---|
| A20 | | | | @1 267-279 |
|---|
| A21 | | | | @1 2006 |
|---|
| A23 | 01 | | | @0 ENG |
|---|
| A26 | 01 | | | @0 3-540-37791-3 |
|---|
| A43 | 01 | | | @1 INIST @2 16343 @5 354000153640950230 |
|---|
| A44 | | | | @0 0000 @1 © 2008 INIST-CNRS. All rights reserved. |
|---|
| A45 | | | | @0 22 ref. |
|---|
| A47 | 01 | 1 | | @0 08-0029305 |
|---|
| A60 | | | | @1 P @2 C |
|---|
| A61 | | | | @0 A |
|---|
| A64 | 01 | 1 | | @0 Lecture notes in computer science |
|---|
| A66 | 01 | | | @0 DEU |
|---|
| A66 | 02 | | | @0 USA |
|---|
| C01 | 01 | | ENG | @0 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. |
|---|
| C02 | 01 | X | | @0 001D01A04 |
|---|
| C02 | 02 | X | | @0 001A02I01D |
|---|
| C02 | 03 | X | | @0 001D02A |
|---|
| C03 | 01 | X | FRE | @0 Informatique théorique @5 01 |
|---|
| C03 | 01 | X | ENG | @0 Computer theory @5 01 |
|---|
| C03 | 01 | X | SPA | @0 Informática teórica @5 01 |
|---|
| C03 | 02 | X | FRE | @0 Temps polynomial @5 06 |
|---|
| C03 | 02 | X | ENG | @0 Polynomial time @5 06 |
|---|
| C03 | 02 | X | SPA | @0 Tiempo polinomial @5 06 |
|---|
| C03 | 03 | X | FRE | @0 Permutation @5 07 |
|---|
| C03 | 03 | X | ENG | @0 Permutation @5 07 |
|---|
| C03 | 03 | X | SPA | @0 Permutación @5 07 |
|---|
| C03 | 04 | X | FRE | @0 Graphe linéaire @5 23 |
|---|
| C03 | 04 | X | ENG | @0 Linear graph @5 23 |
|---|
| C03 | 04 | X | SPA | @0 Grafo lineal @5 23 |
|---|
| C03 | 05 | X | FRE | @0 Graphe intervalle @5 24 |
|---|
| C03 | 05 | X | ENG | @0 Interval graph @5 24 |
|---|
| C03 | 05 | X | SPA | @0 Grafo intervalo @5 24 |
|---|
| C03 | 06 | X | FRE | @0 Théorie graphe @5 25 |
|---|
| C03 | 06 | X | ENG | @0 Graph theory @5 25 |
|---|
| C03 | 06 | X | SPA | @0 Teoría grafo @5 25 |
|---|
| C03 | 07 | X | FRE | @0 Problème agencement @5 26 |
|---|
| C03 | 07 | X | ENG | @0 Layout problem @5 26 |
|---|
| C03 | 07 | X | SPA | @0 Problema disposición @5 26 |
|---|
| C03 | 08 | X | FRE | @0 Problème NP difficile @5 27 |
|---|
| C03 | 08 | X | ENG | @0 NP hard problem @5 27 |
|---|
| C03 | 08 | X | SPA | @0 Problema NP duro @5 27 |
|---|
| C03 | 09 | X | FRE | @0 Intervalle temps @5 28 |
|---|
| C03 | 09 | X | ENG | @0 Time interval @5 28 |
|---|
| C03 | 09 | X | SPA | @0 Intervalo tiempo @5 28 |
|---|
| C03 | 10 | X | FRE | @0 Borne inférieure @5 29 |
|---|
| C03 | 10 | X | ENG | @0 Lower bound @5 29 |
|---|
| C03 | 10 | X | SPA | @0 Cota inferior @5 29 |
|---|
| C03 | 11 | X | FRE | @0 Algorithme rapide @5 30 |
|---|
| C03 | 11 | X | ENG | @0 Fast algorithm @5 30 |
|---|
| C03 | 11 | X | SPA | @0 Algoritmo rápido @5 30 |
|---|
| C03 | 12 | X | FRE | @0 Algorithme approximation @5 31 |
|---|
| C03 | 12 | X | ENG | @0 Approximation algorithm @5 31 |
|---|
| C03 | 12 | X | SPA | @0 Algoritmo aproximación @5 31 |
|---|
| C03 | 13 | X | FRE | @0 Arithmétique intervalle @5 32 |
|---|
| C03 | 13 | X | ENG | @0 Interval arithmetic @5 32 |
|---|
| C03 | 13 | X | SPA | @0 Aritmética intervalo @5 32 |
|---|
| N21 | | | | @1 052 |
|---|
| N44 | 01 | | | @1 OTO |
|---|
| N82 | | | | @1 OTO |
|---|
|
|---|
| pR |
| A30 | 01 | 1 | ENG | @1 International Symposium on Mathematical Foundations of Computer Science @2 31 @3 Stará Lesná SVK @4 2006 |
|---|
|
|---|
Format Inist (serveur)
| NO : | PASCAL 08-0029305 INIST |
|---|
| ET : | Optimal linear arrangement of interval graphs |
|---|
| AU : | COHEN (Johanne); FOMIN (Fedor); HEGGEMES (Pinar); KRATSCH (Dieter); KUCHEROV (Gregory); KRALOVIC (Rastislav); URZYCZYN (Pawel) |
|---|
| AF : | LORIA/54506 Vandoeuvre-lès-Nancy/France (1 aut.); Department of Informatics, University of Bergen/5020 Bergen/Norvège (2 aut., 3 aut.); LITA, Université de Metz/57045 Metz/France (4 aut.); LIFL/CNRS/59655 Villeneuve d'Ascq/France (5 aut.) |
|---|
| DT : | Publication en série; Congrès; Niveau analytique |
|---|
| SO : | Lecture notes in computer science; ISSN 0302-9743; Allemagne; Da. 2006; Vol. 4162; Pp. 267-279; Bibl. 22 ref. |
|---|
| LA : | Anglais |
|---|
| EA : | 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. |
|---|
| CC : | 001D01A04; 001A02I01D; 001D02A |
|---|
| FD : | Informatique théorique; Temps polynomial; Permutation; Graphe linéaire; Graphe intervalle; Théorie graphe; Problème agencement; Problème NP difficile; Intervalle temps; Borne inférieure; Algorithme rapide; Algorithme approximation; Arithmétique intervalle |
|---|
| ED : | Computer theory; Polynomial time; Permutation; Linear graph; Interval graph; Graph theory; Layout problem; NP hard problem; Time interval; Lower bound; Fast algorithm; Approximation algorithm; Interval arithmetic |
|---|
| SD : | Informática teórica; Tiempo polinomial; Permutación; Grafo lineal; Grafo intervalo; Teoría grafo; Problema disposición; Problema NP duro; Intervalo tiempo; Cota inferior; Algoritmo rápido; Algoritmo aproximación; Aritmética intervalo |
|---|
| LO : | INIST-16343.354000153640950230 |
|---|
| ID : | 08-0029305 |
|---|
Links to Exploration step
Pascal:08-0029305
Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en" level="a">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><inist:fA14 i1="01"><s1>LORIA</s1>
<s2>54506 Vandoeuvre-lès-Nancy</s2>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
</inist:fA14><author><name sortKey="Fomin, Fedor" sort="Fomin, Fedor" uniqKey="Fomin F" first="Fedor" last="Fomin">Fedor Fomin</name>
<affiliation><inist:fA14 i1="02"><s1>Department of Informatics, University of Bergen</s1>
<s2>5020 Bergen</s2>
<s3>NOR</s3>
<sZ>2 aut.</sZ>
<sZ>3 aut.</sZ>
</inist:fA14><author><name sortKey="Heggemes, Pinar" sort="Heggemes, Pinar" uniqKey="Heggemes P" first="Pinar" last="Heggemes">Pinar Heggemes</name>
<affiliation><inist:fA14 i1="02"><s1>Department of Informatics, University of Bergen</s1>
<s2>5020 Bergen</s2>
<s3>NOR</s3>
<sZ>2 aut.</sZ>
<sZ>3 aut.</sZ>
</inist:fA14><author><name sortKey="Kratsch, Dieter" sort="Kratsch, Dieter" uniqKey="Kratsch D" first="Dieter" last="Kratsch">Dieter Kratsch</name>
<affiliation><inist:fA14 i1="03"><s1>LITA, Université de Metz</s1>
<s2>57045 Metz</s2>
<s3>FRA</s3>
<sZ>4 aut.</sZ>
</inist:fA14><author><name sortKey="Kucherov, Gregory" sort="Kucherov, Gregory" uniqKey="Kucherov G" first="Gregory" last="Kucherov">Gregory Kucherov</name>
<affiliation><inist:fA14 i1="04"><s1>LIFL/CNRS</s1>
<s2>59655 Villeneuve d'Ascq</s2>
<s3>FRA</s3>
<sZ>5 aut.</sZ>
</inist:fA14><publicationStmt><idno type="wicri:source">INIST</idno>
<idno type="inist">08-0029305</idno>
<date when="2006">2006</date>
<idno type="stanalyst">PASCAL 08-0029305 INIST</idno>
<idno type="RBID">Pascal:08-0029305</idno>
<idno type="wicri:Area/PascalFrancis/Corpus">000350</idno>
</publicationStmt><sourceDesc><biblStruct><analytic><title xml:lang="en" level="a">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><inist:fA14 i1="01"><s1>LORIA</s1>
<s2>54506 Vandoeuvre-lès-Nancy</s2>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
</inist:fA14><author><name sortKey="Fomin, Fedor" sort="Fomin, Fedor" uniqKey="Fomin F" first="Fedor" last="Fomin">Fedor Fomin</name>
<affiliation><inist:fA14 i1="02"><s1>Department of Informatics, University of Bergen</s1>
<s2>5020 Bergen</s2>
<s3>NOR</s3>
<sZ>2 aut.</sZ>
<sZ>3 aut.</sZ>
</inist:fA14><author><name sortKey="Heggemes, Pinar" sort="Heggemes, Pinar" uniqKey="Heggemes P" first="Pinar" last="Heggemes">Pinar Heggemes</name>
<affiliation><inist:fA14 i1="02"><s1>Department of Informatics, University of Bergen</s1>
<s2>5020 Bergen</s2>
<s3>NOR</s3>
<sZ>2 aut.</sZ>
<sZ>3 aut.</sZ>
</inist:fA14><author><name sortKey="Kratsch, Dieter" sort="Kratsch, Dieter" uniqKey="Kratsch D" first="Dieter" last="Kratsch">Dieter Kratsch</name>
<affiliation><inist:fA14 i1="03"><s1>LITA, Université de Metz</s1>
<s2>57045 Metz</s2>
<s3>FRA</s3>
<sZ>4 aut.</sZ>
</inist:fA14><author><name sortKey="Kucherov, Gregory" sort="Kucherov, Gregory" uniqKey="Kucherov G" first="Gregory" last="Kucherov">Gregory Kucherov</name>
<affiliation><inist:fA14 i1="04"><s1>LIFL/CNRS</s1>
<s2>59655 Villeneuve d'Ascq</s2>
<s3>FRA</s3>
<sZ>5 aut.</sZ>
</inist:fA14><series><title level="j" type="main">Lecture notes in computer science</title>
<idno type="ISSN">0302-9743</idno>
<imprint><date when="2006">2006</date>
</imprint><seriesStmt><title level="j" type="main">Lecture notes in computer science</title>
<idno type="ISSN">0302-9743</idno>
</seriesStmt><profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Approximation algorithm</term>
<term>Computer theory</term>
<term>Fast algorithm</term>
<term>Graph theory</term>
<term>Interval arithmetic</term>
<term>Interval graph</term>
<term>Layout problem</term>
<term>Linear graph</term>
<term>Lower bound</term>
<term>NP hard problem</term>
<term>Permutation</term>
<term>Polynomial time</term>
<term>Time interval</term>
</keywords><keywords scheme="Pascal" xml:lang="fr"><term>Informatique théorique</term>
<term>Temps polynomial</term>
<term>Permutation</term>
<term>Graphe linéaire</term>
<term>Graphe intervalle</term>
<term>Théorie graphe</term>
<term>Problème agencement</term>
<term>Problème NP difficile</term>
<term>Intervalle temps</term>
<term>Borne inférieure</term>
<term>Algorithme rapide</term>
<term>Algorithme approximation</term>
<term>Arithmétique intervalle</term>
</keywords><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><inist><standard h6="B"><pA><fA01 i1="01" i2="1"><s0>0302-9743</s0>
</fA01><fA05><s2>4162</s2>
</fA05><fA08 i1="01" i2="1" l="ENG"><s1>Optimal linear arrangement of interval graphs</s1>
</fA08><fA09 i1="01" i2="1" l="ENG"><s1>Mathematical foundations of computer science 2006 : 31st international symposium, MFCS 2006, Stará Lesná, Slovakia, August 28-September 1, 2006 : proceedings</s1>
</fA09><fA11 i1="01" i2="1"><s1>COHEN (Johanne)</s1>
</fA11><fA11 i1="02" i2="1"><s1>FOMIN (Fedor)</s1>
</fA11><fA11 i1="03" i2="1"><s1>HEGGEMES (Pinar)</s1>
</fA11><fA11 i1="04" i2="1"><s1>KRATSCH (Dieter)</s1>
</fA11><fA11 i1="05" i2="1"><s1>KUCHEROV (Gregory)</s1>
</fA11><fA12 i1="01" i2="1"><s1>KRALOVIC (Rastislav)</s1>
<s9>ed.</s9>
</fA12><fA12 i1="02" i2="1"><s1>URZYCZYN (Pawel)</s1>
<s9>ed.</s9>
</fA12><fA14 i1="01"><s1>LORIA</s1>
<s2>54506 Vandoeuvre-lès-Nancy</s2>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
</fA14><fA14 i1="02"><s1>Department of Informatics, University of Bergen</s1>
<s2>5020 Bergen</s2>
<s3>NOR</s3>
<sZ>2 aut.</sZ>
<sZ>3 aut.</sZ>
</fA14><fA14 i1="03"><s1>LITA, Université de Metz</s1>
<s2>57045 Metz</s2>
<s3>FRA</s3>
<sZ>4 aut.</sZ>
</fA14><fA14 i1="04"><s1>LIFL/CNRS</s1>
<s2>59655 Villeneuve d'Ascq</s2>
<s3>FRA</s3>
<sZ>5 aut.</sZ>
</fA14><fA20><s1>267-279</s1>
</fA20><fA21><s1>2006</s1>
</fA21><fA23 i1="01"><s0>ENG</s0>
</fA23><fA26 i1="01"><s0>3-540-37791-3</s0>
</fA26><fA43 i1="01"><s1>INIST</s1>
<s2>16343</s2>
<s5>354000153640950230</s5>
</fA43><fA44><s0>0000</s0>
<s1>© 2008 INIST-CNRS. All rights reserved.</s1>
</fA44><fA45><s0>22 ref.</s0>
</fA45><fA47 i1="01" i2="1"><s0>08-0029305</s0>
</fA47><fA60><s1>P</s1>
<s2>C</s2>
</fA60><fA64 i1="01" i2="1"><s0>Lecture notes in computer science</s0>
</fA64><fA66 i1="01"><s0>DEU</s0>
</fA66><fA66 i1="02"><s0>USA</s0>
</fA66><fC01 i1="01" l="ENG"><s0>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.</s0>
</fC01><fC02 i1="01" i2="X"><s0>001D01A04</s0>
</fC02><fC02 i1="02" i2="X"><s0>001A02I01D</s0>
</fC02><fC02 i1="03" i2="X"><s0>001D02A</s0>
</fC02><fC03 i1="01" i2="X" l="FRE"><s0>Informatique théorique</s0>
<s5>01</s5>
</fC03><fC03 i1="01" i2="X" l="ENG"><s0>Computer theory</s0>
<s5>01</s5>
</fC03><fC03 i1="01" i2="X" l="SPA"><s0>Informática teórica</s0>
<s5>01</s5>
</fC03><fC03 i1="02" i2="X" l="FRE"><s0>Temps polynomial</s0>
<s5>06</s5>
</fC03><fC03 i1="02" i2="X" l="ENG"><s0>Polynomial time</s0>
<s5>06</s5>
</fC03><fC03 i1="02" i2="X" l="SPA"><s0>Tiempo polinomial</s0>
<s5>06</s5>
</fC03><fC03 i1="03" i2="X" l="FRE"><s0>Permutation</s0>
<s5>07</s5>
</fC03><fC03 i1="03" i2="X" l="ENG"><s0>Permutation</s0>
<s5>07</s5>
</fC03><fC03 i1="03" i2="X" l="SPA"><s0>Permutación</s0>
<s5>07</s5>
</fC03><fC03 i1="04" i2="X" l="FRE"><s0>Graphe linéaire</s0>
<s5>23</s5>
</fC03><fC03 i1="04" i2="X" l="ENG"><s0>Linear graph</s0>
<s5>23</s5>
</fC03><fC03 i1="04" i2="X" l="SPA"><s0>Grafo lineal</s0>
<s5>23</s5>
</fC03><fC03 i1="05" i2="X" l="FRE"><s0>Graphe intervalle</s0>
<s5>24</s5>
</fC03><fC03 i1="05" i2="X" l="ENG"><s0>Interval graph</s0>
<s5>24</s5>
</fC03><fC03 i1="05" i2="X" l="SPA"><s0>Grafo intervalo</s0>
<s5>24</s5>
</fC03><fC03 i1="06" i2="X" l="FRE"><s0>Théorie graphe</s0>
<s5>25</s5>
</fC03><fC03 i1="06" i2="X" l="ENG"><s0>Graph theory</s0>
<s5>25</s5>
</fC03><fC03 i1="06" i2="X" l="SPA"><s0>Teoría grafo</s0>
<s5>25</s5>
</fC03><fC03 i1="07" i2="X" l="FRE"><s0>Problème agencement</s0>
<s5>26</s5>
</fC03><fC03 i1="07" i2="X" l="ENG"><s0>Layout problem</s0>
<s5>26</s5>
</fC03><fC03 i1="07" i2="X" l="SPA"><s0>Problema disposición</s0>
<s5>26</s5>
</fC03><fC03 i1="08" i2="X" l="FRE"><s0>Problème NP difficile</s0>
<s5>27</s5>
</fC03><fC03 i1="08" i2="X" l="ENG"><s0>NP hard problem</s0>
<s5>27</s5>
</fC03><fC03 i1="08" i2="X" l="SPA"><s0>Problema NP duro</s0>
<s5>27</s5>
</fC03><fC03 i1="09" i2="X" l="FRE"><s0>Intervalle temps</s0>
<s5>28</s5>
</fC03><fC03 i1="09" i2="X" l="ENG"><s0>Time interval</s0>
<s5>28</s5>
</fC03><fC03 i1="09" i2="X" l="SPA"><s0>Intervalo tiempo</s0>
<s5>28</s5>
</fC03><fC03 i1="10" i2="X" l="FRE"><s0>Borne inférieure</s0>
<s5>29</s5>
</fC03><fC03 i1="10" i2="X" l="ENG"><s0>Lower bound</s0>
<s5>29</s5>
</fC03><fC03 i1="10" i2="X" l="SPA"><s0>Cota inferior</s0>
<s5>29</s5>
</fC03><fC03 i1="11" i2="X" l="FRE"><s0>Algorithme rapide</s0>
<s5>30</s5>
</fC03><fC03 i1="11" i2="X" l="ENG"><s0>Fast algorithm</s0>
<s5>30</s5>
</fC03><fC03 i1="11" i2="X" l="SPA"><s0>Algoritmo rápido</s0>
<s5>30</s5>
</fC03><fC03 i1="12" i2="X" l="FRE"><s0>Algorithme approximation</s0>
<s5>31</s5>
</fC03><fC03 i1="12" i2="X" l="ENG"><s0>Approximation algorithm</s0>
<s5>31</s5>
</fC03><fC03 i1="12" i2="X" l="SPA"><s0>Algoritmo aproximación</s0>
<s5>31</s5>
</fC03><fC03 i1="13" i2="X" l="FRE"><s0>Arithmétique intervalle</s0>
<s5>32</s5>
</fC03><fC03 i1="13" i2="X" l="ENG"><s0>Interval arithmetic</s0>
<s5>32</s5>
</fC03><fC03 i1="13" i2="X" l="SPA"><s0>Aritmética intervalo</s0>
<s5>32</s5>
</fC03><fN21><s1>052</s1>
</fN21><fN44 i1="01"><s1>OTO</s1>
</fN44><fN82><s1>OTO</s1>
</fN82><pR><fA30 i1="01" i2="1" l="ENG"><s1>International Symposium on Mathematical Foundations of Computer Science</s1>
<s2>31</s2>
<s3>Stará Lesná SVK</s3>
<s4>2006</s4>
</fA30><server><NO>PASCAL 08-0029305 INIST</NO>
<ET>Optimal linear arrangement of interval graphs</ET>
<AU>COHEN (Johanne); FOMIN (Fedor); HEGGEMES (Pinar); KRATSCH (Dieter); KUCHEROV (Gregory); KRALOVIC (Rastislav); URZYCZYN (Pawel)</AU>
<AF>LORIA/54506 Vandoeuvre-lès-Nancy/France (1 aut.); Department of Informatics, University of Bergen/5020 Bergen/Norvège (2 aut., 3 aut.); LITA, Université de Metz/57045 Metz/France (4 aut.); LIFL/CNRS/59655 Villeneuve d'Ascq/France (5 aut.)</AF>
<DT>Publication en série; Congrès; Niveau analytique</DT>
<SO>Lecture notes in computer science; ISSN 0302-9743; Allemagne; Da. 2006; Vol. 4162; Pp. 267-279; Bibl. 22 ref.</SO>
<LA>Anglais</LA>
<EA>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.</EA>
<CC>001D01A04; 001A02I01D; 001D02A</CC>
<FD>Informatique théorique; Temps polynomial; Permutation; Graphe linéaire; Graphe intervalle; Théorie graphe; Problème agencement; Problème NP difficile; Intervalle temps; Borne inférieure; Algorithme rapide; Algorithme approximation; Arithmétique intervalle</FD>
<ED>Computer theory; Polynomial time; Permutation; Linear graph; Interval graph; Graph theory; Layout problem; NP hard problem; Time interval; Lower bound; Fast algorithm; Approximation algorithm; Interval arithmetic</ED>
<SD>Informática teórica; Tiempo polinomial; Permutación; Grafo lineal; Grafo intervalo; Teoría grafo; Problema disposición; Problema NP duro; Intervalo tiempo; Cota inferior; Algoritmo rápido; Algoritmo aproximación; Aritmética intervalo</SD>
<LO>INIST-16343.354000153640950230</LO>
<ID>08-0029305</ID>
</server>
Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/PascalFrancis/Corpus
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000350 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/PascalFrancis/Corpus/biblio.hfd -nk 000350 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Lorraine
|area= InforLorV4
|flux= PascalFrancis
|étape= Corpus
|type= RBID
|clé= Pascal:08-0029305
|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 |  |
