Displaying similar documents to “On the Hardness of Approximating Some NP-optimization Problems Related to Minimum Linear Ordering Problem”

On the hardness of approximating some NP-optimization problems related to minimum linear ordering problem

Sounaka Mishra, Kripasindhu Sikdar (2001)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity:

We study hardness of approximating several minimaximal and maximinimal NP-optimization problems related to the minimum linear ordering problem (MINLOP). MINLOP is to find a minimum weight acyclic tournament in a given arc-weighted complete digraph. MINLOP is APX-hard but its unweighted version is polynomial time solvable. We prove that MIN-MAX-SUBDAG problem, which is a generalization of MINLOP and requires to find a minimum cardinality maximal acyclic subdigraph of a given digraph,...

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.