Geodesic
Combinatorial structure and adjacency of vertices of polytope of $b$-factors
Izvestiâ vysših učebnyh zavedenij. Matematika, no. 6 (2014), pp. 56-69 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

In the present paper in terms of the graph theory we describe the structure and vertices adjacency criterion of $b$-factors polyhedron. The special attention is paid to nonintegral vertices. Results of the present paper, in particular, generalize properties of nonintegral vertices of TSP polyhedron, give vertices adjacency criterion of a transportation polytope.
Keywords: graph, polytope, polyhedron, $b$-factor, vertices adjacency of polyhedron. 
@article{IVM_2014_6_a5,
     author = {R. Yu. Simanchev},
     title = {Combinatorial structure and adjacency of vertices of polytope of $b$-factors},
     journal = {Izvesti\^a vys\v{s}ih u\v{c}ebnyh zavedenij. Matematika},
     pages = {56--69},
     year = {2014},
     number = {6},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/IVM_2014_6_a5/}
}
TY  - JOUR
AU  - R. Yu. Simanchev
TI  - Combinatorial structure and adjacency of vertices of polytope of $b$-factors
JO  - Izvestiâ vysših učebnyh zavedenij. Matematika
PY  - 2014
SP  - 56
EP  - 69
IS  - 6
UR  - http://geodesic.mathdoc.fr/item/IVM_2014_6_a5/
LA  - ru
ID  - IVM_2014_6_a5
ER  - 
%0 Journal Article
%A R. Yu. Simanchev
%T Combinatorial structure and adjacency of vertices of polytope of $b$-factors
%J Izvestiâ vysših učebnyh zavedenij. Matematika
%D 2014
%P 56-69
%N 6
%U http://geodesic.mathdoc.fr/item/IVM_2014_6_a5/
%G ru
%F IVM_2014_6_a5
R. Yu. Simanchev. Combinatorial structure and adjacency of vertices of polytope of $b$-factors. Izvestiâ vysših učebnyh zavedenij. Matematika, no. 6 (2014), pp. 56-69. http://geodesic.mathdoc.fr/item/IVM_2014_6_a5/

[1] Grötshel M., Holland O., “Solution of large-scale symmetric travelling salesman problems”, Math. Program. Ser. A, 51:2 (1991), 141–202 | DOI | MR

[2] Hausmann D., Adjacency on polytopes in combinatorial optimization, Mathematical Systems in Economics, 49, Meisenheim am Glan, Hain, 1980 | MR | Zbl

[3] Maksimenko A. N., “Ob affinnoi svodimosti kombinatornykh mnogogrannikov”, Dokl. RAN, 443:6 (2012), 661–663 | MR | Zbl

[4] Simanchev R. Yu., “Struktura netselochislennykh vershin relaksatsii mnogogrannika $k$-faktorov”, Matem. struktury i modelirovanie, 1998, no. 1, 20–26 | MR | Zbl

[5] Kravtsov M. K., Kravtsov V. M., Lukshin E. V., “O netselochislennykh vershinakh mnogogrannika trekhindeksnoi aksialnoi zadachi o naznacheniyakh”, Diskretn. matem., 13:2 (2001), 120–143 | DOI | MR | Zbl

[6] Kravtsov V. M., “Kharakterizatsiya tipov maksimalno netselochislennykh vershin mnogogrannika trekhindeksnoi aksialnoi zadachi o naznacheniyakh”, Izv. vuzov. Matem., 2006, no. 12, 65–68 | MR

[7] Padberg M., Rinaldi G., “Facet identification for the symmetric traveling salesman polytope”, Math. Program., 47 (1990), 219–257 | DOI | MR | Zbl

[8] Emelichev V. A., Kovalev M. M., Kravtsov M. K., Mnogogranniki, grafy, optimizatsiya, Nauka, M., 1981 | MR | Zbl

[9] Skhreiver A., Teoriya lineinogo i tselochislennogo programmirovaniya, v. 1, 2, Mir, M., 1991

[10] Padberg M. W., Rao M. R., “The travelling salesman problem and a class of polyhedra of diameter two”, Math. Program., 7 (1974), 32–45 | DOI | MR | Zbl

[11] Rao M. R., “Adjacency of the traveling salesman tours and $0$–$1$ vertices”, SIAM J. Appl. Math., 30:2 (1976), 191–198 | DOI | MR | Zbl