Décomposition en matrices graphiques de matrices en { 0 , 1 , - 1 } : application à la résolution de programmes linéaires entiers

A. Quilliot

RAIRO - Operations Research - Recherche Opérationnelle (1993)

  • Volume: 27, Issue: 3, page 293-306
  • ISSN: 0399-0559

How to cite

top

Quilliot, A.. "Décomposition en matrices graphiques de matrices en $\lbrace 0, 1, -1\rbrace $ : application à la résolution de programmes linéaires entiers." RAIRO - Operations Research - Recherche Opérationnelle 27.3 (1993): 293-306. <http://eudml.org/doc/105062>.

@article{Quilliot1993,
author = {Quilliot, A.},
journal = {RAIRO - Operations Research - Recherche Opérationnelle},
keywords = {total unimodularity; network matrix; decomposition; linear integer programs},
language = {fre},
number = {3},
pages = {293-306},
publisher = {EDP-Sciences},
title = {Décomposition en matrices graphiques de matrices en $\lbrace 0, 1, -1\rbrace $ : application à la résolution de programmes linéaires entiers},
url = {http://eudml.org/doc/105062},
volume = {27},
year = {1993},
}

TY - JOUR
AU - Quilliot, A.
TI - Décomposition en matrices graphiques de matrices en $\lbrace 0, 1, -1\rbrace $ : application à la résolution de programmes linéaires entiers
JO - RAIRO - Operations Research - Recherche Opérationnelle
PY - 1993
PB - EDP-Sciences
VL - 27
IS - 3
SP - 293
EP - 306
LA - fre
KW - total unimodularity; network matrix; decomposition; linear integer programs
UR - http://eudml.org/doc/105062
ER -

References

top
  1. 1. L. AUSLANDER et H. TRENT, Incidence Matrices and Linear Graphs, J. of Maths and Mecha, 1959, 8, p. 827-835. Zbl0173.26402MR105371
  2. 2. L. AUSLANDER et H. TRENT, On the Realization of a Linear Graph Given its Algebraic Specification, J. of Acoustical Society of America, 33, p. 1183-1192. MR143198
  3. 3. P. BAPTISTE et J. FAVREL, Résolution de problèmes d'ordonnancements par graphes d'intervalles et treillis de galois. RAJ.R.O., 1984, 18, 4. Zbl0549.90054MR782439
  4. 4. J. F. BENDERS, Partitionning Procedure for Solving Mixed Variables Programming Problems. Numerische Mathematik, 1962, 4, p. 238-252. Zbl0109.38302MR147303
  5. 5. C. BERGE, Graphes et hypergraphes (chap. 5, 6), Dunod, 1974. Zbl0213.25702MR357173
  6. 6. R. BIXBY et W. CUNINGHAM, Converting Linear Programs to Network Problems, Maths of Operat. Research, 1980, 5, p. 321-357. Zbl0442.90095MR594849
  7. 7. M. CHEIN et M. HABIB, The Jump Number of Dags and Posets : an Introduction, Ann. of discrete math, 1980, 9, p. 189-194. Zbl0445.05048MR597371
  8. 8. V. CHVATAL, Linear programming, Freeman, N.Y., 1983. Zbl0537.90067MR717219
  9. 9. P. DUCHET, Problèmes de représentations et noyaux, Thèse d'État, Paris-VI, 1981. 
  10. 10. I. HELLER et A. HOFFMAN, On Unimodular Matrices, Pacific Journ. of Math., 1962, 72, p. 1321-1327. Zbl0115.01104MR150051
  11. 11. A. HOFFMAN et J. KRUSKAL, Integral Boundary Points of Convex Polyedra, in Linear Inequalities and Related Systems, H. KUHN and A. TUCKER éds., Princeton Univ. Press, 1956, p. 223-246. Zbl0072.37803MR85148
  12. 12. C. PAPADIMITRIOU et K. STEIGLITZ, Combinatorial optimization (chap. 3, 4, 5), Prentice Hall, 1982. Zbl0503.90060MR663728
  13. 13. A. SCHRIJVER, Theory of Linear and Integer Programming (chap. 19, 20), Wiley Interscience, 1986. Zbl0970.90052MR874114
  14. 14. P. SEYMOUR, Recognizing graphie matroids, Combinatorica, 1985, 1, p. 75-78. Zbl0501.05022MR602418
  15. 15. P. SEYMOUR, Decomposition of Regular Matroids, J.C.T. B., 1980, 28, p. 305-359. Zbl0443.05027MR579077
  16. 16. W. TUTTE, An Algorithm for Determining Whether a Given Binary Matroid is Graphic, Proc; of the American Math. Society, 1960, 11, p. 905-917. Zbl0097.38905MR117173

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.