Reachability Is in DynFO
From MaRDI portal
Publication:4625654
DOI10.1145/3212685zbMATH Open1426.68107arXiv1502.07467OpenAlexW2998720137WikidataQ129333575 ScholiaQ129333575MaRDI QIDQ4625654
Author name not available (Why is that?)
Publication date: 25 February 2019
Published in: (Search for Journal in Brave)
Abstract: Patnaik and Immerman introduced the dynamic complexity class DynFO of database queries that can be maintained by first-order dynamic programs with the help of auxiliary relations under insertions and deletions of edges (Patnaik and Immerman 1997). This article confirms their conjecture that the Reachability query is in DynFO. As a byproduct it is shown that the rank of a matrix with small values can be maintained in DynFO(+,x). It is further shown that the (size of the) maximum matching of a graph can be maintained in non-uniform DynFO, another extension of DynFO, with non-uniform initialisation of the auxiliary relations.
Full work available at URL: https://arxiv.org/abs/1502.07467
No records found.
No records found.
This page was built for publication: Reachability Is in DynFO
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4625654)
