QPTAS and subexponential algorithm for maximum clique on disk graphs
DOI10.4230/LIPICS.SOCG.2018.12zbMATH Open1489.68342arXiv1712.05010MaRDI QIDQ5115779FDOQ5115779
Authors: Édouard Bonnet, Panos Giannopoulos, Eun Jung Kim, Paweł Rzążewski, Florian Sikora 
Publication date: 18 August 2020
Full work available at URL: https://arxiv.org/abs/1712.05010
Recommendations
- EPTAS and Subexponential Algorithm for Maximum Clique on Disk and Unit Ball Graphs
- Computing a maximum clique in geometric superclasses of disk graphs
- Finding, hitting and packing cycles in subexponential time on unit disk graphs
- Polynomial-time approximation schemes for geometric graphs
- Polynomial-Time Approximation Schemes for Geometric Intersection Graphs
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph representations (geometric and intersection representations, etc.) (05C62)
Cites Work
- Topics in Intersection Graph Theory
- Graph Classes: A Survey
- Unit disk graphs
- Unit disk graph recognition is NP-hard
- Which problems have strongly exponential complexity?
- Complexity of approximating bounded variants of optimization problems
- Finding and counting given length cycles
- Odd cycle packing
- On six problems posed by Jarik Nešetřil
- The max clique problem in classes of string-graphs
- The clique problem in ray intersection graphs
- Sphere and dot product representations of graphs
- The number of maximal independent sets in connected graphs
- Polynomial-time approximation schemes for packing and piercing fat objects
- The clique problem in intersection graphs of ellipses and triangles
- Title not available (Why is that?)
- Polynomial-Time Approximation Schemes for Geometric Intersection Graphs
- Geometric separation and exact solutions for the parameterized independent set problem on disk graphs
- State of the union (of geometric objects)
- Approximation and Online Algorithms
- Two-query PCP with subconstant error
- Robust algorithms for restricted domains
- On forbidden induced subgraphs for unit disk graphs
- On max-clique for intersection graphs of sets and the Hadwiger-Debrunner numbers
- Graphs without short odd cycles are nearly bipartite
- Homothetic polygons and beyond: maximal cliques in intersection graphs
- Solving the stable set problem in terms of the odd cycle packing number
- On covering a set of points by disks
- QPTAS and subexponential algorithm for maximum clique on disk graphs
Cited In (13)
- EPTAS and Subexponential Algorithm for Maximum Clique on Disk and Unit Ball Graphs
- A Weakly Robust PTAS for Minimum Clique Partition in Unit Disk Graphs
- On Embeddability of Unit Disk Graphs onto Straight Lines
- Finding, hitting and packing cycles in subexponential time on unit disk graphs
- Computing a maximum clique in geometric superclasses of disk graphs
- The clique problem in intersection graphs of ellipses and triangles
- On embeddability of unit disk graphs onto straight lines
- QPTAS and subexponential algorithm for maximum clique on disk graphs
- Induced odd cycle packing number, independent sets, and chromatic number
- Finding a maximum clique in a disk graph
- Title not available (Why is that?)
- Sparse graphs with bounded induced cycle packing number have logarithmic treewidth
- Finding, hitting and packing cycles in subexponential time on unit disk graphs
This page was built for publication: QPTAS and subexponential algorithm for maximum clique on disk graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5115779)
