arXiv Open Access 2018

The eternal dominating set problem for interval graphs

Martín Rinemberg Francisco J. Soulignac

Lihat Sumber

Abstrak

We prove that, in games in which all the guards move at the same turn, the eternal domination and the clique-connected cover numbers coincide for interval graphs. A linear algorithm for the eternal dominating set problem is obtained as a by-product.

Topik & Kata Kunci

cs.DM math.CO

Penulis (2)

Martín Rinemberg

Francisco J. Soulignac

Format Sitasi

APA MLA BibTeX

Rinemberg, M., Soulignac, F.J. (2018). The eternal dominating set problem for interval graphs. https://arxiv.org/abs/1808.09591

Akses Cepat

Lihat di Sumber

Informasi Jurnal

Tahun Terbit: 2018
Bahasa: en
Sumber Database: arXiv
Akses: Open Access ✓