Concepedia

Complexity results on restricted instances of a paint shop problem for words

Paul Bonsma, Th. Epping, Winfried Hochstättler

Discrete Applied Mathematics · 2006 · 27 citations · 7 references

DOIFull text

Open access

Concepts

References

7

Optimization, approximation, and complexity classes

Christos H. Papadimitriou, Mihalis Yannakakis · Journal of Computer and System Sciences · 1991 · 1.7K citations

, , +12

Proof verification and the hardness of approximation problems

Sanjeev Arora, Carsten Lund, Rajeev Motwani et al. · Journal of the ACM · 1998 · 1.4K citations · Full text

, , +14

Decomposition of regular matroids

Paul Seymour · Journal of Combinatorial Theory Series B · 1980 · 749 citations

, , +4

Some APX-completeness results for cubic graphs

Paola Alimonti, Viggo Kann · Theoretical Computer Science · 2000 · 364 citations

, , +9

The matroids with the max-flow min-cut property

Paul Seymour · Journal of Combinatorial Theory Series B · 1977 · 226 citations

, , +11