Fully dynamic algorithm for chordal graphs with O(1) query-time and O(n2) update-time

AbstractWe propose dynamic algorithms and data structures for chordal graphs supporting the following operation: determine if an edge can be added or removed from the graph while preserving the chordality in O(1) time. We show that the complexity of the algorithms for updating the data structures when an edge is actually inserted or deleted is O(n2) where n is the number of vertices of the graph