A faster polynomial-space algorithm for Max 2-CSP

Keith Edwards (Lead / Corresponding author)

Research output: Contribution to journalArticle

2 Citations (Scopus)
139 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 languageEnglish
Pages (from-to)536-550
Number of pages15
JournalJournal of Computer and System Sciences
Volume82
Issue number3
Early online date10 Dec 2015
DOIs
Publication statusPublished - May 2016

Keywords

  • Max 2-CSP
  • Deletion-reduction length
  • Deletion depth

Fingerprint Dive into the research topics of 'A faster polynomial-space algorithm for Max 2-CSP'. Together they form a unique fingerprint.

Cite this