On-Line Computation and Maximum-Weighted Hereditary Subgraph Problems
Marc Demange, Bernard Kouakou, Eric Soutif (2011)
The Yugoslav Journal of Operations Research
Similarity:
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
Marc Demange, Bernard Kouakou, Eric Soutif (2011)
The Yugoslav Journal of Operations Research
Similarity:
He, G., Liu, J., Zhao, C. (2000)
Journal of Graph Algorithms and Applications
Similarity:
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...
Walshaw, Chris (2003)
Journal of Graph Algorithms and Applications
Similarity:
V. Th. Paschos (1994)
RAIRO - Operations Research - Recherche Opérationnelle
Similarity:
Zsolt Tuza (1992)
Acta Universitatis Carolinae. Mathematica et Physica
Similarity:
D. Arun Kumar, C. Pandu Rangan (2000)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Similarity:
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...
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...
Aslam, Javed A., Pelekhov, Ekaterina, Rus, Daniela (2004)
Journal of Graph Algorithms and Applications
Similarity: