Computing maximum cliques in B 2 EPG graphs

Nicolas Bousquet 1 Marc Heinrich 2
1 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
2 GOAL - Graphes, AlgOrithmes et AppLications
LIRIS - Laboratoire d'InfoRmatique en Image et Systèmes d'information
Abstract : EPG graphs, introduced by Golumbic et al. in 2009, are edge-intersection graphs of paths on an orthogonal grid. The class B k-EPG is the subclass of EPG graphs where the path on the grid associated to each vertex has at most k bends. Epstein et al. showed in 2013 that computing a maximum clique in B1-EPG graphs is polynomial. As remarked in [Heldt et al., 2014], when the number of bends is at least 4, the class contains 2-interval graphs for which computing a maximum clique is an NP-hard problem. The complexity status of the Maximum Clique problem remains open for B2 and B3-EPG graphs. In this paper, we show that we can compute a maximum clique in polynomial time in B2-EPG graphs given a representation of the graph. Moreover, we show that a simple counting argument provides a 2(k + 1)-approximation for the coloring problem on B k-EPG graphs without knowing the representation of the graph. It generalizes a result of [Epstein et al, 2013] on B1-EPG graphs (where the representation was needed).
Type de document :
Communication dans un congrès
WG: Workshop on Graph-Theoretic Concepts in Computer Science, Jun 2017, Eindhoven, Netherlands. 43rd International Workshop on Graph-Theoretic Concepts in Computer Science, 2017, Lecture Notes in Computer Science. <http://www.win.tue.nl/wg2017/>
Liste complète des métadonnées

https://hal.archives-ouvertes.fr/hal-01557335
Contributeur : Marc Heinrich <>
Soumis le : jeudi 6 juillet 2017 - 10:06:25
Dernière modification le : mardi 25 juillet 2017 - 12:45:53

Fichiers

clique-bepg_arxiv.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01557335, version 1

Citation

Nicolas Bousquet, Marc Heinrich. Computing maximum cliques in B 2 EPG graphs. WG: Workshop on Graph-Theoretic Concepts in Computer Science, Jun 2017, Eindhoven, Netherlands. 43rd International Workshop on Graph-Theoretic Concepts in Computer Science, 2017, Lecture Notes in Computer Science. <http://www.win.tue.nl/wg2017/>. <hal-01557335>

Partager

Métriques

Consultations de
la notice

105

Téléchargements du document

36