A Filter for the Circuit Constraint.pdf.pdf' (353.33 kB)
A Filter for the Circuit Constraint
journal contribution
posted on 1987-04-01, 00:00 authored by Latife Genç-Kaya, John N. HookerWe present an incomplete filtering algorithm for the circuit
constraint. The filter removes redundant values by eliminating nonhamiltonian
edges from the associated graph. We identify nonhamiltonian
edges by analyzing a smaller graph with labeled edges that is defined
on a separator of the original graph. The complexity of the procedure
for each separator S is approximately O(|S|5).We found that it identified
all infeasible instances and eliminated about one-third of the redundant
domain elements in feasible instances.