Geodesic
Even kernels
The electronic journal of combinatorics, Tome 1 (1994)
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

Given a graph $G = (V,E)$, an even kernel is a nonempty independent subset $V' \subseteq V$, such that every vertex of $G$ is adjacent to an even number (possibly 0) of vertices in $V'$. It is proved that the question of whether a graph has an even kernel is NP-complete. The motivation stems from combinatorial game theory. It is known that this question is polynomial if $G$ is bipartite. We also prove that the question of whether there is an even kernel whose size is between two given bounds, in a given bipartite graph, is NP-complete. This result has applications in coding and set theory.
DOI : 10.37236/1185
Classification : 68R10, 68Q25
Mots-clés : even kernel, independent subset, bipartite graph 
@article{10_37236_1185,
     author = {Aviezri Fraenkel},
     title = {Even kernels},
     journal = {The electronic journal of combinatorics},
     year = {1994},
     volume = {1},
     doi = {10.37236/1185},
     zbl = {0813.68142},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/1185/}
}
TY  - JOUR
AU  - Aviezri Fraenkel
TI  - Even kernels
JO  - The electronic journal of combinatorics
PY  - 1994
VL  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.37236/1185/
DO  - 10.37236/1185
ID  - 10_37236_1185
ER  - 
%0 Journal Article
%A Aviezri Fraenkel
%T Even kernels
%J The electronic journal of combinatorics
%D 1994
%V 1
%U http://geodesic.mathdoc.fr/articles/10.37236/1185/
%R 10.37236/1185
%F 10_37236_1185
Aviezri Fraenkel. Even kernels. The electronic journal of combinatorics, Tome 1 (1994). doi: 10.37236/1185

Cité par Sources :