Skip to Main content
Skip to Navigation
Toggle navigation
Sign in
Sign in
Sign in with ORCID
se connecter avec Fédération
Create account
Forgot your password?
Have you forgotten your login?
fr
en
HAL-Inria
Publications, software ... of Inria's scientists
Home
Submit
Browse all HAL
by writing date
by domain
by publication type
by collection
arXiv
last submissions
Inria publications
Search
Services
HalTools : Create your web page
Haltools : RAWEB export
X2Hal : Batch import
Find your project team / laboratory
Help
HAL Documentation
HAL - Latest developments
HAL API documentation
Add Thumbnails
Inline help Haltools
X2hal documentation
OpenAccess
Inria supporting open science
hal-00988179, version 1
Journal articles
Independent sets in (P₆, diamond)-free graphs
Raffaele Mosca
1
Details
1
Dipartimento di Scienze - Universita di Chieti-Pescara
Raffaele Mosca
1
Author
1
Dipartimento di Scienze - Universita di Chieti-Pescara
(viale Pindaro 42 - 65127 Pescara - Italy)
StructId : 95956
Universita' di Chieti-Pescara
(France)
StructId : 323471
Hide details
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.
Document type
:
Journal articles
Domain
:
Computer Science [cs]
/
Discrete Mathematics [cs.DM]
Complete list of metadata
Display
Cited literature [47 references]
Display
Hide
Download
https://hal.inria.fr/hal-00988179
Contributor :
Service Ist Inria Sophia Antipolis-Méditerranée / I3s
Connect in order to contact the contributor
Submitted on : Wednesday, May 7, 2014 - 3:36:40 PM
Last modification on : Wednesday, November 29, 2017 - 10:26:21 AM
Long-term archiving on: : Thursday, August 7, 2014 - 11:31:21 AM
File
509-4151-2-PB.pdf
Files produced by the author(s)
Identifiers
HAL Id :
hal-00988179, version 1
DOI :
10.46298/dmtcs.473
Collections
TDS-MACS
Citation
Raffaele Mosca. Independent sets in (P₆, diamond)-free graphs.
Discrete Mathematics and Theoretical Computer Science
, DMTCS, 2009, Vol. 11 no. 1 (1), pp.125--140.
⟨10.46298/dmtcs.473⟩
.
⟨hal-00988179⟩
Export
BibTeX
TEI
DC
DCterms
EndNote
Datacite
Share
Metrics
Record views
121
Files downloads
744