Matching Subsequences in Trees

Philip Bille; Inge Li Gørtz

doi:10.1016/j.jda.2008.11.005

Matching Subsequences in Trees

Philip Bille
, Inge Li Gørtz

IT University of Copenhagen

Research output: Contribution to journal › Journal article › Research › peer-review

Abstract

Given two rooted, labeled trees P and T the tree path subsequence problem is to determine which paths in P are subsequences of which paths in T. Here a path begins at the root and ends at a leaf. In this paper we propose this problem as a useful query primitive for XML data, and provide new algorithms improving the previously best known time and space bounds.

Original language	English
Journal	Journal of Discrete Algorithms
Volume	7
Issue number	3
Pages (from-to)	306-314
ISSN	1570-8667
DOIs	https://doi.org/10.1016/j.jda.2008.11.005
Publication status	Published - 2009

Keywords

Subsequences
Tree matching
XML queries

Access to Document

10.1016/j.jda.2008.11.005

OpenUrl availability

Check availability in DTU Findit

Cite this

@article{c5caed5dd3a64cbfbe1ab9adfa9e1f2c,

title = "Matching Subsequences in Trees",

abstract = "Given two rooted, labeled trees P and T the tree path subsequence problem is to determine which paths in P are subsequences of which paths in T. Here a path begins at the root and ends at a leaf. In this paper we propose this problem as a useful query primitive for XML data, and provide new algorithms improving the previously best known time and space bounds.",

keywords = "Subsequences, Tree matching, XML queries",

author = "Philip Bille and G{\o}rtz, \{Inge Li\}",

year = "2009",

doi = "10.1016/j.jda.2008.11.005",

language = "English",

volume = "7",

pages = "306--314",

journal = "Journal of Discrete Algorithms",

issn = "1570-8667",

publisher = "Elsevier",

number = "3",

}

TY - JOUR

T1 - Matching Subsequences in Trees

AU - Bille, Philip

AU - Gørtz, Inge Li

PY - 2009

Y1 - 2009

N2 - Given two rooted, labeled trees P and T the tree path subsequence problem is to determine which paths in P are subsequences of which paths in T. Here a path begins at the root and ends at a leaf. In this paper we propose this problem as a useful query primitive for XML data, and provide new algorithms improving the previously best known time and space bounds.

AB - Given two rooted, labeled trees P and T the tree path subsequence problem is to determine which paths in P are subsequences of which paths in T. Here a path begins at the root and ends at a leaf. In this paper we propose this problem as a useful query primitive for XML data, and provide new algorithms improving the previously best known time and space bounds.

KW - Subsequences

KW - Tree matching

KW - XML queries

U2 - 10.1016/j.jda.2008.11.005

DO - 10.1016/j.jda.2008.11.005

M3 - Journal article

SN - 1570-8667

VL - 7

SP - 306

EP - 314

JO - Journal of Discrete Algorithms

JF - Journal of Discrete Algorithms

IS - 3

ER -

Matching Subsequences in Trees

Abstract

Keywords

Access to Document

OpenUrl availability

Fingerprint

Cite this