caa a22 4500 445879297 CHVBK 20180317145537.0 cr unu---uuuuu 170323e20111001xx s 000 0 eng 10.1007/s10601-011-9110-y doi (NATIONALLICENCE)springer-10.1007/s10601-011-9110-y New algorithms for max restricted path consistency [Elektronische Daten] [Thanasis Balafoutis, Anastasia Paparrizou, Kostas Stergiou, Toby Walsh] Max Restricted Path Consistency (maxRPC) is a local consistency for binary constraints that enforces a higher order of consistency than arc consistency. Despite the strong pruning that can be achieved, maxRPC is rarely used because existing maxRPC algorithms suffer from overheads and redundancies as they can repeatedly perform many constraint checks without triggering any value deletions. In this paper we propose and evaluate techniques that can boost the performance of maxRPC algorithms by eliminating many of these overheads and redundancies. These include the combined use of two data structures to avoid many redundant constraint checks, and the exploitation of residues to quickly verify the existence of supports. Based on these, we propose a number of closely related maxRPC algorithms. The first one, maxRPC3, has optimal O(end 3) time complexity, displays good performance when used stand-alone, but is expensive to apply during search. The second one, maxRPC3 rm, has O(en 2 d 4) time complexity, but a restricted version with O(end 4) complexity can be very efficient when used during search. The other algorithms are simple modifications of maxRPC3 rm. All algorithms have O(ed) space complexity when used stand-alone. However, maxRPC3 has O(end) space complexity when used during search, while the others retain the O(ed) complexity. Experimental results demonstrate that the resulting methods constantly outperform previous algorithms for maxRPC, often by large margins, and constitute a viable alternative to arc consistency on some problem classes. Springer Science+Business Media, LLC, 2011 Constraint propagation nationallicence Binary constraints nationallicence Local consistency nationallicence Balafoutis Thanasis Department of Information and Communication Systems Engineering, University of the Aegean, University Hill, Administration Bldg., 81100, Mytilene, Lesvos, Greece aut Paparrizou Anastasia Department of Informatics and Telecommunications Engineering, University of Western Macedonia, Karamanli & Lygeris, 50100, Kozani, FL, Greece aut Stergiou Kostas Department of Informatics and Telecommunications Engineering, University of Western Macedonia, Karamanli & Lygeris, 50100, Kozani, FL, Greece aut Walsh Toby NICTA, University of New South Wales, NSW 2052, Sydney, Australia aut Constraints Springer US; http://www.springer-ny.com 16/4(2011-10-01), 372-406 1383-7133 16:4<372 2011 16 10601 https://doi.org/10.1007/s10601-011-9110-y text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s10601-011-9110-y text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Balafoutis Thanasis Department of Information and Communication Systems Engineering, University of the Aegean, University Hill, Administration Bldg., 81100, Mytilene, Lesvos, Greece aut NATIONALLICENCE 700 1- Paparrizou Anastasia Department of Informatics and Telecommunications Engineering, University of Western Macedonia, Karamanli & Lygeris, 50100, Kozani, FL, Greece aut NATIONALLICENCE 700 1- Stergiou Kostas Department of Informatics and Telecommunications Engineering, University of Western Macedonia, Karamanli & Lygeris, 50100, Kozani, FL, Greece aut NATIONALLICENCE 700 1- Walsh Toby NICTA, University of New South Wales, NSW 2052, Sydney, Australia aut NATIONALLICENCE 773 0- Constraints Springer US; http://www.springer-ny.com 16/4(2011-10-01), 372-406 1383-7133 16:4<372 2011 16 10601 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer