Complexity Dichotomies for the Maximum Weighted Digraph Partition Problem

July 03, 2023 · The Ethereal · 🏛 arXiv.org

🔮 THE ETHEREAL: The Ethereal
Pure theory — exists on a plane beyond code

"No code URL or promise found in abstract"

Evidence collected by the PWNC Scanner

Authors Argyrios Deligkas, Eduard Eiben, Gregory Gutin, Philip R. Neary, Anders Yeo arXiv ID 2307.01109 Category cs.DM: Discrete Mathematics Cross-listed cs.DS, cs.GT, math.CO Citations 3 Venue arXiv.org Last Checked 2 months ago
Abstract
We introduce and study a new optimization problem on digraphs, termed Maximum Weighted Digraph Partition (MWDP) problem. We prove three complexity dichotomies for MWDP: on arbitrary digraphs, on oriented digraphs, and on symmetric digraphs. We demonstrate applications of the dichotomies for binary-action polymatrix games and several graph theory problems.
Community shame:
Not yet rated
📄 View on arXiv 🌐 View on ar5iv 📑 PDF 🎉 Report Code Found
Community Contributions

Found the code? Know the venue? Think something is wrong? Let us know!

📜 Similar Papers

In the same crypt — Discrete Mathematics