Dynamic planar graph isomorphism is maintainable in DynFO via FO formulas and polynomial auxiliary data.
Mix Barrington, Neil Immerman, and Howard Straubing
2 Pith papers cite this work. Polarity classification is still indexing.
2
Pith papers citing it
citation-role summary
background 1
citation-polarity summary
roles
background 1polarities
background 1representative citing papers
Presents constant-time CRCW PRAM algorithms for acyclic queries, semijoin algebra queries, and worst-case optimal joins that achieve work O(T^{1+ε}) for any ε>0 relative to optimal sequential time T.
citing papers explorer
-
Dynamic Planar Graph Isomorphism is in DynFO
Dynamic planar graph isomorphism is maintainable in DynFO via FO formulas and polynomial auxiliary data.
-
Work-Efficient Query Evaluation in Constant Time with PRAMs
Presents constant-time CRCW PRAM algorithms for acyclic queries, semijoin algebra queries, and worst-case optimal joins that achieve work O(T^{1+ε}) for any ε>0 relative to optimal sequential time T.