×
Pallo, Jean

An efficient upper bound of the rotation distance of binary trees. (English) Zbl 1014.68112

Inf. Process. Lett. 73, No. 3-4, 87-92 (2000).
Summary: A polynomial time algorithm is developed for computing an upper bound for the rotation distance of binary trees and equivalently for the diagonal-flip distance of convex polygons triangulations. Ordinal tools are used.

Cited in 25 Documents

MSC:

68R10 Graph theory (including graph drawing) in computer science
68P05 Data structures
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
05C85 Graph algorithms (graph-theoretic aspects)

Keywords:

polynomial time algorithm

Software:

OEIS
Cite Review PDF
Full Text: DOI

References:

[1] Aldous, D., Triangulating the circle, at random, Amer. Math. Monthly, Vol. 101, 223-233 (1994) · Zbl 0804.52011
[2] Culik, K.; Wood, D., A note on some tree similarity measures, Inform. Process. Lett., Vol. 15, 39-42 (1982) · Zbl 0489.68058
[3] Dutton, R. D.; Rogers, R. O., Properties of the rotation graph of binary trees, Congr. Numer., Vol. 109, 51-63 (1995) · Zbl 0905.05021
[4] Germain, C.; Pallo, J., The number of coverings in four Catalan lattices, Internat. J. Comput. Math., Vol. 61, 19-28 (1996) · Zbl 1001.05500
[5] Hanke, S.; Ottmann, T.; Schuierer, S., The edge-flipping distance of triangulations, J. Universal Comput. Sci., Vol. 2, 570-579 (1996) · Zbl 0955.68122
[6] Harary, F.; Palmer, E. M.; Read, R. C., On the cell-growth problem for arbitrary polygons, Discrete Math., Vol. 11, 371-389 (1975) · Zbl 0301.05119
[7] Hurtado, F.; Noy, M.; Urrutia, J., Flipping edges in triangulations, Discrete Comput. Geom., Vol. 22, 333-346 (1999) · Zbl 0939.68135
[8] Li, M.; Zhang, L., Better approximation of diagonal-flip transformation and rotation transformation, (Hsu, W. L., Proc. 4th Annual Conf. Computing and Combinatorics. Proc. 4th Annual Conf. Computing and Combinatorics, Lecture Notes in Computer Science, Vol. 1449 (1998), Springer: Springer Berlin), 85-94 · Zbl 0910.68220
[9] Luccio, F.; Pagli, L., On the upper bound on the rotation distance of binary trees, Inform. Process. Lett., Vol. 31, 57-60 (1989) · Zbl 0681.05024
[10] Mäkinen, E., On the rotation distance of binary trees, Inform. Process. Lett., Vol. 26, 271-272 (198788)
[11] Moon, J. W.; Moser, L., Triangular dissections of \(n\)-gons, Canad. Math. Bull., Vol. 6, 175-178 (1963) · Zbl 0118.25701
[12] Pallo, J., Enumerating, ranking and unranking binary trees, Comput. J., Vol. 29, 171-175 (1986) · Zbl 0585.68066
[13] Pallo, J., On the rotation distance in the lattice of binary trees, Inform. Process. Lett., Vol. 25, 369-373 (1987)
[14] Ruskey, F., On the average shape of binary trees, SIAM J. Alg. Disc. Meth., Vol. 1, 43-50 (1980) · Zbl 0496.68044
[15] Ruskey, F.; Hu, T. C., Generating binary trees lexicographically, SIAM J. Comput., Vol. 6, 745-758 (1977) · Zbl 0366.68027
[16] Sleator, D. D.; Tarjan, R. E.; Thurston, W. R., Rotation distance, (Cover, T. M.; Gopinath, B., Open Problems in Communication and Computation (1987), Springer: Springer Berlin), 130-137 · Zbl 0628.68001
[17] Sleator, D. D.; Tarjan, R. E.; Thurston, W. R., Rotation distance, triangulations and hyperbolic geometry, J. Amer. Math. Soc., Vol. 1, 647-681 (1988) · Zbl 0653.51017
[18] Sloane, N. J.A.; Plouffe, S., The Encyclopedia of Integer Sequences (1995), Academic Press: Academic Press New York · Zbl 0845.11001
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.