Disconnecting graphs by removing vertices: a polyhedral approach

Maarten Oosten, Jeroen H. G. C. Rutten and Frits C. R. Spieksma

Statistica Neerlandica, 2007, vol. 61, issue 1, 35-60

Abstract: In this paper, we consider the problem of disconnecting a graph by removing as few vertices as possible, such that no component of the disconnected graph has more than a given number of vertices. We give applications of this problem, present a formulation for it, and describe some polyhedral results. Furthermore, we establish ties with other polytopes and show how these relations can be used to obtain facets of our polytope. Finally, we give some computational results.

Date: 2007
References: View complete reference list from CitEc
Citations: View citations in EconPapers (7)

Downloads: (external link)
https://doi.org/10.1111/j.1467-9574.2007.00350.x

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:bla:stanee:v:61:y:2007:i:1:p:35-60

Ordering information: This journal article can be ordered from
http://www.blackwell ... bs.asp?ref=0039-0402

Access Statistics for this article

Statistica Neerlandica is currently edited by Miroslav Ristic, Marijtje van Duijn and Nan van Geloven

More articles in Statistica Neerlandica from Netherlands Society for Statistics and Operations Research
Bibliographic data for series maintained by Wiley Content Delivery ().