An Algebraic Formulation of a Multiple Path Problem in a Planar Graph with Triple Connectivity

摘要

The report presents a formulation of the single layer printed circuit wiring problem which, to the author's knowledge, is the only known approach other than complete enumeration of all combinations of all possible paths that will generate a solution, i.e., a set of disjoint paths, in every case where a feasible solution exists. Whether the improvement in computational efficiency relative to complete enumeration is sufficient to permit this formulation to provide the basis of a practical computational procedure is still unknown. Its practicality depends on the facility with which a certain set of simultaneous Boolean equations may be solved in cases of practical interest. (Author)