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

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

Displaying similar documents to “Solving the Minimum Independent Domination Set Problem in Graphs by Exact Algorithm and Greedy Heuristic”

Heuristic and metaheuristic methods for computing graph treewidth

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

RAIRO - Operations Research

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

A polynomial algorithm for minDSC on a subclass of series Parallel graphs

Salim Achouri, Timothée Bossart, Alix Munier-Kordon (2009)

RAIRO - Operations Research

Similarity:

The aim of this paper is to show a polynomial algorithm for the problem minimum directed sumcut for a class of series parallel digraphs. The method uses the recursive structure of parallel compositions in order to define a dominating set of orders. Then, the optimal order is easily reached by minimizing the directed sumcut. It is also shown that this approach cannot be applied in two more general classes of series parallel digraphs.

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

Algorithmic aspects of total-subdomination in graphs

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