https://scholars.lib.ntu.edu.tw/handle/123456789/558949
標題: | Three-in-a-tree in near linear time | 作者: | Lai, K.-Y. Thorup, M. HSUEH-I LU |
關鍵字: | Dynamic graph algorithm; Even hole; Graph recognition; Induced subgraph detection; Odd hole; Perfect graph; SPQR-tree; Top tree | 公開日期: | 2020 | 起(迄)頁: | 1279-1292 | 來源出版物: | Proceedings of the Annual ACM Symposium on Theory of Computing | 摘要: | The three-in-a-tree problem is to determine if a simple undirected graph contains an induced subgraph which is a tree connecting three given vertices. Based on a beautiful characterization that is proved in more than twenty pages, Chudnovsky and Seymour [Combinatorica 2010] gave the previously only known polynomial-time algorithm, running in O(mn2) time, to solve the three-in-a-tree problem on an n-vertex m-edge graph. Their three-in-a-tree algorithm has become a critical subroutine in several state-of-the-art graph recognition and detection algorithms. In this paper we solve the three-in-a-tree problem in O(mlog2 n) time, leading to improved algorithms for recognizing perfect graphs and detecting thetas, pyramids, beetles, and odd and even holes. Our result is based on a new and more constructive characterization than that of Chudnovsky and Seymour. Our new characterization is stronger than the original, and our proof implies a new simpler proof for the original characterization. The improved characterization gains the first factor n in speed. The remaining improvement is based on dynamic graph algorithms. © 2020 ACM. |
URI: | https://www.scopus.com/inward/record.url?eid=2-s2.0-85086758711&partnerID=40&md5=b597968accc9b091fb419c1b0d8ebb13 https://scholars.lib.ntu.edu.tw/handle/123456789/558949 |
DOI: | 10.1145/3357713.3384235 |
顯示於: | 資訊工程學系 |
在 IR 系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。