Displaying similar documents to “A solvable case of the set-partitioning problem”

An attractive class of bipartite graphs

Rodica Boliac, Vadim Lozin (2001)

Discussiones Mathematicae Graph Theory

Similarity:

In this paper we propose a structural characterization for a class of bipartite graphs defined by two forbidden induced subgraphs. We show that the obtained characterization leads to polynomial-time algorithms for several problems that are NP-hard in general bipartite graphs.

Factoring directed graphs with respect to the cardinal product in polynomial time II

Wilfried Imrich, Werner Klöckl (2010)

Discussiones Mathematicae Graph Theory

Similarity:

By a result of McKenzie [7] all finite directed graphs that satisfy certain connectivity conditions have unique prime factorizations with respect to the cardinal product. McKenzie does not provide an algorithm, and even up to now no polynomial algorithm that factors all graphs satisfying McKenzie's conditions is known. Only partial results [1,3,5] have been published, all of which depend on certain thinness conditions of the graphs to be factored. In this paper we...

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.

Solving the Minimum Independent Domination Set Problem in Graphs by Exact Algorithm and Greedy Heuristic

Christian Laforest, Raksmey Phan (2013)

RAIRO - Operations Research - Recherche Opérationnelle

Similarity:

In this paper we present a new approach to solve the Minimum Independent Dominating Set problem in general graphs which is one of the hardest optimization problem. We propose a method using a clique partition of the graph, partition that can be obtained greedily. We provide conditions under which our method has a better complexity than the complexity of the previously known algorithms. Based on our theoretical method, we design in the second part of this paper an efficient algorithm...

A note on domination in bipartite graphs

Tobias Gerlach, Jochen Harant (2002)

Discussiones Mathematicae Graph Theory

Similarity:

DOMINATING SET remains NP-complete even when instances are restricted to bipartite graphs, however, in this case VERTEX COVER is solvable in polynomial time. Consequences to VECTOR DOMINATING SET as a generalization of both are discussed.

A signature-based algorithm for computing Gröbner-Shirshov bases in skew solvable polynomial rings

Xiangui Zhao, Yang Zhang (2015)

Open Mathematics

Similarity:

Signature-based algorithms are efficient algorithms for computing Gröbner-Shirshov bases in commutative polynomial rings, and some noncommutative rings. In this paper, we first define skew solvable polynomial rings, which are generalizations of solvable polynomial algebras and (skew) PBW extensions. Then we present a signature-based algorithm for computing Gröbner-Shirshov bases in skew solvable polynomial rings over fields.