Navigating Forest Straight-Line Programs in Constant Time

DOI10.1007/978-3-030-59212-7_2MaRDI QIDQ6485914zbMATH OpenFDO

Authors Carl Philipp Reh, Kurt Sieber

Publication date 22 December 2022

Published in 1511.68105 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-030-59212-7_2

Mathematics Subject Classification ID

Data structures (68P05) Grammars and rewriting systems (68Q42)

Recommendations

• Complexity and approximation of the constrained forest problem
• Linear-time algorithms for tree root problems
• Linear-Time Algorithms for Tree Root Problems
• Optimal sublogarithmic time parallel algorithms on rooted forests
• scientific article; zbMATH DE number 1670677
• Near-linear time approximation schemes for Steiner tree and forest in low-dimensional spaces
• scientific article; zbMATH DE number 742977
• A General Approximation Technique for Constrained Forest Problems
• scientific article; zbMATH DE number 4173000
• Forest-like abstract Voronoi diagrams in linear time

Cited in

(3)

• Finding compact scheme forests in nested normal form is NP-hard
• Constant-time tree traversal and subtree equality check for grammar-compressed trees
• Constant delay traversal of grammar-compressed graphs with bounded rank

This page was built for publication: Navigating Forest Straight-Line Programs in Constant Time

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