On the Complexity of Reinforcement in Graphs
Nader Jafari Rad
Discussiones Mathematicae Graph Theory, Tome 36 (2016), p. 877-887 / Harvested from The Polish Digital Mathematics Library
Access to full text
Full (PDF)

We show that the decision problem for p-reinforcement, p-total rein- forcement, total restrained reinforcement, and k-rainbow reinforcement are NP-hard for bipartite graphs.

Publié le : 2016-01-01
EUDML-ID : urn:eudml:doc:287069 
@article{bwmeta1.element.doi-10_7151_dmgt_1898,
     author = {Nader Jafari Rad},
     title = {On the Complexity of Reinforcement in Graphs},
     journal = {Discussiones Mathematicae Graph Theory},
     volume = {36},
     year = {2016},
     pages = {877-887},
     zbl = {1350.05126},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_7151_dmgt_1898}
}

Nader Jafari Rad. On the Complexity of Reinforcement in Graphs. Discussiones Mathematicae Graph Theory, Tome 36 (2016) pp. 877-887. http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_7151_dmgt_1898/