Kernel Theory in digraphs

• Grant number: 18/16720-6
• Support Opportunities: Scholarships in Brazil - Master
• Start date: March 01, 2019
• End date: September 30, 2019
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Theory of Computation
• Principal Investigator: Orlando Lee
• Grantee: Alonso Ali Gonçalves
• Host Institution: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brazil

Abstract

In this Master's Research Project, we propose the study of kernels and their generalization to k-kernels. We begin by presenting a survey of the current state of the field -- identifying the main results and open problems -- in order to deeply understand the concepts that will be studied and, therefore, easily achieve our goals. Kernels in digraphs were born from the game theory field and attained more relevance when their relation to perfect graphs was proven through the Strong Perfect Graph Theorem. The objective of this project is the study of existing results on the existence of kernels and kernel perfectness in digraphs and generalize them to k-kernels. The generalization of kernel results to k-kernels gained recognition after the generalization of the Richandson's Theorem -- a fundamental result on kernel theory -- and has proven itself a fruitful line of study, being widely researched in the last twenty years. (AU)

Academic Publications

(References retrieved automatically from State of São Paulo Research Institutions)

GONÇALVES, Alonso Ali. On cycles, chords and kernels in digraphs. 2019. Master's Dissertation - Universidade Estadual de Campinas (UNICAMP). Instituto de Computação Campinas, SP.