Polytope des independants d'un graphe serie-parallele |
| |
| Authors: | Mouloud Boulala Jean-Pierre Uhry |
| |
| Affiliation: | Attaché CNRS, I.M.A.G., B.P. 53X, 38041 Grenoble Cédex, France |
| |
| Abstract: | A graph is said to be serie-parallel if it doesn't contain an homeomorph to K4. The aim of the paper is the demonstration of Chvatal's conjecture on the polytope of independent set of vertices in such graphs. This is done classically by using LP-duality, the algorithm for constructing the primal-dual solution having the nice property to be linear in the number of vertices. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
