Systems of distant representatives

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

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

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 space; Independent set; Graph labelings; Systems of representatives

Mathematics Subject Classification ID

68R10: Graph theory (including graph drawing) in computer science

54E35: Metric spaces, metrizability

05C78: Graph labelling (graceful graphs, bandwidth, etc.)

Related Items

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

Cites Work

• 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
• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item