Approximating 2-cliques in unit disk graphs

DOI10.1016/J.DAM.2013.10.017MaRDI QIDQ2636809zbMATH OpenOpenAlexFDO

Authors Jeffrey Pattillo, Sergiy Butenko, Yiming 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 algorithmclique relaxationsdominationunit disk graph

Mathematics Subject Classification ID

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

Recommendations

• Graph-Theoretic Concepts in Computer Science
• ON TWO APPROXIMATION ALGORITHMS FOR THE CLIQUE PROBLEM
• Approximation and inapproximability results for maximum clique of disc graphs in high dimensions
• Approximating Clique and Biclique Problems
• Linear-time approximation algorithms for unit disk graphs
• A 2-approximation algorithm for the graph 2-clustering problem
• Approximation Algorithms for Domatic Partitions of Unit Disk Graphs
• 2-approximation algorithms for two graph clustering problems
• Tighter approximation bounds for minimum CDS in unit disk graphs
• Minimum clique partition in unit disk graphs

Cites work

• A fast algorithm for the maximum clique problem
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• Clique number and ball containment number of unit ball graphs
• Clique relaxations in social network analysis: the maximum k-plex problem
• Covering random points in a unit disk
• Domination numbers of planar graphs
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3214278 (Why is no real title available?)
• Identifying large robust network clusters via new compact formulations of maximum k-club problems
• Novel approaches for analyzing biological networks
• On clique relaxation models in network analysis
• On the maximum quasi-clique problem
• Robust algorithms for restricted domains
• Unit disk graphs

Cited in

(4)

• Approximation and inapproximability results for maximum clique of disc graphs in high dimensions
• Approximating maximum diameter-bounded subgraph in unit disk graphs
• Approximating maximum diameter-bounded subgraph in unit disk graphs
• Minimum clique partition in unit disk graphs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2636809)