Show simple item record

Subgraph Complementation

dc.contributor.authorFomin, Fedor
dc.contributor.authorGolovach, Petr
dc.contributor.authorStrømme, Torstein J. F.
dc.contributor.authorThilikos, Dimitrios M.
dc.date.accessioned2021-02-10T12:59:25Z
dc.date.available2021-02-10T12:59:25Z
dc.date.created2020-10-14T12:36:06Z
dc.date.issued2020-02
dc.PublishedAlgorithmica. 2020, 82 (7), 1859-1880.en_US
dc.identifier.issn0178-4617
dc.identifier.urihttps://hdl.handle.net/11250/2727209
dc.description.abstractA 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.isoengen_US
dc.publisherSpringeren_US
dc.rightsNavngivelse 4.0 Internasjonal*
dc.rights.urihttp://creativecommons.org/licenses/by/4.0/deed.no*
dc.titleSubgraph Complementationen_US
dc.typeJournal articleen_US
dc.typePeer revieweden_US
dc.description.versionpublishedVersionen_US
dc.rights.holderCopyright The Author(s)en_US
cristin.ispublishedtrue
cristin.fulltextoriginal
cristin.qualitycode2
dc.identifier.doi10.1007/s00453-020-00677-8
dc.identifier.cristin1839516
dc.source.journalAlgorithmicaen_US
dc.source.4082en_US
dc.source.147en_US
dc.source.pagenumber1859-1880en_US
dc.identifier.citationAlgorithmica. 2020, 82 (7), 1859-1880.


Files in this item

Thumbnail
Name:
Fomin2020_Article_SubgraphComp ...
Size:
2.673Mb
Format:
PDF
Description:
PDF
View/Open

This item appears in the following Collection(s)

Show simple item record

Navngivelse 4.0 Internasjonal
Except where otherwise noted, this item's license is described as Navngivelse 4.0 Internasjonal