Title:
|
A TEXTILE DESIGN AND THE BOOLEAN RANK PROBLEM |
Author(s):
|
Isamu Matsuura , Mutsunori Yagiura , Tomio Hirata |
ISBN:
|
978-972-8924-97-3 |
Editors:
|
Hans Weghorn and Pedro IsaĆas |
Year:
|
2009 |
Edition:
|
V I, 2 |
Keywords:
|
Boolean rank, dobby loom, biclique cover, biclique partition |
Type:
|
Full Paper |
First Page:
|
345 |
Last Page:
|
352 |
Language:
|
English |
Cover:
|
|
Full Contents:
|
click to dowload
|
Paper Abstract:
|
A dobby loom is a weaving machine prevailing in the textile industry. The more heald frames a dobby loom is equipped
with, the more complicated designs of cloth can be woven. By introducing long-eye healds into a dobby loom, we can
reduce the number of heald frames required for a given design of cloth. It was shown that the number of necessary heald
frames equals the Boolean rank of a Boolean matrix associated with the design of cloth, and thus that the problem of
finding, for a given design of cloth, the minimum number of heald frames is NP-hard. Heuristic and exhaustive
algorithms have been proposed so far. In this paper, we consider a more realistic version of the problem and show that the
number of necessary heald frames equals the exclusive Boolean rank of the matrix. Based on this observation, we
propose a heuristic algorithm. |
|
|
|
|