The search session has expired. Please query the service again.

The search session has expired. Please query the service again.

Displaying similar documents to “A relation between the approximated versions of minimum set covering, minimum vertex covering and maximum independent set”

On-line models and algorithms for max independent set

Bruno Escoffier, Vangelis Th. Paschos (2006)

RAIRO - Operations Research

Similarity:

In on-line computation, the instance of the problem dealt is not entirely known from the beginning of the solution process, but it is revealed step-by-step. In this paper we deal with on-line independent set. On-line models studied until now for this problem suppose that the input graph is initially empty and revealed either vertex-by-vertex, or cluster-by-cluster. Here we present a new on-line model quite different to the ones already studied. It assumes that a superset of the final...

Satisfiability and matchings in bipartite graphs: relationship and tractability.

Belaid Benhamou (2004)

RACSAM

Similarity:

Satisfiability problem is the task to establish either a given CNF logical formula admits a model or not. It is known to be the canonical NP-complete problem. We study in this note the relationship between matchings in bipartite graphs and the satisfiability problem, and prove that some restrictions of formulae including the known r-r-SAT class are trivially satisfiable. We present an algorithm which finds a model for such formulas in polynomial time complexity if one exists or, failing...

A Metaheuristic Approach to Solving the Generalized Vertex Cover Problem

Milanović, Marija (2010)

Mathematica Balkanica New Series

Similarity:

AMS Subj. Classification: 90C27, 05C85, 90C59 The topic is related to solving the generalized vertex cover problem (GVCP) by genetic algorithm. The problem is NP-hard as a generalization of well-known vertex cover problem which was one of the first problems shown to be NP-hard. The definition of the GVCP and basics of genetic algorithms are described. Details of genetic algorithm and numerical results are presented in [8]. Genetic algorithm obtained high quality solutions in...