caa a22 4500 463186931 CHVBK 20180406164856.0 cr unu---uuuuu 170326e20070901xx s 000 0 eng 10.1007/s10472-007-9084-z doi (NATIONALLICENCE)springer-10.1007/s10472-007-9084-z Porschen Stefan Institut für Informatik, Universität zu Köln, Pohligstr. 1, 50969, Köln, Germany aut On variable-weighted exact satisfiability problems [Elektronische Daten] [Stefan Porschen] We show that the NP-hard optimization problems minimum and maximum weight exact satisfiability (XSAT) for a CNF formula C over n propositional variables equipped with arbitrary real-valued weights can be solved in O(||C||20.2441n ) time. To the best of our knowledge, the algorithms presented here are the first handling weighted XSAT optimization versions in non-trivial worst case time. We also investigate the corresponding weighted counting problems, namely we show that the number of all minimum, resp. maximum, weight exact satisfiability solutions of an arbitrarily weighted formula can be determined in O(n 2·||C|| + 20.40567n ) time. In recent years only the unweighted counterparts of these problems have been studied (Dahllöf and Jonsson, An algorithm for counting maximum weighted independent sets and its applications. In: Proceedings of the 13th ACM-SIAM Symposium on Discrete Algorithms, pp. 292-298, 2002; Dahllöf et al., Theor Comp Sci 320: 373-394, 2004; Porschen, On some weighted satisfiability and graph problems. In: Proceedings of the 31st Conference on Current Trends in Theory and Practice of Informatics (SOFSEM 2005). Lecture Notes in Comp. Science, vol. 3381, pp. 278-287. Springer, 2005). Springer Science+Business Media B.V., 2007 Weighted exact satisfiability nationallicence Exact algorithm nationallicence Combinatorial optimization nationallicence Counting problem nationallicence NP-completeness nationallicence Perfect matching nationallicence Maximum weight independent set nationallicence Set partition nationallicence Annals of Mathematics and Artificial Intelligence Springer Netherlands 51/1(2007-09-01), 27-54 1012-2443 51:1<27 2007 51 10472 https://doi.org/10.1007/s10472-007-9084-z text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s10472-007-9084-z text/html Onlinezugriff via DOI NATIONALLICENCE 100 1- Porschen Stefan Institut für Informatik, Universität zu Köln, Pohligstr. 1, 50969, Köln, Germany aut NATIONALLICENCE 773 0- Annals of Mathematics and Artificial Intelligence Springer Netherlands 51/1(2007-09-01), 27-54 1012-2443 51:1<27 2007 51 10472 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer