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/

[1] J. P. Hayes, “A graph model for fault-tolerant computing systems”, IEEE Trans. Computers, C-25, no. 9, 1976, 875–884 | MR | Zbl

[2] F. Harary, J. P. Hayes, “Edge fault tolerance in graphs”, Networks, 23, no. 2, 1993, 135–142 | MR | Zbl

[3] F. Harary, J. P. Hayes, “Node fault tolerance in graphs”, Networks, 27, no. 1, 1996, 19–23 | MR | Zbl

[4] A. M. Bogomolov, V. N. Salii, Algebraicheskie osnovy teorii diskretnykh sistem, Nauka, M., 1997 | MR | Zbl

[5] M. Geri, D. Dzhonson, Vychislitelnye mashiny i trudnoreshaemye zadachi, Mir, M., 1982 | MR | Zbl

[6] Kh. Papadimitriu, K. Staiglits, Kombinatornaya optimizatsiya. Algoritmy i slozhnost, Mir, M., 1985 | MR | Zbl

[7] M. B. Abrosimov, “Minimalnye rasshireniya grafov”, Novye informatsionnye tekhnologii v issledovanii diskretnykh struktur, TNTs SO RAN “Spektr”, Tomsk, 2000, 59–64

[8] V. N. Salii, “Dokazatelstva s nulevym razglasheniem v zadachakh o rasshireniyakh grafov”, Vestn. Tomsk. gos. un-ta. Prilozhenie, no. 6, 2003, 63–65

[9] M. B. Abrosimov, “Minimalnye rasshireniya tranzitivnykh turnirov”, Vestn. Tomsk. gos. un-ta. Prilozhenie, no. 17, 2006, 187–190

[10] M. B. Abrosimov, “Minimalnye rasshireniya dopolnenii grafov”, Teoreticheskie problemy informatiki i ee prilozhenii, Vyp. 4, SGU, Saratov, 2001, 11–19

[11] M. B. Abrosimov, “Nekotorye voprosy o minimalnykh rasshireniyakh grafov”, Izv. Sarat. un-ta. Ser. Matematika. Mekhanika. Informatika, 6, 2006, 86–91