Approximation algorithms for the maximum induced planar and outerplanar subgraph problems.
Morgan, Kerri, Farr, Graham (2007)
Journal of Graph Algorithms and Applications
Similarity:
Morgan, Kerri, Farr, Graham (2007)
Journal of Graph Algorithms and Applications
Similarity:
Eppstein, David, Wang, Joseph (2004)
Journal of Graph Algorithms and Applications
Similarity:
Eppstein, David (2003)
Journal of Graph Algorithms and Applications
Similarity:
V. Th. Paschos (1994)
RAIRO - Operations Research - Recherche Opérationnelle
Similarity:
Shapira, Andrew (1997)
The Electronic Journal of Combinatorics [electronic only]
Similarity:
Maheshwari, Anil, Zeh, Norbert (2004)
Journal of Graph Algorithms and Applications
Similarity:
Harel, David, Koren, Yehuda (2002)
Journal of Graph Algorithms and Applications
Similarity:
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...
Marc Demange, Bernard Kouakou, Eric Soutif (2011)
The Yugoslav Journal of Operations Research
Similarity:
Alain Billionnet, Jean-François Brêteau (1989)
RAIRO - Operations Research - Recherche Opérationnelle
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...
Gajer, Pawel, Kobourov, Stephen G. (2002)
Journal of Graph Algorithms and Applications
Similarity:
Aslam, Javed A., Pelekhov, Ekaterina, Rus, Daniela (2004)
Journal of Graph Algorithms and Applications
Similarity: