Approximating 2-cliques in unit disk graphs

DOI10.1016/j.dam.2013.10.017zbMath1283.05207OpenAlexW2027230710MaRDI QIDQ2636809

Jeffrey Pattillo, Sergiy I. Butenko, Yi-Ming Wang

Publication date: 18 February 2014

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

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

zbMATH Keywords

approximation algorithmdominationclique relaxationsunit disk graph

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10) Distance in graphs (05C12) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25)

Related Items (2)

Approximating maximum diameter-bounded subgraph in unit disk graphs ⋮ Approximating Maximum Diameter-Bounded Subgraph in Unit Disk Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Identifying large robust network clusters via new compact formulations of maximum \(k\)-club problems
• Unit disk graphs
• A fast algorithm for the maximum clique problem
• On the maximum quasi-clique problem
• On clique relaxation models in network analysis
• Novel approaches for analyzing biological networks
• Clique number and ball containment number of unit ball graphs
• Clique Relaxations in Social Network Analysis: The Maximum k-Plex Problem
• Robust algorithms for restricted domains
• Domination numbers of planar graphs
• Covering random points in a unit disk
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs

This page was built for publication: Approximating 2-cliques in unit disk graphs