POLYTOPE OF INDEPENDENT SETS OF SERIES-PARALLEL GRAPH

被引：37

作者：

BOULALA, M

UHRY, JP

机构：

[1] Attaché CNRS, I.M.A.G., 38041 Grenoble Cédex

来源：

DISCRETE MATHEMATICS | 1979年 / 27卷 / 03期

关键词：

D O I：

10.1016/0012-365X(79)90160-2

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

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. © 1979.

引用

页码：225 / 243

页数：19

共 13 条

[1] CERTAIN POLYTOPES ASSOCIATED WITH GRAPHS [J].

CHVATAL, V .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1975, 18 (02) :138-154

[2]

Chvatal V., 1973, Discrete Mathematics, V4, P305, DOI 10.1016/0012-365X(73)90167-2

[3]

CLAMCY M, 1977, THESIS STANFORD U

[4] TOPOLOGY OF SERIES-PARALLEL NETWORKS [J].

DUFFIN, RJ .

JOURNAL OF MATHEMATICAL ANALYSIS AND APPLICATIONS, 1965, 10 (02) :303-&

[5]

Nemhauser G. L., 1974, Mathematical Programming, V6, P48, DOI 10.1007/BF01580222

[6] VERTEX PACKINGS - STRUCTURAL-PROPERTIES AND ALGORITHMS [J].

NEMHAUSER, GL ;

TROTTER, LE .

MATHEMATICAL PROGRAMMING, 1975, 8 (02) :232-248

[7]

Padberg M., 1977, ANN DISCRETE MATH, V1, P421

[8]

Padberg M. W., 1973, Mathematical Programming, V5, P199, DOI 10.1007/BF01580121

[9]

Peled UN, 1977, ANN DISCRETE MATH, V1, P435

[10]

SBIHI N, RR103 IMAG

← 1 2 →