Approximation and inapproximability results for maximum clique of disc graphs in high dimensions

DOI10.1016/j.ipl.2007.08.005zbMath1184.68626arXivcs/0701009OpenAlexW2074892433MaRDI QIDQ2380046

Peyman Afshani, Hamed Hatami

Publication date: 24 March 2010

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/cs/0701009

zbMATH Keywords

diametercomputational geometryapproximation algorithmsdisc graphs

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Related Items (1)

Complexity and approximation of the smallest \(k\)-enclosing ball problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Line graphs, root systems, and elliptic geometry
• Iterated nearest neighbors and finding minimal polytopes
• The geometry of graphs and some of its algorithmic applications
• Finding k points with minimum diameter and related problems
• Extensions of Lipschitz mappings into a Hilbert space
• Exceptional graphs with smallest eigenvalue -2 and related problems
• Static and Dynamic Algorithms for k-Point Clustering Problems
• Fundamentals of Computation Theory

This page was built for publication: Approximation and inapproximability results for maximum clique of disc graphs in high dimensions