Displaying similar documents to “Reducing Off-Line to On-Line: an Example and Its Applications”

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

Heuristic and metaheuristic methods for computing graph treewidth

François Clautiaux, Aziz Moukrim, Stéphane Nègre, Jacques Carlier (2004)

RAIRO - Operations Research - Recherche Opérationnelle

Similarity:

The notion of treewidth is of considerable interest in relation to NP-hard problems. Indeed, several studies have shown that the tree-decomposition method can be used to solve many basic optimization problems in polynomial time when treewidth is bounded, even if, for arbitrary graphs, computing the treewidth is NP-hard. Several papers present heuristics with computational experiments. For many graphs the discrepancy between the heuristic results and the best lower bounds is still very...

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