Publication: The Dynamic Complexity of Acyclic Hypergraph Homomorphisms
Date
Date
Date
2021
Conference or Workshop Item
Published version
Abstract
Abstract
Abstract
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 .
Metrics
Additional indexing
Creators (Authors)
Event Title
Event Title
Event Title
Graph-Theoretic Concepts in Computer Science - 47th International Workshop, WG 2021
Event Location
Event Location
Event Location
Warsaw
Event Start Date
Event Start Date
Event Start Date
2021-06-23
Event End Date
Event End Date
Event End Date
2021-06-25
Page range/Item number
Page range/Item number
Page range/Item number
232
Page end
Page end
Page end
244
Item Type
Item Type
Item Type
Conference or Workshop Item
In collections
Dewey Decimal Classifikation
Dewey Decimal Classifikation
Dewey Decimal Classifikation
Language
Language
Language
English
Date available
Date available
Date available
2024-12-02
Series Name
Series Name
Series Name
Lecture Notes in Computer Science
Number
Number
Number
12911
ISSN or e-ISSN
ISSN or e-ISSN
ISSN or e-ISSN
0302-9743
ISBN or e-ISBN
ISBN or e-ISBN
ISBN or e-ISBN
978-3-030-86837-6
OA Status
OA Status
OA Status
Green
Publisher DOI
Metrics
Green Open Access
Loading...
