Matching Subsequences in Trees

Philip Bille, Inge Li Gørtz

    Research output: Contribution to journalJournal articleResearchpeer-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 languageEnglish
    JournalJournal of Discrete Algorithms
    Volume7
    Issue number3
    Pages (from-to)306-314
    ISSN1570-8667
    DOIs
    Publication statusPublished - 2009

    Keywords

    • Subsequences
    • Tree matching
    • XML queries

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

    Cite this