File Download
There are no files associated with this item.
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1007/s10878-005-1775-y
- Scopus: eid_2-s2.0-23944444496
- WOS: WOS:000231222100001
- Find via
Supplementary
- Citations:
- Appears in Collections:
Article: A combinatorial algorithm for minimum weighted colorings of claw-free perfect graphs
Title | A combinatorial algorithm for minimum weighted colorings of claw-free perfect graphs |
---|---|
Authors | |
Keywords | Algorithm Complexity Graph Coloring Network Flow Perfect Graph |
Issue Date | 2005 |
Publisher | Springer Verlag Dordrecht. The Journal's web site is located at http://springerlink.metapress.com/openurl.asp?genre=journal&issn=1382-6905 |
Citation | Journal Of Combinatorial Optimization, 2005, v. 9 n. 4, p. 331-347 How to Cite? |
Abstract | We present an O(n 5) combinatorial algorithm for the minimum weighted coloring problem on claw-free perfect graphs, which was posed by Hsu and Nemhauser in 1984. Our algorithm heavily relies on the structural descriptions of claw-free perfect graphs given by Chavátal and Sbihi and by Maffray and Reed. © 2005 Springer Science + Business Media, Inc. |
Persistent Identifier | http://hdl.handle.net/10722/156143 |
ISSN | 2023 Impact Factor: 0.9 2023 SCImago Journal Rankings: 0.370 |
ISI Accession Number ID | |
References |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Li, X | en_US |
dc.contributor.author | Zang, W | en_US |
dc.date.accessioned | 2012-08-08T08:40:34Z | - |
dc.date.available | 2012-08-08T08:40:34Z | - |
dc.date.issued | 2005 | en_US |
dc.identifier.citation | Journal Of Combinatorial Optimization, 2005, v. 9 n. 4, p. 331-347 | en_US |
dc.identifier.issn | 1382-6905 | en_US |
dc.identifier.uri | http://hdl.handle.net/10722/156143 | - |
dc.description.abstract | We present an O(n 5) combinatorial algorithm for the minimum weighted coloring problem on claw-free perfect graphs, which was posed by Hsu and Nemhauser in 1984. Our algorithm heavily relies on the structural descriptions of claw-free perfect graphs given by Chavátal and Sbihi and by Maffray and Reed. © 2005 Springer Science + Business Media, Inc. | en_US |
dc.language | eng | en_US |
dc.publisher | Springer Verlag Dordrecht. The Journal's web site is located at http://springerlink.metapress.com/openurl.asp?genre=journal&issn=1382-6905 | en_US |
dc.relation.ispartof | Journal of Combinatorial Optimization | en_US |
dc.subject | Algorithm | en_US |
dc.subject | Complexity | en_US |
dc.subject | Graph Coloring | en_US |
dc.subject | Network Flow | en_US |
dc.subject | Perfect Graph | en_US |
dc.title | A combinatorial algorithm for minimum weighted colorings of claw-free perfect graphs | en_US |
dc.type | Article | en_US |
dc.identifier.email | Zang, W:wzang@maths.hku.hk | en_US |
dc.identifier.authority | Zang, W=rp00839 | en_US |
dc.description.nature | link_to_subscribed_fulltext | en_US |
dc.identifier.doi | 10.1007/s10878-005-1775-y | en_US |
dc.identifier.scopus | eid_2-s2.0-23944444496 | en_US |
dc.identifier.hkuros | 108691 | - |
dc.relation.references | http://www.scopus.com/mlt/select.url?eid=2-s2.0-23944444496&selection=ref&src=s&origin=recordpage | en_US |
dc.identifier.volume | 9 | en_US |
dc.identifier.issue | 4 | en_US |
dc.identifier.spage | 331 | en_US |
dc.identifier.epage | 347 | en_US |
dc.identifier.isi | WOS:000231222100001 | - |
dc.publisher.place | Netherlands | en_US |
dc.identifier.scopusauthorid | Li, X=7501698796 | en_US |
dc.identifier.scopusauthorid | Zang, W=7005740804 | en_US |
dc.identifier.issnl | 1382-6905 | - |