Algorithms for Max Hamming Exact Satisfiability

Details Algorithms for Max Hamming Exact Satisfiability Algorithms for Max Hamming Exact Satisfiability

2005-09-14

arxiv.org/abs/cs/0509038v1

Computer Science

Data Structures and Algorithms

Scientific paper

We here study Max Hamming XSAT, ie, the problem of finding two XSAT models at maximum Hamming distance. By using a recent XSAT solver as an auxiliary function, an O(1.911^n) time algorithm can be constructed, where n is the number of variables. This upper time bound can be further improved to O(1.8348^n) by introducing a new kind of branching, more directly suited for finding models at maximum Hamming distance. The techniques presented here are likely to be of practical use as well as of theoretical value, proving that there are non-trivial algorithms for maximum Hamming distance problems.

Affiliated with

Also associated with

No associations

Rating

Algorithms for Max Hamming Exact Satisfiability does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Algorithms for Max Hamming Exact Satisfiability, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Algorithms for Max Hamming Exact Satisfiability will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-680081