Rs-vector algorithms for combinational problems

✍ Scribed by Chuzo Iwamoto; Kazuo Iwama

• Publisher: John Wiley and Sons
• Year: 1993
• Tongue: English
• Weight: 884 KB
• Volume: 24
• Category: Article
• ISSN: 0882-1666
• DOI: 10.1002/scj.4690240704

✦ Synopsis

Abstract

The RS‐vector machine (RS‐VM) is based on the vector operations called repeat and stretch. It is known that generally they speed up according to a single parameter called the expansion factor, several sequential complexity classes over polynomial space to polynomial time.

This paper investigates the computational power of the model for more concrete problems. The RS‐vector algorithms are given which can solve typical NP‐complete problems, i.e., satisfiability, knapsack, partition, vertex cover, clique and exact cover problems in O(n) time, k‐colorable problem in O(n log k) time, and Hamilton circuit and traveling salesperson problems in O(n log^2^ n) time.

It should be emphasized that, compared with other models such as PRAMs, vector machines are completely of SIMD‐type and their communication facilities are nothing less than those represented by repeat and stretch. The results show that such a restricted model can solve a wide range of NP‐problems in almost linear time.