Systems of distant representatives

DOI10.1016/j.dam.2004.02.018zbMath1084.05059OpenAlexW1981114840MaRDI QIDQ1764814

Jan Kratochvíl, Jiří Fiala, Andrzej Proskurowski

Publication date: 22 February 2005

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2004.02.018

zbMATH Keywords

Metric spaceIndependent setGraph labelingsSystems of representatives

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Metric spaces, metrizability (54E35) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Related Items

Uniformity of Point Samples in Metric Spaces Using Gap Ratio ⋮ POINT SET DISTANCE AND ORTHOGONAL RANGE PROBLEMS WITH DEPENDENT GEOMETRIC UNCERTAINTIES ⋮ Largest and smallest convex hulls for imprecise points ⋮ Threshold-coloring and unit-cube contact representation of planar graphs ⋮ Minimum color spanning circle of imprecise points ⋮ Connectivity graphs of uncertainty regions ⋮ Uniformity of Point Samples in Metric Spaces Using Gap Ratio ⋮ Distance Constrained Labelings of Trees ⋮ Away from each other ⋮ The dispersive art gallery problem ⋮ A polynomial-time approximation scheme for the geometric unique coverage problem on unit squares ⋮ Minimum color spanning circle in imprecise setup ⋮ Minimizing the diameter of a spanning tree for imprecise points ⋮ Data imprecision under \(\lambda\)-geometry model ⋮ Dispersion in disks ⋮ Constrained \(k\)-center and movement to independence ⋮ Largest bounding box, smallest diameter, and related problems on imprecise points ⋮ Approximating Largest Convex Hulls for Imprecise Points ⋮ Approximating largest convex hulls for imprecise points ⋮ On minimum- and maximum-weight minimum spanning trees with neighborhoods ⋮ Systems of distant representatives in Euclidean space

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The clique complex and hypergraph matching
• Complement reducible graphs
• A special planar satisfiability problem and a consequence of its NP- completeness
• Systems of pairs of \(q\)-distant representatives, and graph colorings
• Labelling Graphs with a Condition at Distance 2
• Graph labeling and radio channel assignment
• Hall's theorem for hypergraphs
• Transversals of Vertex Partitions in Graphs
• On Representatives of Subsets
• The $L(2,1)$-Labeling Problem on Graphs
• Precoloring Extension III: Classes of Perfect Graphs
• An upper bound on the number of cliques in a graph
• Paths, Trees, and Flowers
• Fixed-parameter complexity of \(\lambda\)-labelings