On the Complexity of Extracting Subtree with Keeping Distinguishability

DOI10.1007/978-3-319-48749-6_17MaRDI QIDQ2958316zbMATH OpenOpenAlexFDO

Authors Xianmin Liu, Zhipeng Cai, Dongjing Miao, Jianzhong Li

Publication date 1 February 2017

Published in Combinatorial Optimization and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-48749-6_17

zbMATH Keywords

computational complexitydistinguishabilitysubtree extraction

Mathematics Subject Classification ID

Data structures (68P05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• The decision-tree complexity of element distinctness
• On the computational complexity of the rooted subtree prune and regraft distance
• Separating decision tree complexity from subcube partition complexity
• On the complexity of finding a largest common subtree of bounded degree
• On the complexity of finding a largest common subtree of bounded degree
• On subbetweennesses of trees: hardness, algorithms, and characterizations
• The complexity of subgraph isomorphism for classes of partial k-trees
• Tree-Depth and the Formula Complexity of Subgraph Isomorphism
• Distinguishing trees in linear time

Cites work

• Containment and equivalence for a fragment of XPath
• Efficient extraction of schemas for XML documents.
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 1950751 (Why is no real title available?)
• Information Extraction
• Learning \((k,l)\)-contextual tree languages for information extraction from web pages
• Ordered term tree languages which are polynomial time inductively inferable from positive data
• Tree pattern query minimization

Cited in

(3)

• Tree size reduction with keeping distinguishability
• On the computational complexity of the rooted subtree prune and regraft distance
• Losing Treewidth by Separating Subsets

This page was built for publication: On the Complexity of Extracting Subtree with Keeping Distinguishability

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