×
Fowler, Robert J.; Paterson, Michael S.; Tanimoto, Steven L.

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

Inf. Process. Lett. 12, 133-137 (1981).
Page: −5 −4 −3 −2 −1 ±0 +1 +2 +3 +4 +5 Show Scanned Page
scan of Zbl 0469.68053

Cited in 145 Documents

MSC:

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

Keywords:

intersection graph; geometric algorithms; image processing; computer graphics; circuit layout; scheduling
PDF BibTeX XML Cite
\textit{R. J. Fowler} et al., Inf. Process. Lett. 12, 133--137 (1981; Zbl 0469.68053)
Full Text: DOI
  • logo of hbz
  • logo of WorldCat

References:

[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.