Matching Subsequences in Trees

DOI10.1007/11758471_25zbMATH Open1183.68210arXivcs/0512061OpenAlexW2152448425MaRDI QIDQ3434561

Philip Bille, Inge Li Gørtz

Publication date: 2 May 2007

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/cs/0512061

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Data structures (68P05)

This page was built for publication: Matching Subsequences in Trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3434561)