The Library
Complexity of two coloring problems in cubic planar bipartite mixed graphs
Tools
Ries, Bernard (2010) Complexity of two coloring problems in cubic planar bipartite mixed graphs. Discrete Applied Mathematics, Vol.158 (No.5). pp. 592-596. doi:10.1016/j.dam.2009.10.016 ISSN 0166-218X.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: http://dx.doi.org/10.1016/j.dam.2009.10.016
Abstract
In this note we consider two coloring problems in mixed graphs, i.e., graphs containing edges and arcs, which arise from scheduling problems where disjunctive and precedence constraints have to be taken into account. We show that they are both NP-complete in cubic planar bipartite mixed graphs, which strengthens some results of Ries and de Werra (2008)[9]. (C) 2009 Elsevier B.V. All rights reserved.
Item Type: | Journal Article | ||||
---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics | ||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Mathematics Faculty of Social Sciences > Warwick Business School |
||||
Journal or Publication Title: | Discrete Applied Mathematics | ||||
Publisher: | Elsevier Science Ltd. | ||||
ISSN: | 0166-218X | ||||
Official Date: | 6 March 2010 | ||||
Dates: |
|
||||
Volume: | Vol.158 | ||||
Number: | No.5 | ||||
Number of Pages: | 5 | ||||
Page Range: | pp. 592-596 | ||||
DOI: | 10.1016/j.dam.2009.10.016 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published | ||||
Access rights to Published version: | Restricted or Subscription Access | ||||
Funder: | Fonds national de la Recherche (Luxembourg) | ||||
Grant number: | TR-PDR BFR08-17 |
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |