A backtracking algorithm to generate all kernels of a directed graph

Abstract

Determining whether or not a directed graph has a kernel belongs to a class of hard combinatorial problems, known as NP-complete. In this paper we develop a backtracking algorithm which generates all the kernels of a directed, graph in lexicographic.order. Extensive computational experience on randomly generated graphs ranging from 10 to 100 nodes and from 30% to 90% densities has shown that this algorithm compares very favourably with existing algorithms.

Keywords:

• Kernel
• directed graph
• backtracking

C.R. Categories:

• 5.32