<abstract xmlns="http://www.w3.org/1999/xhtml"><p> It is an empirical fact that coloring the nodes of a graph can be used to speed up clique search algorithms. In directed graphs transitive subtournaments can play the role of cliques. In order to speed up algorithms to locate large transitive tournaments we propose a scheme for coloring the nodes of a directed graph. The main result of the paper is that in practically interesting situations determining the optimal number of colors in the proposed coloring is an NP-hard problem. A possible conclusion to draw from this result is that for practical transitive tournament search algorithms we have to develop approximate greedy coloring algorithms.</p></abstract>

It is an empirical fact that coloring the nodes of a graph can be used to speed up clique search algorithms. In directed graphs transitive subtournaments can play the role of cliques. In order to speed up algorithms to locate large transitive tournaments we propose a scheme for coloring the nodes of a directed graph. The main result of the paper is that in practically interesting situations determining the optimal number of colors in the proposed coloring is an NP-hard problem. A possible conclusion to draw from this result is that for practical transitive tournament search algorithms we have to develop approximate greedy coloring algorithms.

Coloring the nodes of a directed graph

University of Pécs Institute of Mathematics and Informatics, Ifjúság u. 6 7624 Pécs, HUNGARY

Acta Universitatis Sapientiae, Informatica

This article is distributed under the terms of the Creative Commons Attribution Non-Commercial License, which permits unrestricted non-commercial use, distribution, and reproduction in any medium, provided the original work is properly cited.

{"article-title":"Coloring the nodes of a directed graph"}

It is an empirical fact that coloring the nodes of a graph can be used to speed up clique search algorithms. In directed graphs transitive subtournaments can...

Coloring the nodes of a directed graph

Publié en ligne: 27 juin 2014

Pages: 117 - 131

Reçu: 25 août 2013

DOI: https://doi.org/10.2478/ausi-2014-0021

Mots clés
simple directed graph, tournament, transitive tournament, maximum transitive tournament, graph coloring, coloring the nodes, NP-hard problems

© 2014

This article is distributed under the terms of the Creative Commons Attribution Non-Commercial License, which permits unrestricted non-commercial use, distribution, and reproduction in any medium, provided the original work is properly cited.

Coloring the nodes of a directed graph

Publié en ligne: 27 juin 2014

Pages: 117 - 131

Reçu: 25 août 2013

DOI: https://doi.org/10.2478/ausi-2014-0021

Mots cléssimple directed graph, tournament, transitive tournament, maximum transitive tournament, graph coloring, coloring the nodes, NP-hard problems

© 2014

This article is distributed under the terms of the Creative Commons Attribution Non-Commercial License, which permits unrestricted non-commercial use, distribution, and reproduction in any medium, provided the original work is properly cited.

Mots clés
simple directed graph, tournament, transitive tournament, maximum transitive tournament, graph coloring, coloring the nodes, NP-hard problems