A New Greedoid: The Family of Local Maximum Stable Sets of a Forest

Details A New Greedoid: The Family of Local Maximum Stable Sets of a Forest A New Greedoid: The Family of Local Maximum Stable Sets of a Forest

1999-12-29

arxiv.org/abs/math/9912222v1

Mathematics

Combinatorics

A preliminary version of this paper has been presented at DIMACS-RUTCOR Workshop DO'99: Discrete Optimization '99, July 1999,

Scientific paper

A maximum stable set in a graph G is a stable set of maximum cardinality. S is a local maximum stable set if it is a maximum stable set of the subgraph of G spanned by the union of S and N(S), where N(S) is the neighborhood of S. One theorem of Nemhauser and Trotter Jr., working as a useful sufficient local optimality condition for the weighted maximum stable set problem, ensures that any local maximum stable set of G can be enlarged to a maximum stable set of G. In this paper we demonstrate that an inverse assertion is true for forests. Namely, we show that for any non-empty local maximum stable set S of a forest T there exists a local maximum stable set S1 of T, such that S1 is included in S and |S1| = |S| - 1. Moreover, as a further strengthening of both the theorem of Nemhauser and Trotter Jr. and its inverse, we prove that the family of all local maximum stable sets of a forest forms a greedoid on its vertex set.

Affiliated with

Also associated with

No associations

Rating

A New Greedoid: The Family of Local Maximum Stable Sets of a Forest does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A New Greedoid: The Family of Local Maximum Stable Sets of a Forest, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A New Greedoid: The Family of Local Maximum Stable Sets of a Forest will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-457939