A randomised heuristical algorithm for estimating the chromatic number of a graph (Q1262784): Difference between revisions
From MaRDI portal
Set profile property. |
ReferenceBot (talk | contribs) Changed an Item |
||
(One intermediate revision by one other user not shown) | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/0020-0190(89)90144-0 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2121434721 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Finite particle systems and infection models / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4198056 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Computational Complexity of Probabilistic Turing Machines / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Optimization by Simulated Annealing / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: An upper bound for the chromatic number of a graph and its application to timetabling problems / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3358770 / rank | |||
Normal rank |
Latest revision as of 11:41, 20 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A randomised heuristical algorithm for estimating the chromatic number of a graph |
scientific article |
Statements
A randomised heuristical algorithm for estimating the chromatic number of a graph (English)
0 references
1989
0 references
We define a class of randomised heuristical algorithms for colouring the vertices of a graph. The problem of graph colouring is known to be NP- complete unless a graph is bipartite. If \(P\neq NP\), then an algorithm for solving an NP-complete or NP-hard problem runs in time which is not bounded by a polynomial function of the problem size. This is the reason for the search of heuristic approaches, which may give (practically) usable results in reasonable time also for larger instances of a particular NP-hard problem. We propose some generalizations of the antivoter algorithm and in this way define a class of algorithms. The essential difference between the original and our algorithms is that our algorithms instead of answering the decision problem: ``Is given graph G k-colourable?'' rather give an estimate for an upper bound of \(\chi\) (G), the chromatic number of G. Comparative experiments led us to believe that for suitably tuned parameters this can be achieved in a time comparable with the time which is needed for the antivoter algorithm. On the other hand, if we try to estimate \(\chi\) (G) with the antivoter algorithm, we would probably need more time. First, we need a reliable upper bound for \(\chi\) (G), say \(u\geq \chi (G)\). Then we repeatedly run the antivoter algorithm with the number of colours u, u-1, u-2, etc. until one of the runs will give a negative answer. We outline a (surprisingly) elementary proof of a kind of weak convergence property that holds for our algorithms. We prove that there is a positive probability to find a \(\chi\) (G)-colouring in finitely many steps with our algorithms. Moreover, it does not matter with which colouring we start. In other words, no initial colouring is hopeless for our algorithms.
0 references
combinatorial problem
0 references
randomised heuristics
0 references
graph colouring
0 references
antivoter algorithm
0 references
0 references