On a class of intersection graphs
From MaRDI portal
Publication:6242592
arXiv1306.2498MaRDI QIDQ6242592FDOQ6242592
Mourad Baïou, Laurent Beaudou, Vincent Limouzy, Zhentao Li
Publication date: 11 June 2013
Abstract: Given a directed graph D = (V,A) we define its intersection graph I(D) = (A,E) to be the graph having A as a node-set and two nodes of I(D) are adjacent if their corresponding arcs share a common node that is the tail of at least one of these arcs. We call these graphs facility location graphs since they arise from the classical uncapacitated facility location problem. In this paper we show that facility location graphs are hard to recognize and they are easy to recognize when the graph is triangle-free. We also determine the complexity of the vertex coloring, the stable set and the facility location problems on that class.
This page was built for publication: On a class of intersection graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6242592)
