Efficient parallel recognition of cographs

详细信息	查看全文 | 推荐本文 |

• 作者：Stavros D. Nikolopoulos and Leonidas Palios
• 关键词：Perfect graphs ; Cographs ; Cotree ; Connected and co-connected components ; Parallel algorithms ; Parallel recognition ; Certifying algorithms
• 刊名：Discrete Applied Mathematics
• 出版年：2005
• 期刊代码：46_0166218x
• 类别：cp
• 出版时间：2005
• 卷：150
• 期：1-3
• 页码：182-215
• 文件大小：375 K

摘要

In this paper, we establish structural properties for the class of complement reducible graphs or cographs, which enable us to describe efficient parallel algorithms for recognizing cographs and for constructing the cotree of a graph if it is a cograph; if the input graph is not a cograph, both algorithms return an induced 4G1R3HN-1&_mathId=mml1&_user=10&_cdi=5629&_rdoc=14&_handle=V-WA-A-W-WC-MsSAYWA-UUA-U-AABZBZDYVU-AABBEVYZVU-CAYDDDUBV-WC-U&_acct=C000050221&_version=1&_userid=10&md5=5d719456a8f343915db818141f158776" title="Click to view the MathML source">P₄. For a graph on 4G1R3HN-1&_mathId=mml2&_user=10&_cdi=5629&_rdoc=14&_handle=V-WA-A-W-WC-MsSAYWA-UUA-U-AABZBZDYVU-AABBEVYZVU-CAYDDDUBV-WC-U&_acct=C000050221&_version=1&_userid=10&md5=694d5ffcb67fed8d7a6568b2e25c655e" title="Click to view the MathML source">n vertices and 4G1R3HN-1&_mathId=mml3&_user=10&_cdi=5629&_rdoc=14&_handle=V-WA-A-W-WC-MsSAYWA-UUA-U-AABZBZDYVU-AABBEVYZVU-CAYDDDUBV-WC-U&_acct=C000050221&_version=1&_userid=10&md5=86b0a6ae5e74de49285022d58b504944" title="Click to view the MathML source">m edges, both our cograph recognition and cotree construction algorithms run in 4">4G1R3HN-1&_mathId=mml4&_user=10&_cdi=5629&_rdoc=14&_handle=V-WA-A-W-WC-MsSAYWA-UUA-U-AABZBZDYVU-AABBEVYZVU-CAYDDDUBV-WC-U&_acct=C000050221&_version=1&_userid=10&md5=ce93ee46067de31e1264f208ea4465f4">4G1R3HN-1-R3/0?wchp=dGLbVlz-zSkWb" alt="Click to view the MathML source" align="absbottom" border="0" height=20 width=68> time and require 4G1R3HN-1&_mathId=mml5&_user=10&_cdi=5629&_rdoc=14&_handle=V-WA-A-W-WC-MsSAYWA-UUA-U-AABZBZDYVU-AABBEVYZVU-CAYDDDUBV-WC-U&_acct=C000050221&_version=1&_userid=10&md5=63100c96fa1402a4c4c8e14149c731f0" title="Click to view the MathML source">O((n+m)/logn) processors on the EREW PRAM model of computation. Our algorithms are motivated by the work of Dahlhaus (Discrete Appl. Math. 57 (1995) 29–44) and take advantage of the optimal 4G1R3HN-1&_mathId=mml6&_user=10&_cdi=5629&_rdoc=14&_handle=V-WA-A-W-WC-MsSAYWA-UUA-U-AABZBZDYVU-AABBEVYZVU-CAYDDDUBV-WC-U&_acct=C000050221&_version=1&_userid=10&md5=aecbdbea3e62d69256d98439faacbe9a" title="Click to view the MathML source">O(logn)-time computation of the co-connected components of a general graph (Theory Comput. Systems 37 (2004) 527–546) and of an optimal 4G1R3HN-1&_mathId=mml7&_user=10&_cdi=5629&_rdoc=14&_handle=V-WA-A-W-WC-MsSAYWA-UUA-U-AABZBZDYVU-AABBEVYZVU-CAYDDDUBV-WC-U&_acct=C000050221&_version=1&_userid=10&md5=3e25a53d9ed195a875c6c95ace31280d" title="Click to view the MathML source">O(logn)-time parallel algorithm for computing the connected components of a cograph, which we present. Our results improve upon the previously known linear-processor parallel algorithms for the problems (Discrete Appl. Math. 57 (1995) 29–44; J. Algorithms 15 (1993) 284–313): we achieve a better time-processor product using a weaker model of computation and we provide a certificate (an induced 4G1R3HN-1&_mathId=mml8&_user=10&_cdi=5629&_rdoc=14&_handle=V-WA-A-W-WC-MsSAYWA-UUA-U-AABZBZDYVU-AABBEVYZVU-CAYDDDUBV-WC-U&_acct=C000050221&_version=1&_userid=10&md5=a7f95eedbda956c13f87488978bc3f53" title="Click to view the MathML source">P₄) whenever our algorithms decide that the input graphs are not cographs.