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