liu.seSearch for publications in DiVA
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Extensions of the Minimum Cost Homomorphism Problem
Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory. Linköping University, The Institute of Technology. (TCSLAB)
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]

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:VD 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

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
Available from: 2010-12-29 Created: 2010-12-29 Last updated: 2014-09-30Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Authority records BETA

Takhanov, Rustem

Search in DiVA

By author/editor
Takhanov, Rustem
By organisation
TCSLAB - Theoretical Computer Science LaboratoryThe Institute of Technology
Computer Science

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 15 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf