Linear time recognition of -indifference graphs.
Habib, Michael, Paul, Christophe, Viennot, Laurent (2001)
Discrete Mathematics and Theoretical Computer Science. DMTCS [electronic only]
Similarity:
Habib, Michael, Paul, Christophe, Viennot, Laurent (2001)
Discrete Mathematics and Theoretical Computer Science. DMTCS [electronic only]
Similarity:
Piwakowski, Konrad (1996)
The Electronic Journal of Combinatorics [electronic only]
Similarity:
J. Pach, H. de Fraysseix, P.O. de Mendez (1995)
Discrete & computational geometry
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...
Evripidis Bampis (2010)
RAIRO - Operations Research
Similarity:
We show that the problem of deciding if there is a schedule of length three for the multiprocessor scheduling problem on identical machines and unit execution time tasks in -complete even for bipartite graphs, i.e. for precedence graphs of depth one. This complexity result extends a classical result of Lenstra and Rinnoy Kan [5].
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.
John R. Gilbert, Robert E. Tarjan (1986/87)
Numerische Mathematik
Similarity:
Lynch, Christopher, Strogova Polina (1998)
Discrete Mathematics and Theoretical Computer Science. DMTCS [electronic only]
Similarity:
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.
A. Adrabiński, M. Wodecki (1979)
Applicationes Mathematicae
Similarity:
M. M. Sysło (1987)
Applicationes Mathematicae
Similarity:
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...
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...
Bruno Bachelet, Philippe Mahey (2003)
RAIRO - Operations Research - Recherche Opérationnelle
Similarity:
We present briefly some results we obtained with known methods to solve minimum cost tension problems, comparing their performance on non-specific graphs and on series-parallel graphs. These graphs are shown to be of interest to approximate many tension problems, like synchronization in hypermedia documents. We propose a new aggregation method to solve the minimum convex piecewise linear cost tension problem on series-parallel graphs in operations.