Partial complementation of graphs

Fedor Fomin 1 Petr Golovach 1 Torstein Strømme 1 Dimitrios M. Thilikos 2, 3
3 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : A partial complement of the graph G is a graph obtained from graph G by complementing edges of some of its induced subgraphs. We study the following algorithmic question: for a given graph G and graph class G, is it possible to partially complement G to G? We show that this problem can be solved in polynomial time for various classes of graphs like bipartite, degenerate, or cographs. We complement these results by proving that the problem is NP-complete when G is the class of r-regular graphs.
Type de document :
Communication dans un congrès
SWAT: Scandinavian Workshops on Algorithm Theory, Jun 2018, Malmö, Sweden. 16th Scandinavian Symposium and Workshops on Algorithm Theory, LIPIcs (101), pp.21:1--21:13, 2018, 〈10.4230/LIPIcs.SWAT.2018.21〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01890534
Contributeur : Dimitrios M. Thilikos <>
Soumis le : lundi 8 octobre 2018 - 16:53:15
Dernière modification le : jeudi 15 novembre 2018 - 20:26:05
Document(s) archivé(s) le : mercredi 9 janvier 2019 - 15:11:20

Fichier

xsoctratfg.pdf
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Collections

Citation

Fedor Fomin, Petr Golovach, Torstein Strømme, Dimitrios M. Thilikos. Partial complementation of graphs. SWAT: Scandinavian Workshops on Algorithm Theory, Jun 2018, Malmö, Sweden. 16th Scandinavian Symposium and Workshops on Algorithm Theory, LIPIcs (101), pp.21:1--21:13, 2018, 〈10.4230/LIPIcs.SWAT.2018.21〉. 〈lirmm-01890534〉

Partager

Métriques

Consultations de la notice

54

Téléchargements de fichiers

21