https://scholars.lib.ntu.edu.tw/handle/123456789/632492
標題: | Blazing a Trail via Matrix Multiplications: A Faster Algorithm for Non-Shortest Induced Paths | 作者: | Chiu Y.-C HSUEH-I LU |
關鍵字: | Dynamic data structure; Induced path; Induced subgraph; Non-shortest path | 公開日期: | 2022 | 卷: | 219 | 來源出版物: | Leibniz International Proceedings in Informatics, LIPIcs | 摘要: | For vertices u and v of an n-vertex graph G, a uv-trail of G is an induced uv-path of G that is not a shortest uv-path of G. Berger, Seymour, and Spirkl [Discrete Mathematics 2021] gave the previously only known polynomial-time algorithm, running in O(n18) time, to either output a uv-trail of G or ensure that G admits no uv-trail. We reduce the complexity to the time required to perform a poly-logarithmic number of multiplications of n2 × n2 Boolean matrices, leading to a largely improved O(n4.75)-time algorithm. © Yung-Chung Chiu and Hsueh-I Lu. |
URI: | https://www.scopus.com/inward/record.uri?eid=2-s2.0-85127116851&doi=10.4230%2fLIPIcs.STACS.2022.23&partnerID=40&md5=0e14e6a463f4ceb43ed7800eee19a3c2 https://scholars.lib.ntu.edu.tw/handle/123456789/632492 |
ISSN: | 18688969 | DOI: | 10.4230/LIPIcs.STACS.2022.23 | SDG/關鍵字: | Matrix algebra; Polynomial approximation; Discrete mathematics; Dynamic data structure; Fast algorithms; Graph G; Induced paths; Induced subgraphs; MAtrix multiplication; N-vertex graph; Non-short path; Short-path; Graph theory |
顯示於: | 資訊工程學系 |
在 IR 系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。