Complexity of two coloring problems in cubic planar bipartite mixed graphs
- Ries, Bernard University of Fribourg
-
2010
Published in:
- Discrete Applied Mathematics. - 2010, vol. 158, no. 5, p. 592-596
English
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].
- Faculty
- Faculté des sciences économiques et sociales et du management
- Department
- Département d'informatique
- Language
-
- English
- Classification
- Computer science and technology
- License
- License undefined
- Identifiers
-
- RERO DOC 324396
- DOI 10.1016/j.dam.2009.10.016
- Persistent URL
- https://folia.unifr.ch/unifr/documents/307706
Statistics
Document views: 43
File downloads:
- coloringmixedgraphsiii.pdf: 121