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});});

Relating the Time Complexity of Optimization Problems in Light of the Exponential-Time HypothesisPrimeFaces.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();
}
}
Number of Authors: 4
PrimeFaces.cw("AccordionPanel","widget_formSmash_responsibleOrgs",{id:"formSmash:responsibleOrgs",widgetVar:"widget_formSmash_responsibleOrgs",multiple:true}); 2014 (English)In: Mathematical Foundations of Computer Science 2014: 39th International Symposium, MFCS 2014, Budapest, Hungary, August 25-29, 2014. Proceedings, Part II / [ed] Erzsébet Csuhaj-Varjú, Martin Dietzfelbinger, Zoltán Ésik, Springer Berlin/Heidelberg, 2014, p. 408-419Chapter in book (Refereed)
##### Abstract [en]

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

Springer Berlin/Heidelberg, 2014. p. 408-419
##### Series

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

Computer and Information Sciences
##### Identifiers

URN: urn:nbn:se:liu:diva-112902DOI: 10.1007/978-3-662-44465-8_35ISI: 000358254600035Scopus ID: 2-s2.0-84906261436ISBN: 978-3-662-44464-1 (print)ISBN: 978-3-662-44465-8 (print)OAI: oai:DiVA.org:liu-112902DiVA, id: diva2:773656
##### Conference

39th International Symposium on Mathematical Foundations of Computer Science (MFCS-2014)
#####

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: 2014-12-19 Created: 2014-12-19 Last updated: 2018-02-19Bibliographically approved
##### In thesis

Obtaining lower bounds for NP-hard problems has for a long time been an active area of research. Recent algebraic techniques introduced by Jonsson et al. (SODA 2013) show that the time complexity of the parameterized SAT(·) problem correlates to the lattice of strong partial clones. With this ordering they isolated a relation R such that SAT(R) can be solved at least as fast as any other NP-hard SAT(·) problem. In this paper we extend this method and show that such languages also exist for the max ones problem (Max-Ones(Γ)) and the Boolean valued constraint satisfaction problem over finite-valued constraint languages (VCSP(Δ)). With the help of these languages we relate Max-Ones and VCSP to the exponential time hypothesis in several different ways.

1. On Some Combinatorial Optimization Problems: Algorithms and Complexity$(function(){PrimeFaces.cw("OverlayPanel","overlay806491",{id:"formSmash:j_idt705:0:j_idt709",widgetVar:"overlay806491",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});});