Y. Itokawa, J. Miyoshi, M. Wada, and T. Uchida (Japan)
Succinct data structures, graph algorithms, two-terminal series parallel graphs, path search problem
Two-terminal series parallel (TTSP) graphs are used as data models in applications for electric networks and scheduling problems. A TTSP graph with an efficient data structure enables us to design efficient strategies for solving such problems. In 2005, Ferragina et al. presented an xbw repre sentation and an xbw transform for an edge-labeled ordered tree, which is a data model of tree-structured data such as Web pages. First, we give a novel succinct representation of a TTSP graph as a sequence of xbw representations of ordered trees. Second, we present a linear time algorithm as a succinct data transform of a TTSP graph. Third, we present an efficient path search algorithm, which uses a succinct representation of a given TTSP graphs as its data structure, for finding all occurrences of paths of a given string. Finally, we report preliminary experimental results that demonstrate the performance of our algorithms.
Important Links:
Go Back
