Hans-Jörg Kreowski (University of Bremen) |
Sabine Kuske (University of Bremen) |
Aaron Lye (University of Bremen) |
Aljoscha Windhorst (University of Bremen) |
The complexity class NP of decision problems that can be solved nondeterministically in polynomial time is of great theoretical and practical importance where the notion of polynomial-time reductions between NP-problems is a key concept for the study of NP. As many typical NP-problems are naturally described as graph problems, they and their reductions are obvious candidates to be investigated by graph-transformational means. In this paper, we propose such a graph-transformational approach for proving the correctness of reductions between NP-problems. |
ArXived at: https://dx.doi.org/10.4204/EPTCS.374.7 | bibtex | |
Comments and questions to: eptcs@eptcs.org |
For website issues: webmaster@eptcs.org |