liu.seSearch for publications in DiVA

CiteExport$(function(){PrimeFaces.cw("TieredMenu","widget_formSmash_upper_j_idt144",{id:"formSmash:upper:j_idt144",widgetVar:"widget_formSmash_upper_j_idt144",autoDisplay:true,overlay:true,my:"left top",at:"left bottom",trigger:"formSmash:upper:exportLink",triggerEvent:"click"});}); $(function(){PrimeFaces.cw("OverlayPanel","widget_formSmash_upper_j_idt145_j_idt147",{id:"formSmash:upper:j_idt145:j_idt147",widgetVar:"widget_formSmash_upper_j_idt145_j_idt147",target:"formSmash:upper:j_idt145:permLink",showEffect:"blind",hideEffect:"fade",my:"right top",at:"right bottom",showCloseIcon:true});});

An algorithm for the sat problem for formulae of linear lengthPrimeFaces.cw("AccordionPanel","widget_formSmash_some",{id:"formSmash:some",widgetVar:"widget_formSmash_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_all",{id:"formSmash:all",widgetVar:"widget_formSmash_all",multiple:true});
function selectAll()
{
var panelSome = $(PrimeFaces.escapeClientId("formSmash:some"));
var panelAll = $(PrimeFaces.escapeClientId("formSmash:all"));
panelAll.toggle();
toggleList(panelSome.get(0).childNodes, panelAll);
toggleList(panelAll.get(0).childNodes, panelAll);
}
/*Toggling the list of authorPanel nodes according to the toggling of the closeable second panel */
function toggleList(childList, panel)
{
var panelWasOpen = (panel.get(0).style.display == 'none');
// console.log('panel was open ' + panelWasOpen);
for (var c = 0; c < childList.length; c++) {
if (childList[c].classList.contains('authorPanel')) {
clickNode(panelWasOpen, childList[c]);
}
}
}
/*nodes have styleClass ui-corner-top if they are expanded and ui-corner-all if they are collapsed */
function clickNode(collapse, child)
{
if (collapse && child.classList.contains('ui-corner-top')) {
// console.log('collapse');
child.click();
}
if (!collapse && child.classList.contains('ui-corner-all')) {
// console.log('expand');
child.click();
}
}
PrimeFaces.cw("AccordionPanel","widget_formSmash_responsibleOrgs",{id:"formSmash:responsibleOrgs",widgetVar:"widget_formSmash_responsibleOrgs",multiple:true}); 2005 (English)In: Algorithms – ESA 2005: 13th Annual European Symposium, Palma de Mallorca, Spain, October 3-6, 2005. / [ed] Gerth S. Brodal and Stefano Leonardi, Berlin/Heidelberg: Springer , 2005, Vol. 3669, p. 107-118Conference paper, Published paper (Other academic)
##### Abstract [en]

##### Place, publisher, year, edition, pages

Berlin/Heidelberg: Springer , 2005. Vol. 3669, p. 107-118
##### Series

Lecture Notes in Computer Science, ISSN 0302-9743, E-ISSN 1611-3349 ; 3669
##### National Category

Engineering and Technology
##### Identifiers

URN: urn:nbn:se:liu:diva-14398DOI: 10.1007/11561071ISBN: 978-3-540-29118-3 (print)OAI: oai:DiVA.org:liu-14398DiVA, id: diva2:23419
##### Conference

13th Annual European Symposium, Palma de Mallorca, Spain, October 3-6, 2005.
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt432",{id:"formSmash:j_idt432",widgetVar:"widget_formSmash_j_idt432",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt438",{id:"formSmash:j_idt438",widgetVar:"widget_formSmash_j_idt438",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt444",{id:"formSmash:j_idt444",widgetVar:"widget_formSmash_j_idt444",multiple:true});
Available from: 2007-04-16 Created: 2007-04-16 Last updated: 2018-02-02
##### In thesis

We present an algorithm that decides the satisfiability of a CNF formula where every variable occurs at most *k* times in time O(2N(1−c/(k+1)+O(1/k2)))" role="presentation" style="box-sizing: border-box; display: inline; line-height: normal; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; position: relative;">O(2N(1−c/(k+1)+O(1/k2)))O(2N(1−c/(k+1)+O(1/k2))) for some *c* (that is, *O*(*α* *N* ) with *α*< 2 for every fixed *k*). For *k* ≤ 4, the results coincide with an earlier paper where we achieved running times of *O*(20.1736 *N* ) for *k* = 3 and *O*(20.3472*N* ) for *k* = 4 (for *k* ≤ 2, the problem is solvable in polynomial time). For *k*>4, these results are the best yet, with running times of *O*(20.4629*N* ) for *k* = 5 and *O*(20.5408*N* ) for *k* = 6. As a consequence of this, the same algorithm is shown to run in time *O*(20.0926*L* ) for a formula of length (i.e.total number of literals) *L*. The previously best bound in terms of *L* is *O*(20.1030*L* ). Our bound is also the best upper bound for an exact algorithm for a 3satformula with up to six occurrences per variable, and a 4sat formula with up to eight occurrences per variable.

1. Algorithms, measures and upper bounds for satisfiability and related problems$(function(){PrimeFaces.cw("OverlayPanel","overlay23420",{id:"formSmash:j_idt705:0:j_idt709",widgetVar:"overlay23420",target:"formSmash:j_idt705:0:parentLink",showEvent:"mousedown",hideEvent:"mousedown",showEffect:"blind",hideEffect:"fade",appendToBody:true});});

doi
isbn
urn-nbn$(function(){PrimeFaces.cw("Tooltip","widget_formSmash_j_idt1141",{id:"formSmash:j_idt1141",widgetVar:"widget_formSmash_j_idt1141",showEffect:"fade",hideEffect:"fade",showDelay:500,hideDelay:300,target:"formSmash:altmetricDiv"});});

CiteExport$(function(){PrimeFaces.cw("TieredMenu","widget_formSmash_lower_j_idt1194",{id:"formSmash:lower:j_idt1194",widgetVar:"widget_formSmash_lower_j_idt1194",autoDisplay:true,overlay:true,my:"left top",at:"left bottom",trigger:"formSmash:lower:exportLink",triggerEvent:"click"});}); $(function(){PrimeFaces.cw("OverlayPanel","widget_formSmash_lower_j_idt1195_j_idt1197",{id:"formSmash:lower:j_idt1195:j_idt1197",widgetVar:"widget_formSmash_lower_j_idt1195_j_idt1197",target:"formSmash:lower:j_idt1195:permLink",showEffect:"blind",hideEffect:"fade",my:"right top",at:"right bottom",showCloseIcon:true});});