A Graph Transformational View on Reductions in NP

Authors

  • Marcus Ermler University of Bremen
  • Sabine Kuske University of Bremen
  • Melanie Luderer University of Bremen
  • Caroline von Totth University of Bremen

DOI:

https://doi.org/10.14279/tuj.eceasst.61.832

Abstract

Many decision problems in the famous and challenging complexity class NP are graph problems and can be adequately specified by polynomial graph transformation units. In this paper, we propose to model the reductions in NP by means of a special type of polynomial graph transformation units, too. Moreover, we present some first ideas how the semantic requirements of reductions including their correctness can be proved in a systematic way.

Downloads

Published

2013-06-25

How to Cite

[1]
M. Ermler, S. Kuske, M. Luderer, and C. von Totth, “A Graph Transformational View on Reductions in NP”, eceasst, vol. 61, Jun. 2013.

Issue

Vol. 61 (2013): Graph Computation Models 2012

Section

Articles

License

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.