liu.seSearch for publications in DiVA

CiteExport$(function(){PrimeFaces.cw("TieredMenu","widget_formSmash_upper_j_idt146",{id:"formSmash:upper:j_idt146",widgetVar:"widget_formSmash_upper_j_idt146",autoDisplay:true,overlay:true,my:"left top",at:"left bottom",trigger:"formSmash:upper:exportLink",triggerEvent:"click"});}); $(function(){PrimeFaces.cw("OverlayPanel","widget_formSmash_upper_j_idt147_j_idt149",{id:"formSmash:upper:j_idt147:j_idt149",widgetVar:"widget_formSmash_upper_j_idt147_j_idt149",target:"formSmash:upper:j_idt147: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();
}
}
PrimeFaces.cw("AccordionPanel","widget_formSmash_responsibleOrgs",{id:"formSmash:responsibleOrgs",widgetVar:"widget_formSmash_responsibleOrgs",multiple:true}); 2010 (English)In: Proceedings of the 16th Annual International Computing and Combinatorics Conference, Berlin: Springer , 2010, 328-337 p.Conference paper, Published paper (Refereed)
##### Abstract [en]

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

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

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

Computer Science
##### 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: diva2:382145
##### Conference

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

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

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

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt446",{id:"formSmash:j_idt446",widgetVar:"widget_formSmash_j_idt446",multiple:true});
Available from: 2010-12-29 Created: 2010-12-29 Last updated: 2014-09-30Bibliographically 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_idt1144",{id:"formSmash:j_idt1144",widgetVar:"widget_formSmash_j_idt1144",showEffect:"fade",hideEffect:"fade",showDelay:500,hideDelay:300,target:"formSmash:altmetricDiv"});});

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