|
This article is cited in 33 scientific papers (total in 33 papers)
On the Complexity of Some Problems Related to Graph Extensions
M. B. Abrosimov Saratov State University named after N. G. Chernyshevsky
Abstract:
The computational complexity of problems related to the construction of $k$-extensions of graphs is studied. It is proved that the problems of recognizing vertex and edge $k$-extensions are NP-complete. The complexity of recognizing irreducible, minimal, and exact vertex and edge $k$-extensions is considered.
Keywords:
extension of graphs, vertex and edge $k$-extension, minimal $k$-extension, irreducible $k$-extension, exact $k$-extension, NP problem, NP-complete problem, fault tolerance.
Received: 10.01.2009 Revised: 13.02.2010
Citation:
M. B. Abrosimov, “On the Complexity of Some Problems Related to Graph Extensions”, Mat. Zametki, 88:5 (2010), 643–650; Math. Notes, 88:5 (2010), 619–625
Linking options:
https://www.mathnet.ru/eng/mzm8403https://doi.org/10.4213/mzm8403 https://www.mathnet.ru/eng/mzm/v88/i5/p643
|
|