Navigation auf zora.uzh.ch
Vortmeier, Nils; Kokkinis, Ioannis (2021). The Dynamic Complexity of Acyclic Hypergraph Homomorphisms. In: Graph-Theoretic Concepts in Computer Science - 47th International Workshop, WG 2021, Warsaw, 23 June 2021 - 25 June 2021. Springer (Bücher), 232-244.
Finding a homomorphism from some hypergraph (or some relational structure) to another hypergraph is a fundamental problem in computer science. We show that an answer to this problem can be maintained under single-edge changes of , as long as it stays acyclic, in the framework of Patnaik and Immerman that uses updates expressed in first-order logic. If additionally also changes of are allowed, we show that it is unlikely that existence of homomorphisms can be maintained in .
| Item Type: | Conference or Workshop Item (Paper), refereed, original work |
|---|---|
| Communities & Collections: | 03 Faculty of Economics > Department of Informatics |
| Dewey Decimal Classification: | 000 Computer science, knowledge & systems |
| Scopus Subject Areas: | Physical Sciences > Theoretical Computer Science
Physical Sciences > General Computer Science |
| Language: | English |
| Event End Date: | 25 June 2021 |
| Deposited On: | 02 Dec 2024 15:18 |
| Last Modified: | 03 Dec 2024 21:00 |
| Publisher: | Springer (Bücher) |
| Series Name: | Lecture Notes in Computer Science |
| Number: | 12911 |
| ISSN: | 0302-9743 |
| ISBN: | 978-3-030-86837-6 |
| OA Status: | Green |
| Publisher DOI: | https://doi.org/10.1007/978-3-030-86838-3\_18 |
Vortmeier, Nils