On limitations of transformations between combinatorial problems

From MaRDI portal





This is an interesting paper which discusses local transformations between combinatorial problems. The local replacement transformation was described by Garey and Johnson as a method of showing a problem to be NP- hard. The present authors formalize this transformation and prove its power and its relation to surface complexity. Finally, they discuss the power and limitation of a single edge transformation. This paper is well written and easy to read.











This page was built for publication: On limitations of transformations between combinatorial problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3979606)