Inductive Kernels of Graphs

Abstract : It is well known that kernels in graphs are powerful and useful structures, for instance in the theory of games. However, a kernel does not always exist and Chvátal proved in 1973 that it is an NP-Complete problem to decide its existence. We present here an alternative definition of kernels that uses an inductive machinery : the inductive kernels. We prove that inductive kernels always exist and a particular one can be constructed in linear time. However, it is an NP-Complete problem to decide the existence of an inductive kernel including (resp. excluding) some fixed vertex.
Keywords : kernel
Type de document :
Article dans une revue
Journal of Multiple-Valued Logic and Soft Computing, 2016, 27 (2/3), pp.175-181
Liste complète des métadonnées

http://hal.univ-reunion.fr/hal-01479612
Contributeur : Réunion Univ <>
Soumis le : mardi 28 février 2017 - 20:47:29
Dernière modification le : mercredi 7 février 2018 - 08:12:02

Identifiants

  • HAL Id : hal-01479612, version 1

Collections

Citation

Serge Burckel. Inductive Kernels of Graphs. Journal of Multiple-Valued Logic and Soft Computing, 2016, 27 (2/3), pp.175-181. 〈hal-01479612〉

Partager

Métriques

Consultations de la notice

53