scientific article; zbMATH DE number 7236416

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.

zbMATH Keywords

computational complexitymaximum cliquedisk graph

Mathematics Subject Classification ID

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)

On Embeddability of Unit Disk Graphs onto Straight Lines ⋮ On embeddability of unit disk graphs onto straight lines ⋮ Induced odd cycle packing number, independent sets, and chromatic number ⋮ Computing a maximum clique in geometric superclasses of disk graphs ⋮ Unnamed Item

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: