Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:








Author, Editor

Author(s):

Wahlström, Magnus

dblp



Editor(s):

Grohe, Martin
Niedermeier, Rolf

dblp
dblp

Not MPII Editor(s):

Grohe, Martin
Niedermeier, Rolf

BibTeX cite key*:

Wahlstroem2008

Title, Booktitle

Title*:

A Tighter Bound for Counting Max-Weight Solutions to 2SAT Instances

Booktitle*:

3rd International Workshop on Parameterized and Exact Computation (IWPEC 2008)

Event, URLs

URL of the conference:

http://www.csc.uvic.ca/iwpec2008/

URL for downloading the paper:


Event Address*:

Victoria (BC), Canada

Language:

English

Event Date*
(no longer used):


Organization:


Event Start Date:

14 May 2008

Event End Date:

16 May 2008

Publisher

Name*:

Springer

URL:

http://www.springer.com/

Address*:

Berlin, DE

Type:


Vol, No, Year, pp.

Series:

Lecture Notes in Computer Science

Volume:

5018

Number:


Month:

May

Pages:

202-213

Year*:

2008

VG Wort Pages:


ISBN/ISSN:

978-3-540-79722-7

Sequence Number:


DOI:

10.1007/978-3-540-79723-4_19



Note, Abstract, ©


(LaTeX) Abstract:

We give an algorithm for counting the number of max-weight
solutions to a 2SAT formula, and improve the bound on its running time to $O(1.2377^n)$. The main source of the improvement is a refinement of the method of analysis, where we extend the concept of compound (piecewise linear) measures to multivariate measures, also allowing the optimal parameters for the measure to be found automatically. This method extension should be of independent interest.



Download
Access Level:

Public

Correlation

MPG Unit:

Max-Planck-Institut für Informatik



MPG Subunit:

Algorithms and Complexity Group

Audience:

experts only

Appearance:

MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort



BibTeX Entry:

@INPROCEEDINGS{Wahlstroem2008,
AUTHOR = {Wahlstr{\"o}m, Magnus},
EDITOR = {Grohe, Martin and Niedermeier, Rolf},
TITLE = {A Tighter Bound for Counting Max-Weight Solutions to {2SAT} Instances},
BOOKTITLE = {3rd International Workshop on Parameterized and Exact Computation (IWPEC 2008)},
PUBLISHER = {Springer},
YEAR = {2008},
VOLUME = {5018},
PAGES = {202--213},
SERIES = {Lecture Notes in Computer Science},
ADDRESS = {Victoria (BC), Canada},
MONTH = {May},
ISBN = {978-3-540-79722-7},
DOI = {10.1007/978-3-540-79723-4_19},
}


Entry last modified by Magnus Wahlström, 03/03/2009
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Magnus Wahlström
Created
02/02/2009 05:43:29 PM
Revision
0.



Editor
Magnus Wahlström



Edit Date
02/02/2009 05:43:29 PM



Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section