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.
Recommendations
Cites work
- ``Global graph problems tend to be intractable
- Communication complexity
- scientific article; zbMATH DE number 3664335 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- Node-Deletion NP-Complete Problems
- Some simplified NP-complete graph problems
Cited in
(2)
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)