QPTAS and subexponential algorithm for maximum clique on disk graphs
From MaRDI portal
Publication:5115779
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)
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
Cites work
- scientific article; zbMATH DE number 772747 (Why is no real title available?)
- Approximation and Online Algorithms
- Complexity of approximating bounded variants of optimization problems
- Finding and counting given length cycles
- Geometric separation and exact solutions for the parameterized independent set problem on disk graphs
- Graph Classes: A Survey
- Graphs without short odd cycles are nearly bipartite
- Homothetic polygons and beyond: maximal cliques in intersection graphs
- Odd cycle packing
- On covering a set of points by disks
- On forbidden induced subgraphs for unit disk graphs
- On max-clique for intersection graphs of sets and the Hadwiger-Debrunner numbers
- On six problems posed by Jarik Nešetřil
- Polynomial-Time Approximation Schemes for Geometric Intersection Graphs
- Polynomial-time approximation schemes for packing and piercing fat objects
- QPTAS and subexponential algorithm for maximum clique on disk graphs
- Robust algorithms for restricted domains
- Solving the stable set problem in terms of the odd cycle packing number
- Sphere and dot product representations of graphs
- State of the union (of geometric objects)
- The clique problem in intersection graphs of ellipses and triangles
- The clique problem in ray intersection graphs
- The max clique problem in classes of string-graphs
- The number of maximal independent sets in connected graphs
- Topics in Intersection Graph Theory
- Two-query PCP with subconstant error
- Unit disk graph recognition is NP-hard
- Unit disk graphs
- Which problems have strongly exponential complexity?
Cited in
(13)- Finding a maximum clique in a disk graph
- EPTAS and Subexponential Algorithm for Maximum Clique on Disk and Unit Ball Graphs
- Sparse graphs with bounded induced cycle packing number have logarithmic treewidth
- On embeddability of unit disk graphs onto straight lines
- Finding, hitting and packing cycles in subexponential time on unit disk graphs
- A Weakly Robust PTAS for Minimum Clique Partition in Unit Disk Graphs
- Computing a maximum clique in geometric superclasses of disk graphs
- QPTAS and subexponential algorithm for maximum clique on disk graphs
- The clique problem in intersection graphs of ellipses and triangles
- Induced odd cycle packing number, independent sets, and chromatic number
- Finding, hitting and packing cycles in subexponential time on unit disk graphs
- scientific article; zbMATH DE number 1979524 (Why is no real title available?)
- On Embeddability of Unit Disk Graphs onto Straight Lines
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)
