Minimum Cost Homomorphisms to Reflexive Digraphs

Details Minimum Cost Homomorphisms to Reflexive Digraphs Minimum Cost Homomorphisms to Reflexive Digraphs

2007-08-18

arxiv.org/abs/0708.2514v2

Computer Science

Discrete Mathematics

Scientific paper

For digraphs $G$ and $H$, a homomorphism of $G$ to $H$ is a mapping $f:\ V(G)\dom V(H)$ such that $uv\in A(G)$ implies $f(u)f(v)\in A(H)$. If moreover each vertex $u \in V(G)$ is associated with costs $c_i(u), i \in V(H)$, then the cost of a homomorphism $f$ is $\sum_{u\in V(G)}c_{f(u)}(u)$. For each fixed digraph $H$, the {\em minimum cost homomorphism problem} for $H$, denoted MinHOM($H$), is the following problem. Given an input digraph $G$, together with costs $c_i(u)$, $u\in V(G)$, $i\in V(H)$, and an integer $k$, decide if $G$ admits a homomorphism to $H$ of cost not exceeding $k$. We focus on the minimum cost homomorphism problem for {\em reflexive} digraphs $H$ (every vertex of $H$ has a loop). It is known that the problem MinHOM($H$) is polynomial time solvable if the digraph $H$ has a {\em Min-Max ordering}, i.e., if its vertices can be linearly ordered by $<$ so that $i

Affiliated with

Also associated with

No associations

Rating

Minimum Cost Homomorphisms to Reflexive Digraphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Minimum Cost Homomorphisms to Reflexive Digraphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Minimum Cost Homomorphisms to Reflexive Digraphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-587256