Finding smallest supertrees under minor containment

DOI10.1142/S0129054100000259MaRDI QIDQ5249050zbMATH OpenOpenAlexWikidataFDO

Authors N. Nishimura, Dimitrios M. Thilikos, Prabhakar Ragde

Publication date 29 April 2015

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/s0129054100000259

zbMATH Keywords

algorithmsminor containmentsupertrees

Mathematics Subject Classification ID

Trees (05C05) Graph minors (05C83) Graph algorithms (graph-theoretic aspects) (05C85) Data structures (68P05) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Publication:4944989
• Finding smallest supertrees
• Finding largest subtrees and smallest supertrees
• Maximum agreement and compatible supertrees
• A supertree method for rooted trees

Cites work

• Finding largest subtrees and smallest supertrees
• Graph minors. II. Algorithmic aspects of tree-width
• Maximum Agreement Subtree in a Set of Evolutionary Trees: Metrics and Efficient Algorithms
• On the agreement of many trees
• On the complexity of finding iso- and other morphisms for partial \(k\)- trees
• Ordered and Unordered Tree Inclusion
• The Parallel Complexity of Tree Embedding Problems

Cited in

(9)

• Finding largest subtrees and smallest supertrees
• An algebraic view of the relation between largest common subtrees and smallest common supertrees
• Constrained tree inclusion
• scientific article; zbMATH DE number 1420917 (Why is no real title available?)
• A 6-Approximation Algorithm for Computing Smallest Common AoN-Supertree with Application to the Reconstruction of Glycan Trees
• A survey on tree edit distance and related problems
• Finding smallest supertrees
• Dichotomies for tree minor containment with structural parameters
• Dichotomies for tree minor containment with structural parameters

This page was built for publication: Finding smallest supertrees under minor containment

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