O(n2.5) time algorithms for the subgraph homeomorphism problem on trees |
| |
| Institution: | 1. Department of Mathematics, Technical University of Darmstadt, Schlossgartenstr. 7, 64289 Darmstadt, Germany;2. Department of Pure Mathematics, University of Leeds, Leeds LS2 9JT, United Kingdom;3. Vakgroep Wiskunde: Analysis, Logic and Discrete Mathematics, Ghent University, Krijgslaan 281 – Gebouw S8, 9000 Ghent, Belgium;1. Faculty of Informatics, Masaryk University, Brno, Czechia;2. Theoretical Computer Science, Department of Computer Science, RWTH Aachen University, Aachen, Germany;1. School of Computer Science and Technology, Harbin Institute of Technology, Harbin, Heilongjiang, 150000, PR China;2. Department of Computer Science, Georgia State University, Atlanta, GA, 30303, USA;1. Department of Earth and Environmental Sciences, University of Waterloo, Waterloo, Ontario N2L 3G1, Canada;2. Beijing SHRIMP Center, Institute of Geology, Chinese Academy of Geological Sciences, Beijing 100037, China;3. School of Resources and Environment, Hefei University of Technology, Hefei 230026, China;4. State Key Laboratory of Ore Deposit Geochemistry, Institute of Geochemistry, Chinese Academy of Sciences, Guiyang 550002, China |
| |
| Abstract: | The complexity of the subgraph homeomorphism problems have been open. We show O(n2.5) time algorithms when the problems are restricted to trees, directed or undirected. The algorithm can be applied to the subtree isomorphism problem for unrooted trees with the same complexity, and improves over Reyner's O(n3.5) algorithm for the subtree isomorphism problem. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
