A faster polynomial-space algorithm for Max 2-CSP

Keith Edwards

doi:10.1016/j.jcss.2015.11.013

A faster polynomial-space algorithm for Max 2-CSP

Keith Edwards (Lead / Corresponding author)

Computing

Research output: Contribution to journal › Article › peer-review

2 Citations (Scopus)

227 Downloads (Pure)

Abstract

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.

Original language	English
Pages (from-to)	536-550
Number of pages	15
Journal	Journal of Computer and System Sciences
Volume	82
Issue number	3
Early online date	10 Dec 2015
DOIs	https://doi.org/10.1016/j.jcss.2015.11.013
Publication status	Published - May 2016

Keywords

Max 2-CSP
Deletion-reduction length
Deletion depth

Access to Document

10.1016/j.jcss.2015.11.013Licence: Elsevier User Licence

Author Accepted ManuscriptAccepted author manuscript, 285 KBLicence: CC BY-NC-ND

Cite this

@article{52de883738af4a3abe6d0dc67732bc35,

title = "A faster polynomial-space algorithm for Max 2-CSP",

abstract = "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.",

keywords = "Max 2-CSP, Deletion-reduction length, Deletion depth",

author = "Keith Edwards",

year = "2016",

month = may,

doi = "10.1016/j.jcss.2015.11.013",

language = "English",

volume = "82",

pages = "536--550",

journal = "Journal of Computer and System Sciences",

issn = "0022-0000",

publisher = "Academic Press Inc.",

number = "3",

}

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 - http://www.scopus.com/inward/record.url?scp=84954271765&partnerID=8YFLogxK

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 -

A faster polynomial-space algorithm for Max 2-CSP

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Edwards, Keith

Cite this

A faster polynomial-space algorithm for Max 2-CSP

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Profiles

Edwards, Keith

Cite this