Approximating maximum diameter-bounded subgraph in unit disk graphs

DOI10.4230/LIPICS.SOCG.2018.2MaRDI QIDQ5115768zbMATH OpenOpenAlexFDO

Authors A. Karim Abu-Affash, Paz Carmi, Anil Maheshwari, Pat Morin, Michiel Smid, Shakhar Smorodinsky

Publication date 18 August 2020

Full work available at URL https://doi.org/10.4230/LIPIcs.SoCG.2018.2

zbMATH Keywords

approximation algorithmsfractional Helly theoremVC-dimensionunit disk graphsmaximum diameter-bounded subgraph

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25) Graph representations (geometric and intersection representations, etc.) (05C62)

Recommendations

• Approximating maximum diameter-bounded subgraphs
• Optimal approximation algorithms for maximum distance-bounded subgraph problems
• Optimal approximation algorithms for maximum distance-bounded subgraph problems
• EPTAS and Subexponential Algorithm for Maximum Clique on Disk and Unit Ball Graphs
• The maximum distance-d independent set problem on unit disk graphs

Cites work

• scientific article; zbMATH DE number 6118217 (Why is no real title available?)
• scientific article; zbMATH DE number 1749054 (Why is no real title available?)
• A graph‐theoretic definition of a sociometric clique†
• An exact algorithm for the maximum \(k\)-club problem in an undirected graph
• Approximating 2-cliques in unit disk graphs
• Approximating maximum diameter-bounded subgraphs
• Bounded VC-dimension implies a fractional Helly theorem
• Covering planar graphs with a fixed number of balls
• Finding large \(k\)-clubs in undirected graphs
• Geometric approximation algorithms
• Identifying large robust network clusters via new compact formulations of maximum \(k\)-club problems
• Integer models and upper bounds for the 3-club problem
• Novel approaches for analyzing biological networks
• On clique relaxation models in network analysis
• On coloring unit disk graphs
• On the maximum number of edges in topological graphs with no four pairwise crossing edges
• Parsimonious formulations for low-diameter clusters
• Quasi-planar graphs have a linear number of edges
• Unit disk graphs
• Upper bounds and heuristics for the 2-club problem

Cited in

(6)

• Optimal approximation algorithms for maximum distance-bounded subgraph problems
• EPTAS and Subexponential Algorithm for Maximum Clique on Disk and Unit Ball Graphs
• Approximating maximum diameter-bounded subgraphs
• Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs
• Approximation and inapproximability results for maximum clique of disc graphs in high dimensions
• On approximating the maximum diameter ratio of graphs

This page was built for publication: Approximating maximum diameter-bounded subgraph in unit disk graphs

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