arXiv Open Access 2014

Polynomial-time algorithms for minimum weighted colorings of ($P_5, \bar{P}_5$)-free graphs and related graph classes

Chính T. Hoàng D. Adam Lazzarato

Lihat Sumber

Abstrak

We design an $O(n^3)$ algorithm to find a minimum weighted coloring of a ($P_5, \bar{P}_5$)-free graph. Furthermore, the same technique can be used to solve the same problem for several classes of graphs, defined by forbidden induced subgraphs, such as (diamond, co-diamond)-free graphs.

Topik & Kata Kunci

cs.DM

Penulis (2)

Chính T. Hoàng

D. Adam Lazzarato

Format Sitasi

APA MLA BibTeX

Hoàng, C.T., Lazzarato, D.A. (2014). Polynomial-time algorithms for minimum weighted colorings of ($P_5, \bar{P}_5$)-free graphs and related graph classes. https://arxiv.org/abs/1409.0893

Akses Cepat

Lihat di Sumber

Informasi Jurnal

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