A faster polynomial-space algorithm for Max 2-CSP

TY - JOUR

T1 - A faster polynomial-space algorithm for Max 2-CSP

AU - Edwards, Keith

PY - 2016/5

Y1 - 2016/5

N2 - We give an algorithm for Max 2-CSP which runs in time O⋆(rm5.555) and uses polynomial space. This compares with the previous fastest published algorithm of Scott and Sorkin [15], which runs in time View the MathML sourceO⋆(r19m100)=O⋆(rm5.263). The algorithm uses the deletion-reduction depth of a graph; we also consider some of the properties of this parameter, and in particular derive a lower bound on the parameter for cubic graphs.

AB - We give an algorithm for Max 2-CSP which runs in time O⋆(rm5.555) and uses polynomial space. This compares with the previous fastest published algorithm of Scott and Sorkin [15], which runs in time View the MathML sourceO⋆(r19m100)=O⋆(rm5.263). The algorithm uses the deletion-reduction depth of a graph; we also consider some of the properties of this parameter, and in particular derive a lower bound on the parameter for cubic graphs.

KW - Max 2-CSP

KW - Deletion-reduction length

KW - Deletion depth

UR - https://www.scopus.com/pages/publications/84954271765

U2 - 10.1016/j.jcss.2015.11.013

DO - 10.1016/j.jcss.2015.11.013

M3 - Article

SN - 0022-0000

VL - 82

SP - 536

EP - 550

JO - Journal of Computer and System Sciences

JF - Journal of Computer and System Sciences

IS - 3

ER -