On limitations of transformations between combinatorial problems (Q3979606)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 20222
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | On limitations of transformations between combinatorial problems |
scientific article; zbMATH DE number 20222 |
Statements
On limitations of transformations between combinatorial problems (English)
0 references
26 June 1992
0 references
local transformations
0 references
combinatorial problems
0 references
local replacement
0 references
surface complexity
0 references
single edge transformation
0 references
0.7682178616523743
0 references
0.7137243151664734
0 references
0.7089416980743408
0 references
0.7089415788650513
0 references
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.
0 references
