✦ LIBER ✦

The Dichotomy of Minimum Cost Homomorphism Problems for Digraphs

✍ Scribed by Hell, Pavol; Rafiey, Arash

Book ID: 118197860
Publisher: Society for Industrial and Applied Mathematics
Year: 2012
Tongue: English
Weight: 208 KB
Volume: 26
Category: Article
ISSN: 0895-4801
DOI: 10.1137/100783856

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Minimum Cost Homomorphism Dichotomy for

Minimum Cost Homomorphism Dichotomy for Oriented Cycles

✍ Gregory Gutin; Arash Rafiey; Anders Yeo 📂 Article 📅 2009 🏛 Springer Japan 🌐 English ⚖ 179 KB

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

An algorithm for the quadratic cost mini

An algorithm for the quadratic cost minimum cost flow problems

✍ Azuma Ouchi; Ikuo Kaji; Hirosaki Sawato 📂 Article 📅 1983 🏛 John Wiley and Sons 🌐 English ⚖ 482 KB

The geometry of the minimum cost problem

✍ John A Burns 📂 Article 📅 1975 🏛 Elsevier Science 🌐 English ⚖ 401 KB

Parallel algorithms for the assignment a

Parallel algorithms for the assignment and minimum-cost flow problems

✍ James B. Orlin; Clifford Stein 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 429 KB

A bounded approximation for the minimum

A bounded approximation for the minimum cost 2-sat problem

✍ Dan Gusfield; Leonard Pitt 📂 Article 📅 1992 🏛 Springer 🌐 English ⚖ 969 KB