On the complexity of finding a largest common subtree of bounded degree

DOI10.1007/978-3-642-40164-0_4MaRDI QIDQ2842767zbMATH OpenOpenAlexFDO

Authors Tatsuya Akutsu, Avraham A. Melkman, Atsuhiro Takasu

Publication date 16 August 2013

Published in Fundamentals of Computation Theory (Search for Journal in Brave)

Full work available at URL http://hdl.handle.net/2433/203049

zbMATH Keywords

dynamic programmingparameterized complexitytree edit distanceunordered trees

Mathematics Subject Classification ID

Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Data structures (68P05) Analysis of algorithms and problem complexity (68Q25) Dynamic programming (90C39)

Recommendations

• On the complexity of finding a largest common subtree of bounded degree
• Improved approximation of the largest common subtree of two unordered trees of bounded height
• Faster algorithms for the maximum common subtree isomorphism problem
• On the approximation of largest common subtrees and largest common point sets
• Approximation and parameterized algorithms for common subtrees and edit distance between unordered trees

Cited in

(9)

• On the complexity of finding a largest common subtree of bounded degree
• An algebraic view of the relation between largest common subtrees and smallest common supertrees
• Enumeration of Maximum Common Subtree Isomorphisms with Polynomial-Delay
• On the Complexity of Extracting Subtree with Keeping Distinguishability
• About the largest subtree common to several X-trees
• scientific article; zbMATH DE number 1555958 (Why is no real title available?)
• Finding largest common embeddable subtrees
• Faster algorithms for the maximum common subtree isomorphism problem
• Improved approximation of the largest common subtree of two unordered trees of bounded height

This page was built for publication: On the complexity of finding a largest common subtree of bounded degree

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