The problem of compatible representatives

This paper attaches a name to a natural class of combinatorial problems and points out that the class includes many important special cases. One special case, a simple problem of placing nonoverlapping labels on a rectangular map, is shown to be NP-complete.

Saved in:
Bibliographic Details
Published in:SIAM journal on discrete mathematics 1992-08, Vol.5 (3), p.422-427
Main Authors: KNUTH, D. E, ARVIND RAGHUNATHAN
Format: Article
Language:English
Subjects:
Applied sciences
Computer science
Exact sciences and technology
Flows in networks. Combinatorial problems
Operational research and scientific management
Operational research. Management science
Radio communications
Semiconductor research
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:This paper attaches a name to a natural class of combinatorial problems and points out that the class includes many important special cases. One special case, a simple problem of placing nonoverlapping labels on a rectangular map, is shown to be NP-complete.
ISSN:0895-4801
1095-7146
DOI:10.1137/0405033