Improved approximation of the largest common subtree of two unordered trees of bounded height

DOI10.1016/J.IPL.2008.09.025zbMATH Open1191.68858OpenAlexW2076999762MaRDI QIDQ975557FDOQ975557

Authors: Tatsuya Akutsu, Daiji Fukagawa, Atsuhiro Takasu 

Publication date: 9 June 2010

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

Full work available at URL: https://doi.org/10.1016/j.ipl.2008.09.025

Recommendations

• On the complexity of finding a largest common subtree of bounded degree
• Approximation and parameterized algorithms for common subtrees and edit distance between unordered trees
• On the complexity of finding a largest common subtree of bounded degree
• On the approximation of largest common subtrees and largest common point sets
• Approximation and special cases of common subtrees and editing distance

zbMATH Keywords

approximation algorithmsedit distanceunordered treescommon subtrees

Mathematics Subject Classification ID

Approximation algorithms (68W25)

Cites Work

• Introduction to algorithms
• The Tree-to-Tree Correction Problem
• A survey on tree edit distance and related problems
• Some MAX SNP-hard results concerning unordered labeled trees
• An Optimal Decomposition Algorithm for Tree Edit Distance
• On the editing distance between unordered labeled trees
• A constrained edit distance between unordered labeled trees
• Approximation and special cases of common subtrees and editing distance

Cited In (3)

• Title not available (Why is that?)
• An algebraic view of the relation between largest common subtrees and smallest common supertrees
• Efficient exponential-time algorithms for edit distance between unordered trees

This page was built for publication: Improved approximation of the largest common subtree of two unordered trees of bounded height

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