Acyclic orientations with path constraints

Details Acyclic orientations with path constraints Acyclic orientations with path constraints

2005-10-21

arxiv.org/abs/cs/0510064v1

RAIRO Operations Research 42 (2008), 455-467

Computer Science

Discrete Mathematics

Scientific paper

10.1051/ro:2008028

Many well-known combinatorial optimization problems can be stated over the set of acyclic orientations of an undirected graph. For example, acyclic orientations with certain diameter constraints are closely related to the optimal solutions of the vertex coloring and frequency assignment problems. In this paper we introduce a linear programming formulation of acyclic orientations with path constraints, and discuss its use in the solution of the vertex coloring problem and some versions of the frequency assignment problem. A study of the polytope associated with the formulation is presented, including proofs of which constraints of the formulation are facet-defining and the introduction of new classes of valid inequalities.

Affiliated with

Also associated with

No associations

Rating

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

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-89070