liu.seSearch for publications in DiVA

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

Extensions of the Minimum Cost Homomorphism ProblemPrimeFaces.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();
}
}
2010 (English)In: Proceedings of the 16th Annual International Computing and Combinatorics Conference, Berlin: Springer , 2010, p. 328-337Conference paper, Published paper (Refereed)
##### Abstract [en]

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

Berlin: Springer , 2010. p. 328-337
##### Series

Lecture Notes in Computer Science, ISSN 0302-9743 ; 6196
##### National Category

Computer Sciences
##### Identifiers

URN: urn:nbn:se:liu:diva-63678DOI: 10.1007/978-3-642-14031-0_36ISBN: 978-3-642-14030-3 (print)ISBN: 978-3-642-14031-0 (print)OAI: oai:DiVA.org:liu-63678DiVA, id: diva2:382145
##### Conference

16th Annual International Computing and Combinatorics Conference, COCOON 2010; Nha Trang; Viet Nam
#####

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

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

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt1130",{id:"formSmash:j_idt1130",widgetVar:"widget_formSmash_j_idt1130",multiple:true}); Available from: 2010-12-29 Created: 2010-12-29 Last updated: 2018-01-12Bibliographically approved

Assume *D* is a finite set and *R* is a finite set of functions from *D* to the natural numbers. An instance of the minimum *R*-cost homomorphism problem (*MinHom* _{R }) is a set of variables *V* subject to specified constraints together with a positive weight *c* _{vr } for each combination of *v* ∈ *V* and *r* ∈ *R*. The aim is to find a function *f*:*V* →*D* such that *f* satisfies all constraints and ∑ _{ v ∈ V } ∑ _{ r ∈ R } *c* _{vr } *r*(*f*(*v*)) is maximized.

This problem unifies well-known optimization problems such as the minimum cost homomorphism problem and the maximum solution problem, and this makes it a computationally interesting fragment of the valued CSP framework for optimization problems. We parameterize *MinHom* _{R } by *constraint languages*, i.e. sets Γ of relations that are allowed in constraints. A constraint language is called *conservative* if every unary relation is a member of it; such constraint languages play an important role in understanding the structure of constraint problems. The dichotomy conjecture for *MinHom* _{R } is the following statement: if Γ is a constraint language, then *MinHom* _{R } is either polynomial-time solvable or NP-complete. For *MinHom* the dichotomy result has been recently obtained [Takhanov, STACS, 2010] and the goal of this paper is to expand this result to the case of *MinHom* _{R } with conservative constraint language. For arbitrary *R* this problem is still open, but assuming certain restrictions on *R* we prove a dichotomy. As a consequence of this result we obtain a dichotomy for the conservative maximum solution problem

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

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