dc.contributor.author | Fomin, Fedor | |
dc.contributor.author | Golovach, Petr | |
dc.contributor.author | Strømme, Torstein J. F. | |
dc.contributor.author | Thilikos, Dimitrios M. | |
dc.date.accessioned | 2021-02-10T12:59:25Z | |
dc.date.available | 2021-02-10T12:59:25Z | |
dc.date.created | 2020-10-14T12:36:06Z | |
dc.date.issued | 2020-02 | |
dc.Published | Algorithmica. 2020, 82 (7), 1859-1880. | en_US |
dc.identifier.issn | 0178-4617 | |
dc.identifier.uri | https://hdl.handle.net/11250/2727209 | |
dc.description.abstract | A subgraph complement of the graph G is a graph obtained from G by complementing all the edges in one of its induced subgraphs. We study the following algorithmic question: for a given graph G and graph class G, is there a subgraph complement of G which is in G? We show that this problem can be solved in polynomial time for various choices of the graphs class G, such as bipartite, d-degenerate, or cographs. We complement these results by proving that the problem is NP-complete when G is the class of regular graphs. | en_US |
dc.language.iso | eng | en_US |
dc.publisher | Springer | en_US |
dc.rights | Navngivelse 4.0 Internasjonal | * |
dc.rights.uri | http://creativecommons.org/licenses/by/4.0/deed.no | * |
dc.title | Subgraph Complementation | en_US |
dc.type | Journal article | en_US |
dc.type | Peer reviewed | en_US |
dc.description.version | publishedVersion | en_US |
dc.rights.holder | Copyright The Author(s) | en_US |
cristin.ispublished | true | |
cristin.fulltext | original | |
cristin.qualitycode | 2 | |
dc.identifier.doi | 10.1007/s00453-020-00677-8 | |
dc.identifier.cristin | 1839516 | |
dc.source.journal | Algorithmica | en_US |
dc.source.40 | 82 | en_US |
dc.source.14 | 7 | en_US |
dc.source.pagenumber | 1859-1880 | en_US |
dc.identifier.citation | Algorithmica. 2020, 82 (7), 1859-1880. | |