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

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.
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].
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.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11590/138291
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 5
  • ???jsp.display-item.citation.isi??? 5
social impact