Fast exact colouring algorithms

In: Tatra Mountains Mathematical Publications, vol. 9, no. 3

Ingo Schiermeyer

Detaily:

Rok, strany: 1996, 15 - 30

O článku:

In this paper we describe and analyze four improved algorithms for deciding the $3-, 4-, 5-$ and $6-$ Colourability problem. If $G$ is a simple graph on $n$ vertices then we will show that these algorithms test a graph for $3-, 4-, 5-$ or $6$-Colourability, i.e., an assignment of three, four, five or six colours to the vertices of $G$ such that two adjacent vertices obtain different colours, in less than $O(1,398^N)$, $O(1,585ⁿ)$, $O(1,938ⁿ)$ or $O(2,155ⁿ)$ steps.

Ako citovať:

ISO 690:

Schiermeyer, I. 1996. Fast exact colouring algorithms. In Tatra Mountains Mathematical Publications, vol. 9, no.3, pp. 15-30. 1210-3195.

APA:

Schiermeyer, I. (1996). Fast exact colouring algorithms. Tatra Mountains Mathematical Publications, 9(3), 15-30. 1210-3195.