2019/07/24 by Maneth, Sebastian, Peternek, Fabian · 1 citation
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1907.10444
We present a pointer-based data structure for constant time traversal of the edges of an edge-labeled (alphabet Σ) directed hypergraph (a graph where edges can be incident to more than two vertices, and the incident vertices are ordered) given as hyperedge-replacement grammar G. It is assumed that the grammar has a fixed rank κ (maximal number of vertices connected to a nonterminal hyperedge) and that each vertex of the represented graph is incident to at most one σ-edge per direction (σ∈ Σ). Precomputing the data structure needs O(|G||Σ|κr h) space and O(|G||Σ|κrh2) time, where h is the height of the derivation tree of G and r is the maximal rank of a terminal edge occurring in the grammar.