×

A note on the computational complexity of computing the edge rotation distance between graphs. (English) Zbl 0635.68072

Summary: The problem of computing the edge rotation distance between trees is shown to be NP-hard.

MSC:

68R10 Graph theory (including graph drawing) in computer science
68Q25 Analysis of algorithms and problem complexity
05C99 Graph theory
PDF BibTeX XML Cite
Full Text: EuDML