Matching Subsequences in Trees

Philip Bille, Inge Li Gørtz

    Research output: Contribution to journalJournal articleResearchpeer-review


    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 languageEnglish
    JournalJournal of Discrete Algorithms
    Issue number3
    Pages (from-to)306-314
    Publication statusPublished - 2009


    • Subsequences
    • Tree matching
    • XML queries

    Fingerprint Dive into the research topics of 'Matching Subsequences in Trees'. Together they form a unique fingerprint.

    Cite this