Homothetic Polygons and Beyond: Intersection Graphs, Recognition, and Maximum Clique
Homothetic Polygons and Beyond: Intersection Graphs, Recognition, and Maximum Clique
复制标题
相似多边形及其他：交集图、识别和最大团
DOI：
--
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Joshua Terhaar
中科院分区：
文献类型：
--
作者：
V. Brimkov;Konstanty Junosza;Sean Kafer;Jan Kratochvíl;M. Pergel;Paweł Rzaͅżewski;Matthew Szczepankiewicz;Joshua Terhaar
我们研究平面凸集交集类中的派系问题。已知该问题在凸集交集图和直线段交集图中是 NP 完全问题，但在拟似三角形交集图中可在多项式时间内求解。我们扩展了后一个结果，表明对于
We study the Clique problem in classes of intersection graphs of convex sets in the plane. The problem is known to be NP-complete in convex-set intersection graphs and straight-line-segment intersection graphs, but solvable in polynomial time in intersection graphs of homothetic triangles. We extend the latter result by showing that for