Computing approximate tree edit distance using relaxation labeling
Pattern Recognition LettersPublished 4 February 2003
Andrea Torsello, Edwin R. Hancock
Citations68
SJR quartileQ1
SJR score1.00
SNIP1.43
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
This paper shows that any tree obtained with a sequence of cut operations is a subtree of the transitive closure of the original tree, and shows that the necessary condition for any subtree to be a solution can be reduced to a clique problem in a derived structure.
Abstract
This paper presents a new method for computing the tree edit distance problem with uniform edit cost. We commence by showing that any tree obtained with a sequence of cut operations is a subtree of the transitive closure of the original tree, we show that the necessary condition for any subtree to be a solution can be reduced to a clique problem in a derived structure. Using this idea we transform the problem of computing tree edit distance into a series of maximum weight clique problems. We, then use relaxation labeling to find an approximation to the tree edit distance.
Keywords
Computer Science
SIAM Journal on ComputingSimple Fast Algorithms for the Editing Distance between Trees and Related Problems
1,275 Citations1989Kaizhong Zhang, Dennis Shasha
Algorithms are designed to answer the following kinds of questions about trees: what is the distance between two trees, and the analogous question for prunings as for subtrees.
Journal of the ACMThe Tree-to-Tree Correction Problem
856 Citations1979Kuo‐Chung Tai
An algorithm is presented which solves the problem of determining the distance from T to T' as measured by the mlmmum cost sequence of edit operaUons needed to transform T into T'.
International Journal of Computer VisionShock Graphs and Shape Matching
762 Citations1999Kaleem Siddiqi, Ali Shokoufandeh +2 more
A novel tree matching algorithm is introduced which finds the best set of corresponding nodes between two shock trees in polynomial time and is demonstrated under articulation, occlusion, and moderate changes in viewpoint.
Canadian Journal of MathematicsMaxima for Graphs and a New Proof of a Theorem of Turán
728 Citations1965T. S. Motzkin, E. G. Straus
IEEE Transactions on Pattern Analysis and Machine IntelligenceMatching hierarchical structures using association graphs
394 Citations1999Marcello Pelillo, Kaleem Siddiqi +1 more
It is proved that, in the new formulation, there is a one-to-one correspondence between maximal cliques and maximal subtree isomorphisms, which allows the tree matching problem to be cast as an indefinite quadratic program using the Motzkin-Straus theorem.
IEEE Transactions on Systems Man and CyberneticsError-Correcting Isomorphisms of Attributed Relational Graphs for Pattern Analysis
325 Citations1979Wen‐Hsiang Tsai, King‐Sun Fu
The pattern deformational model proposed by Tsai and Fu is extended so that numerical attributes and probability or density distributions can be introduced into primitives and relations in a nonhierarchical relational graph.
Information Processing LettersOn the editing distance between unordered labeled trees
317 Citations1992Kaizhong Zhang, Rick Statman +1 more
This paper gives efficient polynomial-time algorithms for the case when one tree is a string or has a bounded number of leaves and shows that the problem is NP-complete even for binary trees having a label alphabet of size two.
AlgorithmicaA constrained edit distance between unordered labeled trees
189 Citations1996Kaizhong Zhang
This paper considers the problem of computing a constrained edit distance between unordered labeled trees and presents dynamic programming algorithms solving these problems in sequential timeO(|T1|×|T2|×(deg (T1)+deg(T2)× log2(deg( t2));)
IEEE Transactions on Pattern Analysis and Machine IntelligenceAn Image Understanding System Using Attributed Symbolic Representation and Inexact Graph-Matching
174 Citations1986M. A. Eshera, King‐Sun Fu
Mathematics of Operations ResearchContinuous Characterizations of the Maximum Clique Problem
160 Citations1997L. Gibbons, Donald W. Hearn +2 more
The Motzkin-Strauss QP is characterized, revealing interesting underlying discrete structures, and its properties are investigated, which are polynomial time verifiable.
IEEE Transactions on Neural NetworksApproximating the maximum weight clique using replicator dynamics
110 Citations2000Volker Stix, Marcello Pelillo +1 more
A parallel, distributed heuristic for approximating the maximum weight clique problem based on dynamics principles developed and studied in various branches of mathematical biology, and theoretical results which guarantee that the solutions provided by the clique finding replicator network are actually the ones being sought.
Journal of Mathematical Imaging and VisionThe Dynamics of Nonlinear Relaxation Labeling Processes
108 Citations1997Marcello Pelillo
It is shown that, when a certain symmetry condition is met, the algorithm possesses a Liapunov function which turns out to be a well-known consistency measure, which follows almost immediately from a powerful result of Baum and Eagon developed in the context of Markov chain theory.
Pattern Recognition LettersMean and maximum common subgraph of two graphs
52 Citations2000Horst Bunke, Abraham Kandel
It will be shown that under a particular set of cost functions for any two graphs, g and g', a maximum common subgraph is a mean and any subgraph of g or g' that contains amaximum common sub graph is a means as well.
The approximate graph matching problem
23 Citations2002J.T.L. Wang, Kaizhong Zhang +1 more
It is shown that no efficient algorithm can solve either variant of the approximate graph matching (AGM) problem, unless P=NP, and a polynomial-time approximation algorithm is given to solve this problem.
A probabilistic framework for graph clustering
18 Citations2005Bin Luo, Antonio Robles‐Kelly +3 more
A probabilistic framework for graph clustering is described from a set of pairwise distances between graph structures and an EM-like algorithm for clustering the graphs is presented by iteratively updating the elements of the affinity matrix.