On cardinality constrained cycle and path polytopes

Details On cardinality constrained cycle and path polytopes On cardinality constrained cycle and path polytopes

2007-10-16

arxiv.org/abs/0710.3036v1

Mathematics

Combinatorics

24 pages

Scientific paper

Given a directed graph D = (N, A) and a sequence of positive integers 1 <= c_1 < c_2 < ... < c_m <= |N|, we consider those path and cycle polytopes that are defined as the convex hulls of simple paths and cycles of D of cardinality c_p for some p, respectively. We present integer characterizations of these polytopes by facet defining linear inequalities for which the separation problem can be solved in polynomial time. These inequalities can simply be transformed into inequalities that characterize the integer points of the undirected counterparts of cardinality constrained path and cycle polytopes. Beyond we investigate some further inequalities, in particular inequalities that are specific to odd/even paths and cycles.

Affiliated with

Also associated with

No associations

Rating

On cardinality constrained cycle and path polytopes 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 On cardinality constrained cycle and path polytopes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On cardinality constrained cycle and path polytopes will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-714329