A polynomial algorithm for finding \(T\)-span of generalized cacti (Q1406033): Difference between revisions

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.