Displaying similar documents to “Acyclic orientations with path constraints”

Bounds of graph parameters for global constraints

Nicolas Beldiceanu, Thierry Petit, Guillaume Rochart (2006)

RAIRO - Operations Research - Recherche Opérationnelle

Similarity:

This article presents a basic scheme for deriving systematically a filtering algorithm from the graph properties based representation of global constraints. This scheme is based on the bounds of the graph parameters used in the description of a global constraint. The article provides bounds for the most common used graph parameters.

Acyclic Orientations with Path Constraints

Rosa M. V. Figueiredo, Valmir C. Barbosa, Nelson Maculan, Cid C. de Souza (2009)

RAIRO - Operations Research

Similarity:

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...

Exponents of two-colored digraphs

Yan Ling Shao, Yubin Gao (2009)

Czechoslovak Mathematical Journal

Similarity:

We consider the primitive two-colored digraphs whose uncolored digraph has n + s vertices and consists of one n -cycle and one ( n - 3 ) -cycle. We give bounds on the exponents and characterizations of extremal two-colored digraphs.