ZIB

Hits per page

hit 1 - 1 | 1 hit

Select All Export

Electronic Resource

Facets with fixed defect of the stable set polytope (2000)

Lipták, László ; Lovász, László

Springer

Mathematical programming 88 (2000), S. 33-44

add to mindlist on the mindlist

Details

ISSN: 1436-4646

Source: Springer Online Journal Archives 1860-2000

Topics: Computer Science , Mathematics

Notes: Abstract. The stable set polytope of a graph is the convex hull of the 0-1 vectors corresponding to stable sets of vertices. To any nontrivial facet ∑ v∈V a(v)x v ≤b of this polytope we associate an integer δ, called the defect of the facet, by δ=∑ v∈V a(v)-2b. We show that for any fixed δ there is a finite collection of graphs (called “basis”) such that any graph with a facet of defect δ contains a subgraph which can be obtained from one of the graphs in the basis by a simple subdivision operation.

Type of Medium: Electronic Resource

URL: http://dx.doi.org/10.1007/PL00011376

Library	Location	Call Number	Volume/Issue/Year	Availability

Others were also interested in ...

Paper (German National Licenses)

Fulltext

hit 1 - 1 | 1 hit