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:
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...
Maheshwari, Anil, Zeh, Norbert (2004)
Journal of Graph Algorithms and Applications
Similarity:
Laura M. Harris, Johannes H. Hattingh, Michael A. Henning (2006)
Discussiones Mathematicae Graph Theory
Similarity:
Let G = (V,E) be a graph and let k ∈ Z⁺. A total k-subdominating function is a function f: V → {-1,1} such that for at least k vertices v of G, the sum of the function values of f in the open neighborhood of v is positive. The total k-subdomination number of G is the minimum value of f(V) over all total k-subdominating functions f of G where f(V) denotes the sum of the function values assigned to the vertices under f. In this paper, we present a cubic time algorithm to compute the total...
Suderman, Matthew, Whitesides, Sue (2005)
Journal of Graph Algorithms and Applications
Similarity:
Jaroslav Nešetřil (1997)
Archivum Mathematicum
Similarity:
On the background of Borůvka’s pioneering work we present a survey of the development related to the Minimum Spanning Tree Problem. We also complement the historical paper Graham-Hell [GH] by a few remarks and provide an update of the extensive literature devoted to this problem.
Alain Billionnet, Jean-François Brêteau (1989)
RAIRO - Operations Research - Recherche Opérationnelle
Similarity:
Boris Milašinović, Krešimir Fertalj (2012)
Computer Science and Information Systems
Similarity:
Donato, Debora, Laura, Luigi, Leonardi, Stefano, Meyer, Ulrich, Millozzi, Stefano, Sibeyn, Jop F. (2006)
Journal of Graph Algorithms and Applications
Similarity: