Applying tabu search to determine new Ramsey graphs.
Piwakowski, Konrad (1996)
The Electronic Journal of Combinatorics [electronic only]
Similarity:
Piwakowski, Konrad (1996)
The Electronic Journal of Combinatorics [electronic only]
Similarity:
J. Grabowski (1978)
Applicationes Mathematicae
Similarity:
J. Pach, H. de Fraysseix, P.O. de Mendez (1995)
Discrete & computational geometry
Similarity:
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.
Lynch, Christopher, Strogova Polina (1998)
Discrete Mathematics and Theoretical Computer Science. DMTCS [electronic only]
Similarity:
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...
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...
John R. Gilbert, Robert E. Tarjan (1986/87)
Numerische Mathematik
Similarity:
José D. Alvarado, Simone Dantas, Dieter Rautenbach (2017)
Discussiones Mathematicae Graph Theory
Similarity:
For a graph G, let R(G) and yr2(G) denote the Roman domination number of G and the 2-rainbow domination number of G, respectively. It is known that yr2(G) ≤ R(G) ≤ 3/2yr2(G). Fujita and Furuya [Difference between 2-rainbow domination and Roman domination in graphs, Discrete Appl. Math. 161 (2013) 806-812] present some kind of characterization of the graphs G for which R(G) − yr2(G) = k for some integer k. Unfortunately, their result does not lead to an algorithm that allows to recognize...
Gary Chartrand, Hudson V. Kronk, Seymour Schuster (1973)
Colloquium Mathematicae
Similarity:
Zdzisław Skupień (2007)
Discussiones Mathematicae Graph Theory
Similarity:
Risto Šokarovski (1977)
Publications de l'Institut Mathématique
Similarity:
M. M. Sysło (1987)
Applicationes Mathematicae
Similarity:
Bretto, A. (1999)
Southwest Journal of Pure and Applied Mathematics [electronic only]
Similarity: