A polynomial algorithm for finding T-span of generalized cacti

DOI10.1016/S0166-218X(02)00575-9MaRDI QIDQ1406033zbMATH OpenFDO

Authors Krzysztof Giaro, R. Janczewski, Michal Malafiejski

Publication date 9 September 2003

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0166-218X(02)00575-9

zbMATH Keywords

T-coloringT-spanthorny graph

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

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.

Recommendations

• An O(n n) algorithm for finding edge span of cacti
• scientific article; zbMATH DE number 1262806
• Spanners in Sparse Graphs
• scientific article; zbMATH DE number 1107724
• Spanning cactus of a graph: Existence, extension, optimization, and approximation

Cites work

• \(T\)-colorings of graphs
• \(T\)-colorings of graphs: recent results and open problems
• A rainbow about T-colorings for complete graphs
• Distance graphs and the T-coloring problem
• Further Results on T-Coloring and Frequency Assignment Problems
• scientific article; zbMATH DE number 3853101 (Why is no real title available?)
• scientific article; zbMATH DE number 4160759 (Why is no real title available?)
• List T-colorings of graphs
• The complexity of the \(T\)-coloring problem for graphs with small degree

Cited in

(4)

• Greedy \(T\)-colorings of graphs
• \(T\)-colorings, divisibility and the circular chromatic number
• The computational complexity of the backbone coloring problem for planar graphs with connected backbones
• Finding cactus roots in polynomial time

This page was built for publication: A polynomial algorithm for finding \(T\)-span of generalized cacti

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1406033)