Skip Header

RRC2003-01
Bor-Chung Chen and William E. Winkler

Abstract

Most combinatorial problems are very big - bigger than what can be handled efficiently on most fast computers - and hence the development and implementation of fast algorithms is very important. The DISCRETE edit system, based on the Fellegi and Holt model (1976) of editing, contains a combinatorial problem: the set covering problem (SCP). The two major components of the edit system are edit generation and error localization. The SCP is formulated many times in both components. Therefore, an efficient set covering algorithm is critical to the overall performance of the DISCRETE edit system. The preorder of traversing a tree is one of the structures used in the design of a set covering algorithm for the DISCRETE edit system. In this paper, we will describe a simple implementation of the preorder of traversing a tree used in a new set covering algorithm proposed by Chen (1998).

Related Information


Back to Header