The optimal sequential and parallel algorithms to compute all hinge vertices on interval graphs

被引：0
|
作者：
Debashis Bera
Madhumangal Pal
Tapan K. Pal
机构：
[1] Vidyasagar University,Department of Applied Mathematics with Oceanology and Computer Programming
来源：
Korean Journal of Computational and Applied Mathematics | 2001年 / 8卷 / 2期
关键词：
68Q22; 68Q25; 68R10; Interval graph; hinge vertex; design of algorithms; analysis of algorithms; parallel algorithms;
D O I：
10.1007/BF02941967
中图分类号：
学科分类号：
摘要：
If the distance between two vertices becomes longer after the removal of a vertexu, thenu is called a hinge vertex. In this paper, a linear time sequential algorithm is presented to find all hinge vertices of an interval graph. Also, a parallel algorithm is presented which takesO(n/P + logn) time usingP processors on an EREW PRAM.
引用
收藏
页码：295 / 309
页数：14
相关论文
共 30 条
123