liu.seSearch for publications in DiVA
Change search
ReferencesLink to record
Permanent link

Direct link
Algorithms for Max Hamming exact satisfiability
Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory. Linköping University, The Institute of Technology.
2005 (English)In: Algorithms and Computation: 16th International Symposium, ISAAC 2005, Sanya, Hainan, China, December 19-21, 2005. Proceedings / [ed] Xiaotie Deng and Ding-Zhu Du, Springer Berlin/Heidelberg, 2005, Vol. 3827, 829-838 p.Chapter in book (Refereed)
Abstract [en]

We here study MAX HAMMING XSAT, i.e., the problem of finding two XSAT models at maximum Hamming distance. By using a recent XSAT solver as an auxiliary function, an O(2(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.

Place, publisher, year, edition, pages
Springer Berlin/Heidelberg, 2005. Vol. 3827, 829-838 p.
Lecture Notes in Computer Science, ISSN 0302-9743 (print), 1611-3349 (online) ; 3827
, Lecture Notes in Computer Science, ISSN 0302-9743 ; 3827
National Category
Engineering and Technology
URN: urn:nbn:se:liu:diva-48109DOI: 10.1007/11602613_83ISBN: 978-3-540-30935-2ISBN: 3-540-30935-7OAI: diva2:269005
Available from: 2009-10-11 Created: 2009-10-11 Last updated: 2013-10-15Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textfind book at a swedish library/hitta boken i ett svenskt bibliotek

Search in DiVA

By author/editor
Dahllöf, Vilhelm
By organisation
TCSLAB - Theoretical Computer Science LaboratoryThe Institute of Technology
Engineering and Technology

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 33 hits
ReferencesLink to record
Permanent link

Direct link