Anzeige
Erschienen in:
2011 | OriginalPaper | Buchkapitel
Faster Bit-Parallel Algorithms for Unordered Pseudo-tree Matching and Tree Homeomorphism
verfasst von : Yusaku Kaneta, Hiroki Arimura
Erschienen in: Combinatorial Algorithms
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
In this paper, we consider the unordered pseudo-tree matching problem, which is a problem of, given two unordered labeled trees
P
and
T
, finding all occurrences of
P
in
T
via such many-one embeddings that preserve node labels and parent-child relationship. This problem is closely related to tree pattern matching problem for XPath queries with child axis only. If
m
>
w
, we present an efficient algorithm that solves the problem in
$O(nm\ log(w)/w)$
time using
O
(
hm
/
w
+
m
log(
w
)/
w
) space and
O
(
m
log(
w
)) preprocessing on a unit-cost arithmetic RAM model with addition, where
m
is the number of nodes in
P
,
n
is the number of nodes in
T
,
h
is the height of
T
, and
w
is the word length. We also discuss a modification of our algorithm for the unordered tree homeomorphism problem, which corresponds to a tree pattern matching problem for XPath queries with descendant axis only.