A distance metric on binary trees using lattice-theoretic measures

DOI10.1016/0020-0190(90)90088-FMaRDI QIDQ910191zbMATH OpenFDO

Authors N. E. Zubov

Publication date 1990

Published in Information Processing Letters (Search for Journal in Brave)

zbMATH Keywords

binary treesdistance metricrotation lattice

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Data structures (68P05) Lattices (06B99)

Recommendations

• Distances between rooted trees
• The agreement metric for labeled binary trees
• An \(O(n \log n)\) time algorithm for computing the path-length distance between trees
• A metric for rooted trees with unlabeled vertices based on nested parentheses
• scientific article; zbMATH DE number 1113982

Cites work

• Enumerating, Ranking and Unranking Binary Trees
• Height on posets and graphs
• Metrics on partially ordered sets - a survey
• Metrics on spaces of finite trees
• On the upper bound on the rotation distance of binary trees
• Path length in the covering graph of a lattice
• The average height of binary trees and other simple trees

Cited in

(15)

• The pruning-grafting lattice of binary trees
• A tight bound on approximating arbitrary metrics by tree metrics
• An algorithm to compute the möbius function of the rotation lattice of binary trees
• Two shortest path metrics on well-formed parentheses strings
• The higher Stasheff‐Tamari posets
• Decision trees of algorithms and a semivaluation to measure their distance
• A metric for rooted trees with unlabeled vertices based on nested parentheses
• A tight bound on approximating arbitrary metrics by tree metrics
• On the rotation distance between binary trees
• Metrics on the multirubric lattice of a rubricator tree
• Binary trees equipped with semivaluations
• The phagocyte lattice of Dyck words
• Extremal distances for subtree transfer operations in binary trees
• Matchings In Three Catalan Lattices
• On the intercluster distance of a tree metric

This page was built for publication: A distance metric on binary trees using lattice-theoretic measures

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