The Library
Complexity of two coloring problems in cubic planar bipartite mixed graphs
Tools
Tools
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. ISSN 0166-218X
Full text not available from this repository.
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 > Mathematics Faculty of Social Sciences > Warwick Business School |
| Journal or Publication Title: | Discrete Applied Mathematics |
| Publisher: | Elsevier Science Ltd. |
| ISSN: | 0166-218X |
| Date: | 6 March 2010 |
| Volume: | Vol.158 |
| Number: | No.5 |
| Number of Pages: | 5 |
| Page Range: | pp. 592-596 |
| Identification Number: | 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 |
| URI: | http://wrap.warwick.ac.uk/id/eprint/6280 |
Data sourced from Thomson Reuters' Web of Knowledge
Actions (login required)
 |
View Item |
