scientific article; zbMATH DE number 7236416
Publication:5115779
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
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
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) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25) Graph representations (geometric and intersection representations, etc.) (05C62)
Related Items (5)
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
This page was built for publication: