Concepedia

A short note on the approximability of the maximum leaves spanning tree problem

Giulia Galbiati, Francesco Maffioli, Angelo Morzenti

Information Processing Letters · 1994 · 84 citations · 7 references

DOI

Concepts

References

7

Approximation algorithms for combinatorial problems

David S. Johnson · Journal of Computer and System Sciences · 1974 · 2.2K citations

, , +12

Self-stabilizing systems in spite of distributed control

Edsger W. Dijkstra · Communications of the ACM · 1974 · 2.1K citations · Full text

, , +17

Optimization, approximation, and complexity classes

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

, , +12

Proof verification and hardness of approximation problems

Sanjeev Arora, Carsten Lund, R. Motwani et al. · 1992 · 744 citations

, , +16

Probabilistic checking of proofs; a new characterization of NP

Sanjeev Arora · 1992 · 278 citations

, , +16