✦ LIBER ✦

Minimum Cost Homomorphisms to Semicomplete Bipartite Digraphs

✍ Scribed by Gutin, Gregory; Rafiey, Arash; Yeo, Anders

Book ID: 118197638
Publisher: Society for Industrial and Applied Mathematics
Year: 2008
Tongue: English
Weight: 272 KB
Volume: 22
Category: Article
ISSN: 0895-4801
DOI: 10.1137/060668316

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

The Minimum Spanning Strong Subdigraph P

The Minimum Spanning Strong Subdigraph Problem for Extended Semicomplete Digraphs and Semicomplete Bipartite Digraphs

✍ Jørgen Bang-Jensen; Anders Yeo 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 148 KB

We consider the problem (minimum spanning strong subdigraph (MSSS)) of finding the minimum number of arcs in a spanning strongly connected subdigraph of a strongly connected digraph. This problem is NP-hard for general digraphs since it generalizes the Hamiltonian cycle problem. We characterize the

The Dichotomy of Minimum Cost Homomorphi

The Dichotomy of Minimum Cost Homomorphism Problems for Digraphs

✍ Hell, Pavol; Rafiey, Arash 📂 Article 📅 2012 🏛 Society for Industrial and Applied Mathematics 🌐 English ⚖ 208 KB