This paper deals with the well known classes of threshold and difference graphs, both characterized by separators, i.e. node weight functions and thresholds. We design an efficient algorithm to find the minimum separator, and we show how to maintain minimum its value when the input (threshold or difference) graph is fully dynamic, i.e. edges/nodes are inserted/removed. Moreover, exploiting the data structure used for maintaining the minimality of the separator, we study the disjoint union and the join of two threshold graphs, showing that the resulting graphs are threshold signed graphs, i.e. a superclass of both threshold and difference graphs. Finally, we consider the complement operation on all the three introduced classes of graphs. All these operations produce in output the modified graph in terms of their separator and require time linear w.r.t. the number of different degrees. We observe that recomputing from scratch the separator would run either in linear (for threshold and difference graphs) or quadratic (for threshold signed graphs) time w.r.t. the number of nodes of the graph.

On dynamic threshold graphs and related classes / Calamoneri, Tiziana; Monti, Angelo; Petreschi, Rossella. - In: THEORETICAL COMPUTER SCIENCE. - ISSN 0304-3975. - STAMPA. - 718:(2018), pp. 46-57. [10.1016/j.tcs.2017.01.007]

On dynamic threshold graphs and related classes

Tiziana Calamoneri
;
Angelo Monti;Rossella Petreschi
2018

Abstract

This paper deals with the well known classes of threshold and difference graphs, both characterized by separators, i.e. node weight functions and thresholds. We design an efficient algorithm to find the minimum separator, and we show how to maintain minimum its value when the input (threshold or difference) graph is fully dynamic, i.e. edges/nodes are inserted/removed. Moreover, exploiting the data structure used for maintaining the minimality of the separator, we study the disjoint union and the join of two threshold graphs, showing that the resulting graphs are threshold signed graphs, i.e. a superclass of both threshold and difference graphs. Finally, we consider the complement operation on all the three introduced classes of graphs. All these operations produce in output the modified graph in terms of their separator and require time linear w.r.t. the number of different degrees. We observe that recomputing from scratch the separator would run either in linear (for threshold and difference graphs) or quadratic (for threshold signed graphs) time w.r.t. the number of nodes of the graph.
2018
Fully dynamic; graphsThreshold; graphsDifference; graphsChain
01 Pubblicazione su rivista::01a Articolo in rivista
On dynamic threshold graphs and related classes / Calamoneri, Tiziana; Monti, Angelo; Petreschi, Rossella. - In: THEORETICAL COMPUTER SCIENCE. - ISSN 0304-3975. - STAMPA. - 718:(2018), pp. 46-57. [10.1016/j.tcs.2017.01.007]
File allegati a questo prodotto
File Dimensione Formato  
Petreschi_dynamic_2018.pdf

accesso aperto

Tipologia: Documento in Pre-print (manoscritto inviato all'editore, precedente alla peer review)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 601.22 kB
Formato Adobe PDF
601.22 kB Adobe PDF
Petreschi_dynamic_2018.pdf

solo gestori archivio

Tipologia: Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 712.33 kB
Formato Unknown
712.33 kB Unknown   Contatta l'autore

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/11573/1104495
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 2
  • ???jsp.display-item.citation.isi??? 2
social impact