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. |
Year | DOI | Venue |
---|---|---|
2018 | 10.1016/j.tcs.2017.01.007 | Theoretical Computer Science |
Keywords | Field | DocType |
Fully dynamic graphs,Threshold graphs,Difference graphs,Chain graphs,Threshold signed graphs,Graph operations | Discrete mathematics,Indifference graph,Combinatorics,Chordal graph,Graph product,Cograph,Pathwidth,1-planar graph,Mathematics,Split graph,Maximal independent set | Journal |
Volume | ISSN | Citations |
718 | 0304-3975 | 0 |
PageRank | References | Authors |
0.34 | 6 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Tiziana Calamoneri | 1 | 511 | 46.80 |
Angelo Monti | 2 | 671 | 46.93 |
Rossella Petreschi | 3 | 374 | 47.10 |