A polynomial algorithm for finding \(T\)-span of generalized cacti
type: Item
instance of: scholarly article
title: A polynomial algorithm for finding \(T\)-span of generalized cacti
zbMATH Open document ID: 1023.05125
DOI: 10.1016/S0166-218X(02)00575-9
author: Krzysztof Giaro
author: R. Janczewski
author: Michal Malafiejski
published in: Discrete Applied Mathematics
publication date: 2003-09-09T00:00:00Z
review text: The authors study basically the minimum \(T\)-span problem for a diversity of graph classes. The general problem was proved to be NP-complete in the strong sense, however for numerous instances of the general problem exist polynomial-time algorithms. Subject of the paper are thorny graphs. The authors claim that, by the general algorithm for the problem, numerous classes of thorny graphs posses polynomial-time complexity. Nevertheless, the results for cacti are a little bit doubtful. The main reason is that the authors claim that the thorny graphs are planar and they use this claim for arguing. However, it is in contradiction to the famous Kuratowski's theorem on planar graphs. So for the time being the obtained results must be restricted to planar thorny graphs.
reviewed by: Adam Kapralski
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 1977904
zbMATH Keywords: T-coloring
zbMATH Keywords: T-span
zbMATH Keywords: thorny graph
MaRDI profile type: Publication
cites work: Q3322121
cites work: The complexity of the \(T\)-coloring problem for graphs with small degree
cites work: Distance graphs and the \(T\)-coloring problem
cites work: A rainbow about \(T\)-colorings for complete graphs
cites work: \(T\)-colorings of graphs
cites work: Further Results on T-Coloring and Frequency Assignment Problems
cites work: \(T\)-colorings of graphs: recent results and open problems
cites work: List \(T\)-colorings of graphs
cites work: Q3487366
description: scientific article; zbMATH DE number 1977904