Minimum Cost Homomorphisms to Semicomplete Bipartite Digraphs
| dc.creator | Gutin, G. | |
| dc.creator | Rafiey, A. | |
| dc.creator | Yeo, A. | |
| dc.date | 2006-08-25 | |
| dc.date.accessioned | 2026-07-07T07:20:04Z | |
| dc.date.available | 2026-07-07T07:20:04Z | |
| dc.description | 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. | |
| dc.identifier | https://arxiv.org/abs/cs/0608101 | |
| dc.identifier | http://arxiv.org/abs/cs/0608101 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/114853 | |
| dc.subject | Discrete Mathematics | |
| dc.subject | Computational Complexity | |
| dc.title | Minimum Cost Homomorphisms to Semicomplete Bipartite Digraphs | |
| dc.type | text |