Generalized coloring for tree-like graphs
Identifieur interne : 001158 ( Istex/Curation ); précédent : 001157; suivant : 001159Generalized coloring for tree-like graphs
Auteurs : Klaus Jansen [Allemagne] ; Petra Scheffler [Allemagne]Source :
- Discrete Applied Mathematics [ 0166-218X ] ; 1997.
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
Links toward previous steps (curation, corpus...)
- to stream Istex, to step Corpus: Pour aller vers cette notice dans l'étape Curation :001270
Links to Exploration step
ISTEX:B786DB27747FE60A5EF8B582C4EBFCCFEEA2D041Le 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>
<affiliation wicri:level="1"><mods:affiliation>E-mail: jansen@dm3.uni-trier.de</mods:affiliation>
<country wicri:rule="url">Allemagne</country>
</affiliation>
<affiliation wicri:level="1"><mods:affiliation>FB IV — Mathematik und Informatik, Universität Trier, Postfach 38 25, D-54286 Trier, Germany</mods:affiliation>
<country xml:lang="fr">Allemagne</country>
<wicri:regionArea>FB IV — Mathematik und Informatik, Universität Trier, Postfach 38 25, D-54286 Trier</wicri:regionArea>
</affiliation>
</author>
<author><name sortKey="Scheffler, Petra" sort="Scheffler, Petra" uniqKey="Scheffler P" first="Petra" last="Scheffler">Petra Scheffler</name>
<affiliation wicri:level="1"><mods:affiliation>Fachbereich Wirtschaft, Fachhochschule Stralsund, Groβe Parower Straβe 145, D-18435 Stralsund, Germany</mods:affiliation>
<country xml:lang="fr">Allemagne</country>
<wicri:regionArea>Fachbereich Wirtschaft, Fachhochschule Stralsund, Groβe Parower Straβe 145, D-18435 Stralsund</wicri:regionArea>
</affiliation>
</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>
</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"><mods:affiliation>E-mail: jansen@dm3.uni-trier.de</mods:affiliation>
<country wicri:rule="url">Allemagne</country>
</affiliation>
<affiliation wicri:level="1"><mods:affiliation>FB IV — Mathematik und Informatik, Universität Trier, Postfach 38 25, D-54286 Trier, Germany</mods:affiliation>
<country xml:lang="fr">Allemagne</country>
<wicri:regionArea>FB IV — Mathematik und Informatik, Universität Trier, Postfach 38 25, D-54286 Trier</wicri:regionArea>
</affiliation>
</author>
<author><name sortKey="Scheffler, Petra" sort="Scheffler, Petra" uniqKey="Scheffler P" first="Petra" last="Scheffler">Petra Scheffler</name>
<affiliation wicri:level="1"><mods:affiliation>Fachbereich Wirtschaft, Fachhochschule Stralsund, Groβe Parower Straβe 145, D-18435 Stralsund, Germany</mods:affiliation>
<country xml:lang="fr">Allemagne</country>
<wicri:regionArea>Fachbereich Wirtschaft, Fachhochschule Stralsund, Groβe Parower Straβe 145, D-18435 Stralsund</wicri:regionArea>
</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></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>
</record>
Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Rhénanie/explor/UnivTrevesV1/Data/Istex/Curation
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 001158 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Istex/Curation/biblio.hfd -nk 001158 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien |wiki= Wicri/Rhénanie |area= UnivTrevesV1 |flux= Istex |étape= Curation |type= RBID |clé= ISTEX:B786DB27747FE60A5EF8B582C4EBFCCFEEA2D041 |texte= Generalized coloring for tree-like graphs }}
This area was generated with Dilib version V0.6.31. |