Approximating maximum diameter-bounded subgraph in unit disk graphs
DOI10.4230/LIPICS.SOCG.2018.2zbMATH Open1489.68335OpenAlexW2798478000MaRDI QIDQ5115768FDOQ5115768
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
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
approximation algorithmsfractional Helly theoremVC-dimensionunit 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
- Title not available (Why is that?)
- Unit disk graphs
- On coloring unit disk graphs
- Title not available (Why is that?)
- On clique relaxation models in network analysis
- Novel approaches for analyzing biological networks
- Quasi-planar graphs have a linear number of edges
- Identifying large robust network clusters via new compact formulations of maximum \(k\)-club problems
- Geometric approximation algorithms
- Bounded VC-dimension implies a fractional Helly theorem
- An exact algorithm for the maximum \(k\)-club problem in an undirected graph
- Integer models and upper bounds for the 3-club problem
- Upper bounds and heuristics for the 2-club problem
- Approximating maximum diameter-bounded subgraphs
- A graph‐theoretic definition of a sociometric clique†
- On the maximum number of edges in topological graphs with no four pairwise crossing edges
- Parsimonious formulations for low-diameter clusters
- Finding large \(k\)-clubs in undirected graphs
- Covering planar graphs with a fixed number of balls
- Approximating 2-cliques in unit disk graphs
Cited In (6)
- EPTAS and Subexponential Algorithm for Maximum Clique on Disk and Unit Ball Graphs
- Approximation and inapproximability results for maximum clique of disc graphs in high dimensions
- Optimal approximation algorithms for maximum distance-bounded subgraph problems
- Approximating maximum diameter-bounded subgraphs
- Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs
- 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)
