Premium
Een indelingsprobleem
Author(s) -
ANTHONISSE JAC. M.
Publication year - 1968
Publication title -
statistica neerlandica
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.52
H-Index - 39
eISSN - 1467-9574
pISSN - 0039-0402
DOI - 10.1111/j.1467-9574.1968.tb01360.x
Subject(s) - combinatorics , disjoint sets , mathematics , chromatic scale , graph , upper and lower bounds , set (abstract data type) , discrete mathematics , computer science , mathematical analysis , programming language
Summary A branch and bound algorithm is given to solve the following problem: To each pair of elements (i,j) from a set X ={l,…, n } a number r ij with r ij ≥ 0, r ij = r ij and r ij = 0 has been assigned. Find a prescribed number of disjoint subsets P 1 …, P m from X , such that Experiments indicate that an optimal solution is usually found in a small number of iterations, but the verification may be rather time consuming. The algorithm may be used to find the minimum value of m for which a partitioning of X with z = 0 exists. The algorithm appears to be efficient for finding this ‘chromatic number of a graph’.