Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6875575 | Theoretical Computer Science | 2018 | 12 Pages |
Abstract
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Tiziana Calamoneri, Angelo Monti, Rossella Petreschi,