Minimum Cost Homomorphisms to Semicomplete Bipartite Digraphs

Details Minimum Cost Homomorphisms to Semicomplete Bipartite Digraphs Minimum Cost Homomorphisms to Semicomplete Bipartite Digraphs

2006-08-25

arxiv.org/abs/cs/0608101v1

Computer Science

Discrete Mathematics

Scientific paper

For digraphs $D$ and $H$, a mapping $f: V(D)\dom V(H)$ is a homomorphism of $D$ to $H$ if $uv\in A(D)$ implies $f(u)f(v)\in A(H).$ If, moreover, each vertex $u \in V(D)$ is associated with costs $c_i(u), i \in V(H)$, then the cost of the homomorphism $f$ is $\sum_{u\in V(D)}c_{f(u)}(u)$. For each fixed digraph $H$, we have the {\em minimum cost homomorphism problem for} $H$. The problem is to decide, for an input graph $D$ with costs $c_i(u),$ $u \in V(D), i\in V(H)$, whether there exists a homomorphism of $D$ to $H$ and, if one exists, to find one of minimum cost. Minimum cost homomorphism problems encompass (or are related to) many well studied optimization problems. We describe a dichotomy of the minimum cost homomorphism problem for semicomplete multipartite digraphs $H$. This solves an open problem from an earlier paper. To obtain the dichotomy of this paper, we introduce and study a new notion, a $k$-Min-Max ordering of digraphs.

Affiliated with

Also associated with

No associations

Rating

Minimum Cost Homomorphisms to Semicomplete Bipartite 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 Semicomplete Bipartite Digraphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Minimum Cost Homomorphisms to Semicomplete Bipartite Digraphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-111373