Publication:5115779
From MaRDI portal
DOI10.4230/LIPIcs.SoCG.2018.12zbMath1489.68342arXiv1712.05010MaRDI QIDQ5115779
Paweł Rzążewski, Panos Giannopoulos, Eun Jung Kim, Édouard Bonnet, Florian Sikora
Publication date: 18 August 2020
Full work available at URL: https://arxiv.org/abs/1712.05010
68Q25: Analysis of algorithms and problem complexity
68R10: Graph theory (including graph drawing) in computer science
68U05: Computer graphics; computational geometry (digital and algorithmic aspects)
05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
68W25: Approximation algorithms
05C62: Graph representations (geometric and intersection representations, etc.)
Related Items
Unnamed Item, On Embeddability of Unit Disk Graphs onto Straight Lines, Computing a maximum clique in geometric superclasses of disk graphs, On embeddability of unit disk graphs onto straight lines, Induced odd cycle packing number, independent sets, and chromatic number
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The clique problem in ray intersection graphs
- Sphere and dot product representations of graphs
- Finding and counting given length cycles
- On forbidden induced subgraphs for unit disk graphs
- Unit disk graphs
- The max clique problem in classes of string-graphs
- Graphs without short odd cycles are nearly bipartite
- Unit disk graph recognition is NP-hard
- Which problems have strongly exponential complexity?
- Homothetic polygons and beyond: maximal cliques in intersection graphs
- The clique problem in intersection graphs of ellipses and triangles
- On subexponential and FPT-time inapproximability
- Complexity of approximating bounded variants of optimization problems
- Odd cycle packing
- Solving the stable set problem in terms of the odd cycle packing number
- Two-query PCP with subconstant error
- The number of maximal independent sets in connected graphs
- Topics in Intersection Graph Theory
- Graph Classes: A Survey
- Robust algorithms for restricted domains
- On Max-Clique for intersection graphs of sets and the Hadwiger-Debrunner numbers
- Polynomial-time approximation schemes for packing and piercing fat objects
- Geometric separation and exact solutions for the parameterized independent set problem on disk graphs
- Polynomial-Time Approximation Schemes for Geometric Intersection Graphs
- Approximation and Online Algorithms