This article is cited 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.

UDC: 519.17

Received: 10.01.2009
Revised: 13.02.2010

DOI: 10.4213/mzm8403

 English version: Mathematical Notes, 2010, 88:5, 619–625

Bibliographic databases:

• 
• 
•