Facets of the (s,t)-p-path polytope

Details Facets of the (s,t)-p-path polytope Facets of the (s,t)-p-path polytope

2006-06-13

arxiv.org/abs/math/0606308v1

Mathematics

Combinatorics

Scientific paper

We give a partial description of the (s,t)-p-path polytope of a directed graph D which is the convex hull of the incidence vectors of simple directed (s,t)-paths in D of length p. First, we point out how the (s,t)-p-path polytope is located in the family of path and cycle polyhedra. Next, we give some classes of valid inequalities which are very similar to inequalities which are valid for the p-cycle polytope, that is, the convex hull of the incidence vectors of simple cycles of length p in D. We give necessary and sufficient conditions for these inequalities to be facet defining. Furthermore, we consider a class of inequalities that has been identified to be valid for (s,t)-paths of cardinality at most p. Finally, we transfer the results to related polytopes, in particular, the undirected counterpart of the (s,t)-p-path polytope.

Affiliated with

Also associated with

No associations

Rating

Facets of the (s,t)-p-path polytope 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 Facets of the (s,t)-p-path polytope, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Facets of the (s,t)-p-path polytope will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-46147