The Problem of Compatible Representatives
From MaRDI portal
Abstract: The purpose of this note is to attach a name to a natural class of combinatorial problems and to point out that this class includes many important special cases. We also show that a simple problem of placing nonoverlapping labels on a rectangular map is NP-complete.
Cited in
(63)- Combinatorial optimization in system configuration design
- Untangling a planar graph
- Approximate map labeling is in (n n)
- Polynomial time algorithms for three-label point labeling.
- The hardness of placing street names in a Manhattan type map
- On the complexity of submap isomorphism and maximum common submap problems
- On the complexity of clustering with relaxed size constraints in fixed dimension
- Algorithmic aspects of proportional symbol maps
- Computing orbit period in max-min algebra
- Dominating set of rectangles intersecting a straight line
- Minimum color spanning circle of imprecise points
- Who witnesses The Witness? Finding witnesses in The Witness is hard and sometimes impossible
- Dispersing and grouping points on planar segments
- Independent and hitting sets of rectangles intersecting a diagonal line: algorithms and complexity
- Systems of distant representatives in Euclidean space
- Generalised arc consistency for the AllDifferent constraint: an empirical survey
- Computing conforming partitions of orthogonal polygons with minimum stabbing number
- The complexity of reasoning with global constraints
- A practical map labeling algorithm.
- The complexity of separating points in the plane
- Approximation algorithms on consistent dynamic map labeling
- Minimum color spanning circle in imprecise setup
- On the Complexity of Clustering with Relaxed Size Constraints
- A polynomial time solution for labeling a rectilinear map
- Following a curve with the discrete Fréchet distance
- Exploring and triangulating a region by a swarm of robots
- Geometric hitting set, set cover and generalized class cover problems with half-strips in opposite directions
- Covering, hitting, piercing and packing rectangles intersecting an inclined line
- Removing local extrema from imprecise terrains
- Balanced location on a graph
- scientific article; zbMATH DE number 1154176 (Why is no real title available?)
- EFFICIENT APPROXIMATION ALGORITHMS FOR TWO-LABEL POINT LABELING
- LABELING A RECTILINEAR MAP WITH SLIDING LABELS
- LABELING POINTS WITH CIRCLES
- Independent dominating set problem revisited
- The Monotone Satisfiability Problem with Bounded Variable Appearances
- Maximum area axis-aligned square packings
- Extending Partial Orthogonal Drawings
- Extending partial orthogonal drawings
- Planar 3-SAT with a clause/variable cycle
- Matching colored points with rectangles
- Convex quadrangulations of bichromatic point sets
- Optimal binary space partitions for segments in the plane
- Partitioning Graph Drawings and Triangulated Simple Polygons into Greedily Routable Regions
- LABELING POINTS ON A SINGLE LINE
- Optimizing active ranges for consistent dynamic map labeling
- Minimum membership covering and hitting
- Covering and packing of triangles intersecting a straight line
- Covering and packing of rectilinear subdivision
- Computing coverage kernels under restricted settings
- An efficient and effective approximation algorithm for the Map Labeling Problem
- Unique assembly verification in two-handed self-assembly
- Complexity of solo chess with unlimited moves
- Minimum membership geometric set cover in the continuous setting
- On k-plane insertion into plane drawings
- On two-handed planar assembly partitioning with connectivity constraints
- On the geometric red-blue set cover problem
- Tight approximation and kernelization bounds for vertex-disjoint shortest paths
- On the complexity of minimising the moving distance for dispersing objects
- Total (restrained) domination in B_k-EPG graphs and B_k-VPG graphs
- Regular augmentation of planar graphs
- The reach of axis-aligned squares in the plane
- Matching points with rectangles and squares
This page was built for publication: The Problem of Compatible Representatives
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4018853)
