Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
419590 | Discrete Applied Mathematics | 2010 | 5 Pages |
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 NPNP-complete in cubic planar bipartite mixed graphs, which strengthens some results of Ries and de Werra (2008) [9].
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
B. Ries,