Name
Title | ||
|---|---|---|
Fully Dynamically Maintaining Minimal Integral Separator for Threshold and Difference Graphs. |
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 show how to maintain minimum the value of the separator 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 handle the operations of disjoint union and join of two threshold graphs. |
Year | Venue | Field |
|---|---|---|
2016 | WALCOM | Graph operations,Discrete mathematics,Indifference graph,Combinatorics,Computer science,Chordal graph,Cograph,Treewidth,Pathwidth,Maximal independent set,Dense graph |
DocType | Citations | PageRank |
Conference | 0 | 0.34 |
References | Authors | |
2 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Tiziana Calamoneri | 1 | 511 | 46.80 |
| Angelo Monti | 2 | 671 | 46.93 |
| Rossella Petreschi | 3 | 374 | 47.10 |