Name
Abstract | ||
|---|---|---|
We consider the problem of subtree extraction with guarantee of preserving distinguishability. Given a query q and a tree T, evaluating q on T will output q(T) which is a set of nodes of T. For two nodes a and b in T, they can be distinguished by some query q in T, iff exactly one of them belongs to q(T). Then, given a tree T, a query class (mathcal {L}), and two disjoint node sets A and B of T, a subtree (Tu0027) of T is called preserving distinguishability of T, iff (1) (Tu0027) contains all nodes in (Acup B), (2) for any node pair ((a,b)in {Atimes B}), if a and b can be distinguished by some query in (mathcal {L}) in T, they can also be distinguished by some query (not necessarily the same one) in (mathcal {L}) in (Tu0027), and (3) for any node pair ((a,b)in {Atimes B}) and a query (qin mathcal {L}), if a and b can be distinguished by q in (Tu0027), they can also be distinguished by q in T. The subtree extraction problem considered by this paper is to determine whether there is a small enough subtree (Tu0027) of T, such that for query class (mathcal {L}) and node sets A and B, (Tu0027) preserves the distinguishability of T. In this paper, as an initial attempt of investigating this problem, fixing (mathcal {L}) to be a specific part of tree pattern queries (introduced later), the subtree extraction problem is shown to be NP-complete. |
Year | Venue | Field |
|---|---|---|
2016 | COCOA | Discrete mathematics,Combinatorics,Disjoint sets,Computer science,Tree (data structure),Computational complexity theory,Tree pattern |
DocType | Citations | PageRank |
Conference | 0 | 0.34 |
References | Authors | |
10 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Xianmin Liu | 1 | 12 | 5.00 |
| Zhipeng Cai | 2 | 1928 | 132.81 |
| Dongjing Miao | 3 | 18 | 9.91 |
| Jianzhong Li | 4 | 3196 | 304.46 |