Polynomial algorithms for kernels in comparability, permutation and P
4-free graphs |
| |
| Authors: | Moncef Abbas Youcef Saoula |
| |
| Institution: | (1) USTHB, Faculté de Mathématiques, LAID3, El-Alia, BP 32, Bab-Ezzouar, 16111 Alger, Algérie;(2) Département de Mathématiques, Ecole Normale Supérieure, BP 92 Kouba, 16050 Alger, Algérie |
| |
| Abstract: | In this paper, we give three polynomial algorithms which detect a kernel in comparability graphs relatively to an M-orientation,
in permutation graphs and in P4-free graphs with a normal orientation.
MSC classification:
05C69, 05C85
Correspondence to: Saoula Youcef |
| |
| Keywords: | Orientation kernel comparability graph permutation graph P4-free graph |
| 本文献已被 SpringerLink 等数据库收录！ |
|
