摘要: n this paper, we obtain an explicit formula for the total number of paths length 5 in a simple graph G. We also determine some formulae each which starts from specific vertex \(v_{i}\) and \(v_{i}-v_{j}\) in G, terms adjacency matrix with help combinatorics.
arxiv.org
sci-hub.se 参考文章(21)
Thore Husfeldt, Mikko Koivisto, Petteri Kaski, Andreas Björklund, The fast intersection transform with applications to counting paths arXiv: Data Structures and Algorithms. ,(2008)
Ioannis Koutis, Faster Algebraic Algorithms for Path and Packing Problems international colloquium on automata languages and programming. pp. 575- 586 ,(2008) , 10.1007/978-3-540-70575-8_47
Topics in algebraic graph theory Cambridge University Press. ,(2004) , 10.1017/CBO9780511529993
B. Monien, How to Find Long Paths Efficiently North-holland Mathematics Studies. ,vol. 109, pp. 239- 254 ,(1985) , 10.1016/S0304-0208(08)73110-4
Andreas Björklund, Thore Husfeldt, Petteri Kaski, Mikko Koivisto, Counting paths and packings in halves european symposium on algorithms. ,vol. 5757, pp. 578- 586 ,(2009) , 10.1007/978-3-642-04128-0_52
Ryan Williams, Finding paths of length k in time Information Processing Letters. ,vol. 109, pp. 315- 318 ,(2009) , 10.1016/J.IPL.2008.11.004
N. Alon, R. Yuster, U. Zwick, Finding and counting given length cycles Algorithmica. ,vol. 17, pp. 209- 223 ,(1997) , 10.1007/BF02523189
Songjian Lu, Fenghui Zhang, Jianer Chen, Sing-Hoi Sze, Improved algorithms for path, matching, and packing problems symposium on discrete algorithms. pp. 298- 307 ,(2007) , 10.5555/1283383.1283415
Eric T. Bax, Inclusion and exclusion algorithm for the Hamiltonian Path Problem Information Processing Letters. ,vol. 47, pp. 203- 207 ,(1993) , 10.1016/0020-0190(93)90033-6
Noga Alon, Raphy Yuster, Uri Zwick, Color-coding Proceedings of the twenty-sixth annual ACM symposium on Theory of computing - STOC '94. pp. 326- 335 ,(1994) , 10.1145/195058.195179