MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Wahlström, Magnusdblp
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
Conference URL::
http://www.csc.uvic.ca/iwpec2008/
Downloading URL:
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
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