Geodesic
On 2-neighborly polytopes and the Gale construction
Modelirovanie i analiz informacionnyh sistem, Tome 16 (2009) no. 2, pp. 5-20.

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

The Gale construction of 2-neighborly polytopes is investigated.
Keywords: 2-neighborly polytope, probability, density of a polytopal graph, intractability.
Mots-clés : Gale construction 
@article{MAIS_2009_16_2_a0,
     author = {A. G. Brodskiy},
     title = {On 2-neighborly polytopes and the {Gale} construction},
     journal = {Modelirovanie i analiz informacionnyh sistem},
     pages = {5--20},
     publisher = {mathdoc},
     volume = {16},
     number = {2},
     year = {2009},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MAIS_2009_16_2_a0/}
}
TY  - JOUR
AU  - A. G. Brodskiy
TI  - On 2-neighborly polytopes and the Gale construction
JO  - Modelirovanie i analiz informacionnyh sistem
PY  - 2009
SP  - 5
EP  - 20
VL  - 16
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MAIS_2009_16_2_a0/
LA  - ru
ID  - MAIS_2009_16_2_a0
ER  - 
%0 Journal Article
%A A. G. Brodskiy
%T On 2-neighborly polytopes and the Gale construction
%J Modelirovanie i analiz informacionnyh sistem
%D 2009
%P 5-20
%V 16
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MAIS_2009_16_2_a0/
%G ru
%F MAIS_2009_16_2_a0
A. G. Brodskiy. On 2-neighborly polytopes and the Gale construction. Modelirovanie i analiz informacionnyh sistem, Tome 16 (2009) no. 2, pp. 5-20. http://geodesic.mathdoc.fr/item/MAIS_2009_16_2_a0/

[1] Yu. A. Belov, “O plotnosti grafa matroida”, Modeli issledovaniya operatsii v vychislitelnykh sistemakh, YarGU, Yaroslavl, 1985, 95–100

[2] M. M. Beloshevskii, “Mnogogrannik zadachi o maksimalnom razreze”, Modeli i algoritmy matematicheskogo obespecheniya EVM, YarGU, Yaroslavl, 1986, 12–20

[3] V. A. Bondarenko, “Sosednie vershiny mnogogrannikov, porozhdaemykh matroidami”, Voprosy teorii grupp i gomologicheskoi algebry, YarGU, Yaroslavl, 1982, 66–68 | MR

[4] V. A. Bondarenko, “Nepolinomialnaya nizhnyaya otsenka slozhnosti zadachi kommivoyazhera v odnom klasse algoritmov”, Avtomatika i telemekhanika, 1983, no. 9, 45–50 | MR | Zbl

[5] V. A. Bondarenko, E. V. Shunikova, “Obobschennye perestanovochnye mnogogranniki i svoistva algoritmov sortirovki”, Modeli issledovaniya operatsii v vychislitelnykh sistemakh, YarGU, Yaroslavl, 1985, 105–113

[6] V. A. Bondarenko, “Nepolinomialnye nizhnie otsenki slozhnosti optimizatsionnykh zadach o klike i vershinnom pokrytii v klasse pryamykh algoritmov”, Kombinatorno-algebraicheskie metody v prikladnoi matematike, GGU, Gorkii, 1985, 59–65 | MR

[7] V. A. Bondarenko, “Eksponentsialnost plotnosti grafa mnogogrannika zadachi o trekhmernom sochetanii”, Tezisy 7-i Vsesoyuznoi konferentsii «Problemy teoreticheskoi kibernetiki», IGU, Irkutsk, 1985, 29

[8] V. A. Bondarenko, “Otsenki slozhnosti zadach kombinatornoi optimizatsii v odnom klasse algoritmov”, Dokl. AN SSSR, 328:1 (1993), 22–24 | MR | Zbl

[9] V. A. Bondarenko, Poliedralnye grafy i slozhnost v kombinatornoi optimizatsii, YarGU, Yaroslavl, 1995, 126 pp.

[10] V. A. Bondarenko, “Poliedralnye grafy i slozhnost zadach kombinatornoi optimizatsii”, Matematika v Yaroslavskom universitete, YarGU, Yaroslavl, 1995, 31–42

[11] V. A. Bondarenko, A. G. Brodskii, “O sluchainykh 2-smezhnostnykh 0/1-mnogogrannikakh”, Diskretnaya matematika, 20:1 (2008), 64–69 | MR

[12] V. A. Bondarenko, A. N. Maksimenko, Geometricheskie konstruktsii i slozhnost v kombinatornoi optimizatsii, Izd-vo LKI, M., 2008, 184 pp.

[13] A. Brënsted, Vvedenie v teoriyu vypuklykh mnogogrannikov, Mir, M., 1988, 240 pp. | MR

[14] S. N. Greshnev, “Mnogogrannik zadachi o $m$-vershinnom podgrafe polnogo grafa”, Zhurnal vychislitelnoi matematiki i matematicheskoi fiziki, 24:5 (1984), 790–793 | MR | Zbl

[15] V. A. Emelichev, M. M. Kovalev, M. K. Kravtsov, Mnogogranniki, grafy, optimizatsiya (kombinatornaya teoriya mnogogrannikov), Nauka, M., 1981, 344 pp. | MR

[16] A. N. Maksimenko, “Nizhnyaya otsenka plotnosti grafa mnogogrannika zadachi o parosochetaniyakh”, Sovremennye problemy matematiki i informatiki, 2001, no. 4, 157–161

[17] A. N. Maksimenko, “Svodimost zadach diskretnoi optimizatsii i sootnoshenie plotnostei ikh poliedralnykh grafov”, Modelirovanie i analiz informatsionnykh sistem, 10:2 (2003), 3–10 | MR

[18] A. N. Maksimenko, “Mnogogrannik zadachi o ryukzake”, Voprosy teorii grupp i gomologicheskoi algebry, YarGU, Yaroslavl, 2003, 163–172

[19] A. N. Maksimenko, “Kombinatornye svoistva mnogogrannika zadachi o kratchaishem puti”, Zhurnal vychislitelnoi matematiki i matematicheskoi fiziki, 44:9 (2004), 1693–1696 | MR | Zbl

[20] C. Caratheodory, “Ueber den Variabilitatsbereich der Koeffizienten von Potenzreihen, die gegebene Werte nicht annehmen”, Math. Ann., 64 (1907), 12–17 | DOI | MR

[21] D. Gale, “Neighboring vertices on a convex polyhedron”, Linear inequalities and related systems, eds. H. W. Kuhn, A. W. Tucker, Princeton University Press, Princeton, New Jersey, 1956 ; D. Geil, “Sosednie vershiny na vypuklom mnogogrannike”, Lineinye neravenstva i smezhnye voprosy, eds. G. U. Kuna, A. U. Takkera, IL, M., 1959, 355–362 | MR

[22] G. M. Ziegler, Lectures on polytopes, Springer, N.Y., 1995, 370 pp. | MR

[23] F. Barahona, A. R. Mahjoub, “On the cut polytope”, Mathematical Programming, 36 (1986), 157–173 | DOI | MR | Zbl