We 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.
Mezzini, M. (2012). Fully dynamic algorithm for chordal graphs with O(1) query-time and O(n2) update-time. THEORETICAL COMPUTER SCIENCE, 445, 82-92 [10.1016/j.tcs.2012.05.002].
Fully dynamic algorithm for chordal graphs with O(1) query-time and O(n2) update-time
MEZZINI, MAURO
2012-01-01
Abstract
We 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.File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
