Geodesic
On the Complexity of Some Problems Related to Graph Extensions
Matematičeskie zametki, Tome 88 (2010) no. 5, pp. 643-650

Voir la notice de l'article provenant de la source Math-Net.Ru

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. 
@article{MZM_2010_88_5_a0,
     author = {M. B. Abrosimov},
     title = {On the {Complexity} of {Some} {Problems} {Related} to {Graph} {Extensions}},
     journal = {Matemati\v{c}eskie zametki},
     pages = {643--650},
     publisher = {mathdoc},
     volume = {88},
     number = {5},
     year = {2010},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MZM_2010_88_5_a0/}
}
TY  - JOUR
AU  - M. B. Abrosimov
TI  - On the Complexity of Some Problems Related to Graph Extensions
JO  - Matematičeskie zametki
PY  - 2010
SP  - 643
EP  - 650
VL  - 88
IS  - 5
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MZM_2010_88_5_a0/
LA  - ru
ID  - MZM_2010_88_5_a0
ER  - 
%0 Journal Article
%A M. B. Abrosimov
%T On the Complexity of Some Problems Related to Graph Extensions
%J Matematičeskie zametki
%D 2010
%P 643-650
%V 88
%N 5
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MZM_2010_88_5_a0/
%G ru
%F MZM_2010_88_5_a0
M. B. Abrosimov. On the Complexity of Some Problems Related to Graph Extensions. Matematičeskie zametki, Tome 88 (2010) no. 5, pp. 643-650. http://geodesic.mathdoc.fr/item/MZM_2010_88_5_a0/