A Linear Algorithm for Minimum Dominator Colorings of Orientations of Paths

June 11, 2019 · The Ethereal · 🏛 Engineering and Applied Science Letters

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

"Last commit was 5.0 years ago (≥5 year threshold)"

Evidence collected by the PWNC Scanner

Repo contents: LICENSE, MDC-path.py, README.md

Authors Michael Cary arXiv ID 1906.04523 Category cs.DM: Discrete Mathematics Cross-listed cs.DS, math.CO Citations 1 Venue Engineering and Applied Science Letters Repository https://github.com/cat-astrophic/MDC-orientations_of_paths/ Last Checked 5 months ago
Abstract
In this paper we present an algorithm for finding a minimum dominator coloring of orientations of paths. To date this is the first algorithm for dominator colorings of digraphs in any capacity. We prove that the algorithm always provides a minimum dominator coloring of an oriented path and show that it runs in $\mathcal{O}(n)$ time. The algorithm is available at https://github.com/cat-astrophic/MDC-orientations_of_paths/.
Community shame:
Not yet rated
📄 View on arXiv 🌐 View on ar5iv 📑 PDF 💻 Repository 🎉 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