Generalized coloring for tree-like graphs
Identifieur interne : 002444 ( Main/Exploration ); précédent : 002443; suivant : 002445Generalized coloring for tree-like graphs
Auteurs : Klaus Jansen [Allemagne] ; Petra Scheffler [Allemagne]Source :
- Discrete Applied Mathematics [ 0166-218X ] ; 1997.
Descripteurs français
- Pascal (Inist)
English descriptors
- KwdEn :
Abstract
We discuss the Precoloring Extension (PrExt) and the List Coloring (LiCol) problems for trees, partial k-trees and cographs in the decision and the construction versions. Both problems for partial k-trees are solved in linear time when the number of colors is bounded by a constant and in polynomial time for an unbounded number of colors. For trees, we improve this to linear time. In contrast to that, the two problems differ in complexity for cographs. While PrExt has a linear-time decision algorithm, LiCol is shown to be NP-complete. We give polynomial-time algorithms for the corresponding enumeration problems # PrExt and # LiCol on partial k-trees and trees and for # PrExt on cographs.
Url:
DOI: 10.1016/S0166-218X(96)00085-6
Affiliations:
Links toward previous steps (curation, corpus...)
- to stream Istex, to step Corpus: 001270
- to stream Istex, to step Curation: 001158
- to stream Istex, to step Checkpoint: 000F16
- to stream Main, to step Merge: 002879
- to stream PascalFrancis, to step Corpus: 001385
- to stream PascalFrancis, to step Curation: 001607
- to stream PascalFrancis, to step Checkpoint: 001052
- to stream Main, to step Merge: 002A34
- to stream Main, to step Curation: 002444
Le document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title>Generalized coloring for tree-like graphs</title><author><name sortKey="Jansen, Klaus" sort="Jansen, Klaus" uniqKey="Jansen K" first="Klaus" last="Jansen">Klaus Jansen</name></author><author><name sortKey="Scheffler, Petra" sort="Scheffler, Petra" uniqKey="Scheffler P" first="Petra" last="Scheffler">Petra Scheffler</name></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:B786DB27747FE60A5EF8B582C4EBFCCFEEA2D041</idno><date when="1997" year="1997">1997</date><idno type="doi">10.1016/S0166-218X(96)00085-6</idno><idno type="url">https://api.istex.fr/document/B786DB27747FE60A5EF8B582C4EBFCCFEEA2D041/fulltext/pdf</idno><idno type="wicri:Area/Istex/Corpus">001270</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">001270</idno><idno type="wicri:Area/Istex/Curation">001158</idno><idno type="wicri:Area/Istex/Checkpoint">000F16</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Checkpoint">000F16</idno><idno type="wicri:doubleKey">0166-218X:1997:Jansen K:generalized:coloring:for</idno><idno type="wicri:Area/Main/Merge">002879</idno><idno type="wicri:source">INIST</idno><idno type="RBID">Pascal:97-0348288</idno><idno type="wicri:Area/PascalFrancis/Corpus">001385</idno><idno type="wicri:Area/PascalFrancis/Curation">001607</idno><idno type="wicri:Area/PascalFrancis/Checkpoint">001052</idno><idno type="wicri:explorRef" wicri:stream="PascalFrancis" wicri:step="Checkpoint">001052</idno><idno type="wicri:doubleKey">0166-218X:1997:Jansen K:generalized:coloring:for</idno><idno type="wicri:Area/Main/Merge">002A34</idno><idno type="wicri:Area/Main/Curation">002444</idno><idno type="wicri:Area/Main/Exploration">002444</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a">Generalized coloring for tree-like graphs</title><author><name sortKey="Jansen, Klaus" sort="Jansen, Klaus" uniqKey="Jansen K" first="Klaus" last="Jansen">Klaus Jansen</name><affiliation wicri:level="1"><country wicri:rule="url">Allemagne</country></affiliation><affiliation wicri:level="1"><country xml:lang="fr">Allemagne</country><wicri:regionArea>FB IV — Mathematik und Informatik, Universität Trier, Postfach 38 25, D-54286 Trier</wicri:regionArea><wicri:noRegion>54286 Trier</wicri:noRegion><wicri:noRegion>D-54286 Trier</wicri:noRegion></affiliation></author><author><name sortKey="Scheffler, Petra" sort="Scheffler, Petra" uniqKey="Scheffler P" first="Petra" last="Scheffler">Petra Scheffler</name><affiliation wicri:level="1"><country xml:lang="fr">Allemagne</country><wicri:regionArea>Fachbereich Wirtschaft, Fachhochschule Stralsund, Groβe Parower Straβe 145, D-18435 Stralsund</wicri:regionArea><wicri:noRegion>18435 Stralsund</wicri:noRegion><wicri:noRegion>D-18435 Stralsund</wicri:noRegion></affiliation></author></analytic><monogr></monogr><series><title level="j">Discrete Applied Mathematics</title><title level="j" type="abbrev">DAM</title><idno type="ISSN">0166-218X</idno><imprint><publisher>ELSEVIER</publisher><date type="published" when="1997">1997</date><biblScope unit="volume">75</biblScope><biblScope unit="issue">2</biblScope><biblScope unit="page" from="135">135</biblScope><biblScope unit="page" to="155">155</biblScope></imprint><idno type="ISSN">0166-218X</idno></series><idno type="istex">B786DB27747FE60A5EF8B582C4EBFCCFEEA2D041</idno><idno type="DOI">10.1016/S0166-218X(96)00085-6</idno><idno type="PII">S0166-218X(96)00085-6</idno></biblStruct></sourceDesc><seriesStmt><idno type="ISSN">0166-218X</idno></seriesStmt></fileDesc><profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Algorithm</term><term>Computational complexity</term><term>Graph colouring</term><term>Linear time</term><term>NP complete problem</term><term>Polynomial time</term><term>Tree(graph)</term></keywords><keywords scheme="Pascal" xml:lang="fr"><term>Algorithme</term><term>Arbre graphe</term><term>Coloration graphe</term><term>Complexité calcul</term><term>Problème NP complet</term><term>Temps linéaire</term><term>Temps polynomial</term></keywords></textClass><langUsage><language ident="en">en</language></langUsage></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">We discuss the Precoloring Extension (PrExt) and the List Coloring (LiCol) problems for trees, partial k-trees and cographs in the decision and the construction versions. Both problems for partial k-trees are solved in linear time when the number of colors is bounded by a constant and in polynomial time for an unbounded number of colors. For trees, we improve this to linear time. In contrast to that, the two problems differ in complexity for cographs. While PrExt has a linear-time decision algorithm, LiCol is shown to be NP-complete. We give polynomial-time algorithms for the corresponding enumeration problems # PrExt and # LiCol on partial k-trees and trees and for # PrExt on cographs.</div></front></TEI><affiliations><list><country><li>Allemagne</li></country></list><tree><country name="Allemagne"><noRegion><name sortKey="Jansen, Klaus" sort="Jansen, Klaus" uniqKey="Jansen K" first="Klaus" last="Jansen">Klaus Jansen</name></noRegion><name sortKey="Jansen, Klaus" sort="Jansen, Klaus" uniqKey="Jansen K" first="Klaus" last="Jansen">Klaus Jansen</name><name sortKey="Scheffler, Petra" sort="Scheffler, Petra" uniqKey="Scheffler P" first="Petra" last="Scheffler">Petra Scheffler</name></country></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Rhénanie/explor/UnivTrevesV1/Data/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 002444 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 002444 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Rhénanie
|area= UnivTrevesV1
|flux= Main
|étape= Exploration
|type= RBID
|clé= ISTEX:B786DB27747FE60A5EF8B582C4EBFCCFEEA2D041
|texte= Generalized coloring for tree-like graphs
}}
| This area was generated with Dilib version V0.6.31. |  |