Access Restriction

Author Segundo, P.S. ♦ Rodriguez-Losada, D. ♦ Galan, R. ♦ Matia, F. ♦ Jimenez, A.
Source IEEE Xplore Digital Library
Content type Text
Publisher Institute of Electrical and Electronics Engineers, Inc. (IEEE)
File Format PDF
Copyright Year ©2007
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Special computer methods
Subject Keyword Search problems ♦ Application software ♦ Parallel processing ♦ Concrete ♦ Signal processing algorithms ♦ Computer vision ♦ Artificial intelligence ♦ Intelligent control ♦ Concurrent computing ♦ Buildings
Abstract It is the authors' belief that the ability of processors to compute bit parallel operations should have a right to exist as an optimization discipline, rather than a state-of- the-art technique. This paper is a step forward in this direction analysing a number of key issues related to bit model design and implementation of search problems. Building efficient search algorithms optimized at bit level is a difficult task It requires not only a good implementation but also an adequate model so as to make bitwise operations meaningful, and only by addressing design and implementation globally an improvement in efficiency can be obtained. On the other hand, we have proved in this paper that the improvement can conceivably be exponential on the size of the CPU register for problems in NP. This global approach has been used to implement the fastest complete algorithm, to the best of our knowledge, for the maximum clique problem, an important NP-hard combinatorial problem from the graph domain. Our solver clearly outperforms other existing algorithms for hard instances, in some cases by nearly an order of magnitude.
Description Author affiliation: Univ. Polytech. de Madrid, Madrid (Segundo, P.S.; Rodriguez-Losada, D.; Galan, R.; Matia, F.; Jimenez, A.)
ISBN 9780769530154
ISSN 10823409
Educational Role Student ♦ Teacher
Age Range above 22 year
Educational Use Research ♦ Reading
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2007-10-29
Publisher Place Greece
Rights Holder Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Size (in Bytes) 479.70 kB
Page Count 7
Starting Page 53
Ending Page 59

Source: IEEE Xplore Digital Library