EPTAS and Subexponential Algorithm for Maximum Clique on Disk and Unit Ball Graphs
- Submitting institution
-
City, University of London
- Unit of assessment
- 11 - Computer Science and Informatics
- Output identifier
- 1253
- Type
- D - Journal article
- DOI
-
10.1145/3433160
- Title of journal
- Journal of the ACM
- Article number
- 9
- First page
- -
- Volume
- 68
- Issue
- 2
- ISSN
- 0004-5411
- Open access status
- Compliant
- Month of publication
- December
- Year of publication
- 2020
- URL
-
-
- Supplementary information
-
-
- Request cross-referral to
- -
- Output has been delayed by COVID-19
- No
- COVID-19 affected output statement
- -
- Forensic science
- No
- Criminology
- No
- Interdisciplinary
- No
- Number of additional authors
-
8
- Research group(s)
-
-
- Citation count
- -
- Proposed double-weighted
- No
- Reserve for an output with double weighting
- No
- Additional information
- Output is significant as it makes progress on a long-standing and widely known open problem (for over three decades). It establishes a range of novel algorithmic as well as hardness results and discovers surprising structural properties for disk graphs that are crucial for these new algorithms. The output combines results from two papers presented at SoCG 2018 and FOCS 2018. Research informing results at SoCG was funded by EPSRC first grant ‘FptGeom’. Results from this paper have already been covered in surveys/tutorials such as 'A Tutorial on Clique Problems' in Communications and Signal Processing (Douik et al., Proc. IEEE).
- Author contribution statement
- -
- Non-English
- No
- English abstract
- -
