Approximating Maximum Diameter-Bounded Subgraph in Unit Disk Graphs
DOI10.4230/LIPIcs.SoCG.2018.2zbMath1489.68335OpenAlexW2798478000MaRDI QIDQ5115768
A. Karim Abu-Affash, Anil Maheshwari, Pat Morin, Paz Carmi, Shakhar Smorodinsky, Michiel H. M. Smid
Publication date: 18 August 2020
Full work available at URL: https://doi.org/10.4230/LIPIcs.SoCG.2018.2
VC-dimensionapproximation algorithmsfractional Helly theoremunit disk graphsmaximum diameter-bounded subgraph
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)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Identifying large robust network clusters via new compact formulations of maximum \(k\)-club problems
- Finding large \(k\)-clubs in undirected graphs
- Upper bounds and heuristics for the 2-club problem
- Covering planar graphs with a fixed number of balls
- On the maximum number of edges in topological graphs with no four pairwise crossing edges
- Unit disk graphs
- Quasi-planar graphs have a linear number of edges
- On coloring unit disk graphs
- An exact algorithm for the maximum \(k\)-club problem in an undirected graph
- Bounded VC-dimension implies a fractional Helly theorem
- Parsimonious formulations for low-diameter clusters
- On clique relaxation models in network analysis
- Novel approaches for analyzing biological networks
- Approximating 2-cliques in unit disk graphs
- Approximating Maximum Diameter-Bounded Subgraphs
- A graph‐theoretic definition of a sociometric clique†
- Integer models and upper bounds for the 3‐club problem
This page was built for publication: Approximating Maximum Diameter-Bounded Subgraph in Unit Disk Graphs
