Optimal packing and covering in the plane are NP-complete. (English) Zbl 0469.68053


68Q25 Analysis of algorithms and problem complexity
52C17 Packing and covering in \(n\) dimensions (aspects of discrete geometry)
68R99 Discrete mathematics in relation to computer science
Full Text: DOI


[1] Aho, A.V.; Hopcroft, J.E.; Ullman, J.D., The design and analysis of computer algorithms, (1974), Addison-Wesley Reading, MA · Zbl 0286.68029
[2] Booth, K.S.; Lueker, G.S., Testing for the consecutive ones property, interval graphs and graph planarity using PQ-tree algorithms, J. comput. system sci., 13, 335-379, (1976) · Zbl 0367.68034
[3] Erlich, G.; Even, S.; Tarjan, R.E., Intersection graphs of curves in the plane, J. combinatorial theory ser., B21, 8-20, (1976) · Zbl 0348.05113
[4] Fowler, R.J.; Paterson, M.S.; Tanimoto, S.L., The complexity of packing and covering in the plane and related intersection graph problems, ()
[5] Garey, M.R.; Johnson, D.S., Computers and intractability: A guide to the theory of NP-completeness, (1979), W.H. Freeman San Francisco · Zbl 0411.68039
[6] Gavril, F., Some NP-complete problems on graphs, Proc. 11^{th} conf. on information sciences and systems, 91-95, (1977)
[7] Golumbic, M.C., Algorithmic graph theory and perfect graphs, (1980), Academic Press New York · Zbl 0541.05054
[8] Roberts, F.S., On the boxicity and cubicity of a graph, () · Zbl 0193.24301
[9] Rogers, C.A., Packing and covering, (1964), Cambridge University Press · Zbl 0176.51401
[10] Rose, D.J.; Tarjan, R.E.; Lueker, G.S., Algorithmic aspects of vertex elimination on graphs, SIAM J. comput., 34, 266-283, (1976) · Zbl 0353.65019
[11] Tanimoto, S.L., Covering and indexing an image subset, (), 239-245
[12] Tanimoto, S.L.; Fowler, R.J., Covering image subsets with patches, Proc. 5^{th} international conf. on pattern recognition, 835-839, (1980)
[13] Wegner, G., Eigenschaften der nerven homologisch-ein-facher familien im R^{n}, Ph.D. thesis, (1967), Göttingen
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.