×

Coloring the nodes of a directed graph. (English) Zbl 1297.05092

Summary: 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.

MSC:

05C15 Coloring of graphs and hypergraphs
05C20 Directed graphs (digraphs), tournaments
68R10 Graph theory (including graph drawing) in computer science
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)

Software:

MaxCliqueDyn
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] I. M. Bomze, M. Budinich, P. M. Pardalos, M. Pelillo, The maximum clique problem, in Handbook of Combinatorial Optimization Vol. 4, Eds. D.-Z. Du and P. M. Pardalos, Kluwer Academic Publisher, Boston, MA 1999. ⇒118; · Zbl 1253.90188
[2] R. Carraghan, P. M. Pardalos, An exact algorithm for the maximum clique problem, Operation Research Letters 9, 6 (1990), 375-382. ⇒118; · Zbl 0711.90080
[3] P. Erdős, L. Moser, On the representation of directed graphs as unions of orderings. Magyar Tud. Akad. Mat. Kutató Int. Közl. 9 (1964), 125-132. ⇒118; · Zbl 0136.44901
[4] P. Erdős, J. W. Moon, On sets of consistent arcs in tournament, Canad. Math. Bull. 8 (1965), 269-271. ⇒118; · Zbl 0137.43301
[5] M. R. Garey, D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-completeness, Freeman, New York, 2003. ⇒118; · Zbl 0411.68039
[6] F. Kárteszi, Introduction to Finite Geometries, North-Holland Pub. Co., Amsterdam, 1976. ⇒120; · Zbl 0325.50001
[7] L. Kiviluoto, P. R. J. Östergård, V. P. Vaskelainen, Exact algorithms for finding maximum transitive subtournaments, (manuscript) ⇒118; · Zbl 1342.90164
[8] J. Konc, D. Janežič, An improved branch and bound algorithm for the maximum clique problem, MATCH Commun. Math. Comput. Chem. 58, 3 (2007), 569-590. ⇒118; · Zbl 1274.05452
[9] D. Kumlander, Some practical algorithms to solve the maximal clique problem, PhD Thesis, Tallin University of Technology, 2005. ⇒118; · Zbl 1079.68076
[10] J. W. Moon, Topics on Tournaments, Holt, Reinhart and Winston, New York, 1968. ⇒118; · Zbl 0191.22701
[11] P. R. J. Östergård, A fast algorithm for the maximum clique problem, Discrete Appl. Math. 120, 1-3 (2002), 197-207. ⇒118; · Zbl 1019.05054
[12] C. H. Papadimitriou, Computational Complexity, Addison-Wesley Publishing Company, Inc., Reading, MA, 1994. ⇒118; · Zbl 0833.68049
[13] R. Stearns, The voting problem, Amer. Math. Monthly 66 (1959), 761-763. ⇒ 118; · Zbl 0090.25101
[14] E. Tomita, T. Seki, An efficient branch-and-bound algorithm for finding a maximum clique, Discrete Mathematics and Theoretical Computer Science, Lecture Notes in Comp. Sci. 2731 (2003), 278-289. ⇒118; · Zbl 1038.68565
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.