Sur les quasi-noyaux d’un graphe. (On quasi-kernels of a graph). (French) Zbl 0623.05020
Authors’ summary: “We define three classes of quasi-kernels for a directed graph. As a consequence, we show the existence of quasi-kernels in every progressively finite graph and in every locally finite graph, generalizing the result of Chvátal and Lovász which deals with the finite case. Our method shows that the problem of finding a quasi-kernel in a finite digraph and the problem of finding the unique kernel of an acircuitic finite digraph have the same algorithmic complexity.”
Reviewer: G.Chaty
MSC:
| 05C20 | Directed graphs (digraphs), tournaments |
References:
| [1] | Bry, F., Sur les noyaux dans les graphes infinis, Note de Recherche, Univ. Paris, 6 (1979), non publié |
| [2] | Chvátal, V.; Lovász, L., Every directed graph has a semi-kernel, (Hypergraph Seminar. Hypergraph Seminar, Lect. Notes in Math., 411 (1974), Springer: Springer Berlin), 175 · Zbl 0297.05116 |
| [3] | Milner, E. C.; Woodrow, R. E., On directed graphs with an independent covering set (1985), submitted · Zbl 0689.05027 |
| [4] | von Neuman, J.; Morgenstern, O., Theory of Games and Economical Behavior (1944), Princeton Univ. Press: Princeton Univ. Press Princeton, N.J · Zbl 0063.05930 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
