Dynamically mantaining minimal integral separator for Threshold and Difference Graphs
| Autor: | Rossella Petreschi, Angelo Monti, Tiziana Calamoneri |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2016 |
| Předmět: |
Dense graph
Fully dynamic graphs Threshold signed graphs 0102 computer and information sciences 02 engineering and technology Topology 01 natural sciences Threshold graphs Combinatorics Treewidth Chain graphs Difference graphs Graph operations Indifference graph Pathwidth 010201 computation theory & mathematics Chordal graph 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing Maximal independent set Cograph MathematicsofComputing_DISCRETEMATHEMATICS Mathematics |
| Zdroj: | WALCOM: Algorithms and Computation ISBN: 9783319301389 WALCOM |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|