Independent sets in (P₆, diamond)-free graphs

Raffaele Mosca

doi:10.46298/dmtcs.473

Article

Independent sets in (P₆, diamond)-free graphs

Raffaele Mosca⁽¹⁾

(1) Dipartimento di Scienze - Universita di Chieti-Pescara

Download article

Open on HAL

Imported on

March 26, 2015

Published on

January 1, 2009

Last modified on

March 31, 2025

Volume 11

vol. 11:1

Graph and Algorithms

DOI

10.46298/dmtcs.473

License

https://about.hal.science/hal-authorisation-v1

Indicators

751

Views

807

Downloads

Independent sets in (P₆, diamond)-free graphs

Raffaele Mosca⁽¹⁾

(1) Dipartimento di Scienze - Universita di Chieti-Pescara

Abstract

We prove that on the class of (P6,diamond)-free graphs the Maximum-Weight Independent Set problem and the Minimum-Weight Independent Dominating Set problem can be solved in polynomial time.

Keywords

[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]

Cited by

Source: OpenCitations

Maximum Weight Independent Set in Graphs with no Long Claws in Quasi-Polynomial Time
Proceedings of the 56th Annual ACM Symposium on Theory of Computing
Authors : Peter Gartland , Daniel Lokshtanov , Tomáš Masařík , Marcin Pilipczuk , Michał Pilipczuk , Paweł Rzążewski
Journal reference : Volume , 2024, pp. 683-691
DOI : 10.1145/3618260.3649791

Preview

Loading PDF preview...

Article

Independent sets in (P₆, diamond)-free graphs

Raffaele Mosca⁽¹⁾

(1) Dipartimento di Scienze - Universita di Chieti-Pescara

Download article

Open on HAL

Imported on

March 26, 2015

Published on

January 1, 2009

Last modified on

March 31, 2025

Volume 11

vol. 11:1

Graph and Algorithms

DOI

10.46298/dmtcs.473

License

https://about.hal.science/hal-authorisation-v1

Indicators

751

Views

807

Downloads

Independent sets in (P₆, diamond)-free graphs

Raffaele Mosca⁽¹⁾

(1) Dipartimento di Scienze - Universita di Chieti-Pescara

Abstract

We prove that on the class of (P6,diamond)-free graphs the Maximum-Weight Independent Set problem and the Minimum-Weight Independent Dominating Set problem can be solved in polynomial time.

Keywords

[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]

Cited by

Source: OpenCitations

Maximum Weight Independent Set in Graphs with no Long Claws in Quasi-Polynomial Time
Proceedings of the 56th Annual ACM Symposium on Theory of Computing
Authors : Peter Gartland , Daniel Lokshtanov , Tomáš Masařík , Marcin Pilipczuk , Michał Pilipczuk , Paweł Rzążewski
Journal reference : Volume , 2024, pp. 683-691
DOI : 10.1145/3618260.3649791

Preview

Loading PDF preview...