Geodesic
Polytopes and connected subgraphs
Diskretnyj analiz i issledovanie operacij, Tome 21 (2014) no. 3, pp. 82-86.

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

The edges of the linear relaxation polytopes for quadratic Boolean programming problems are described. We found correspondence between the edges of such a polytope and connected subgraphs of the complete graph. Tab. 1, bibliogr. 14.
Keywords: combinatorial optimization, polyhedral cone, polytope, subgraph. 
@article{DA_2014_21_3_a8,
     author = {A. V. Seliverstov},
     title = {Polytopes and connected subgraphs},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {82--86},
     publisher = {mathdoc},
     volume = {21},
     number = {3},
     year = {2014},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2014_21_3_a8/}
}
TY  - JOUR
AU  - A. V. Seliverstov
TI  - Polytopes and connected subgraphs
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2014
SP  - 82
EP  - 86
VL  - 21
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2014_21_3_a8/
LA  - ru
ID  - DA_2014_21_3_a8
ER  - 
%0 Journal Article
%A A. V. Seliverstov
%T Polytopes and connected subgraphs
%J Diskretnyj analiz i issledovanie operacij
%D 2014
%P 82-86
%V 21
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2014_21_3_a8/
%G ru
%F DA_2014_21_3_a8
A. V. Seliverstov. Polytopes and connected subgraphs. Diskretnyj analiz i issledovanie operacij, Tome 21 (2014) no. 3, pp. 82-86. http://geodesic.mathdoc.fr/item/DA_2014_21_3_a8/

[1] Arutyunov A. V., “Two problems of the theory of quadratic maps”, Funct. Anal. Appl., 46:3 (2012), 225–227 | DOI | DOI | MR | Zbl

[2] Vladimirov A. A., “Non-crossing matchings”, Probl. Inf. Transmission, 49:1 (2013), 54–57 | DOI | Zbl

[3] Voblyi V. A., “Ob odnoi formule dlya chisla pomechennykh svyaznykh grafov”, Diskret. analiz i issled. operatsii, 19:4 (2012), 48–59 | MR

[4] Gorbunov K. Yu., Lyubetsky V. A., “The tree nearest on average to a given set of trees”, Probl. Inf. Transmission, 47:3 (2011), 274–288 | DOI | MR | Zbl

[5] Gorbunov K. Yu., Seliverstov A. V., Lyubetsky V. A., “Geometric relationship between parallel hyperplanes, quadrics, and vertices of a hypercube”, Prob. Inf. Transmission, 48:2 (2012), 185–192 | DOI | Zbl

[6] Erzin A. I., Plotnikov R. V., Shamardin Yu. V., “On some polynomially solvable cases and approximate algorithms in the optimal communication tree construction problem”, J. Appl. Industr. Math., 7:2 (2013), 142–152 | MR

[7] Maksimenko A. N., “$k$-Smezhnostnye grani buleva kvadratichnogo mnogogrannika”, Fundament. i prikl. matematika, 18:2 (2013), 95–103

[8] Seliverstov A. V., “Monomials in quadratic forms”, J. Appl. Industr. Math., 7:3 (2013), 431–434 | DOI | MR

[9] Stetsyuk P. I., Zolotykh N. Yu., “Binarnyi kvadratichnyi mnogogrannik i ego approksimatsii”, Zhurn. obchisl. ta prikl. matematiki, 2010, no. 2, 139–149

[10] Shlyk V. A., “O vershinakh glavnogo mnogogrannika Gomori”, Dokl. NAN Belarusi, 55:5 (2011), 14–17 | MR | Zbl

[11] Shlyk V. A., “Opornye vershiny glavnogo mnogogrannika Gomori”, Vestn. Belorus. gos. un-ta. Ser. 1. Fizika. Matematika. Informatika, 2012, no. 1, 49–54 | MR

[12] Avis D., Fukuda K., “A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra”, Discrete Comput. Geom., 8:1 (1992), 295–313 | DOI | MR | Zbl

[13] Conrad J. M., Gomes C. P., van Hoeve W.-J., Sabharwal A., Suter J. F., “Wildlife corridors as a connected subgraph problem”, J. Environ. Econ. Manage., 63:1 (2012), 1–18 | DOI | Zbl

[14] Padberg M., “The boolean quadric polytope: some characteristics, facets and relatives”, Math. Program., 45:1–3 (1989), 139–172 | DOI | MR | Zbl