首页> 外文期刊>Algorithmica >Hardness and Structural Results for Half-Squares of Restricted Tree Convex Bipartite Graphs
【24h】

Hardness and Structural Results for Half-Squares of Restricted Tree Convex Bipartite Graphs

机译:约束树凸二部图半平方的硬度和结构结果

获取原文
获取原文并翻译 | 示例

摘要

Let B=(X,Y,E) be a bipartite graph. A half-square of B has one color class of B as vertex set, say X; two vertices are adjacent whenever they have a common neighbor in Y. Every planar graph is a half-square of a planar bipartite graph, namely of its subdivision. Until recently, only half-squares of planar bipartite graphs, also known as map graphs (Chen et al., in: Proceedings of the thirtieth annual ACM symposium on the theory of computing, STOC '98, pp 514-523. 10.1145/276698.276865, 1998; J ACM 49(2):127-138. 10.1145/506147.506148, 2002), have been investigated, and the most discussed problem is whether it is possible to recognize these graphs faster and simpler than Thorup's O(n120)-time algorithm (Thorup, in: Proceedings of the 39th IEEE symposium on foundations of computer science (FOCS), pp 396-405. 10.1109/SFCS.1998.743490, 1998). In this paper, we identify the first hardness case, namely that deciding if a graph is a half-square of a balanced bisplit graph is NP-complete. (Balanced bisplit graphs form a proper subclass of star convex bipartite graphs). For classical subclasses of tree convex bipartite graphs such as biconvex, convex, and chordal bipartite graphs, we give good structural characterizations of their half-squares that imply efficient recognition algorithms. As a by-product, we obtain new characterizations of unit interval graphs, interval graphs, and of strongly chordal graphs in terms of half-squares of biconvex bipartite, convex bipartite, and of chordal bipartite graphs, respectively. Good characterizations of half-squares of star convex and star biconvex bipartite graphs are also given, giving linear-time recognition algorithms for these half-squares.
机译:令B =(X,Y,E)为二部图。 B的一个半正方形具有B的一种颜色类别作为顶点集,例如X。只要两个顶点在Y中有一个公共的相邻点,两个顶点就相邻。每个平面图都是平面二部图(即其细分)的半个正方形。直到最近,平面二部图(也称为地图图)只有一半的正方形(Chen等人,在:第三十届ACM年度计算理论研讨会论文集,STOC '98,第514-523页。10.1145 / 276698.276865 ,1998; J ACM 49(2):127-138。10.1145 / 506147.506148,2002),并且讨论最多的问题是,是否有可能比Thorup的O(n120)时间更快,更简单地识别这些图。算法(Thorup,在:第39届IEEE计算机科学基础研讨会论文集(FOCS),第396-405页。10.1109/ SFCS.1998.743490,1998)。在本文中,我们确定了第一种硬度情况,即确定图是否为平衡双分裂图的半平方是NP完全的。 (平衡的双分裂图构成星形凸二部图的适当子类)。对于树凸二分图的经典子类,例如双凸,凸和弦二分图,我们给出了它们的半平方的良好结构特征,这意味着有效的识别算法。作为副产品,我们分别用双凸二分图,凸二分图和弦二分图的半平方分别获得了单位间隔图,间隔图和强弦图的新特征。还给出了星形凸和星形双凸二分图的半正方形的良好刻画,为这些半正方形给出了线性时间识别算法。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱:kefu@zhangqiaokeyan.com

京公网安备:11010802029741号 ICP备案号:京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有
  • 客服微信

  • 服务号