Kai Liu
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Kai Liu has a total of 9 co-authors. Here are the top co-authors by number of shared publications:
- Yi Zhang
College of Computer, National University of Defense Technology, Changsha 410073, China
3 shared publications Kai Lu
College of Computer, National University of Defense Technology, Changsha, China
2 shared publications- Kai Lu
College of Computer Science and Technology, National University of Defense Technology, Changsha, China
2 shared publications Xiaoping Wang
College of Computer, National University of Defense Technology, Changsha, China
2 shared publications- Xiaoping Wang
National University of Defense Technology
2 shared publications Xin Wang
College of Computer, National University of Defense Technology, Changsha, China
2 shared publications
Latest Publications
- Open Access
MapEff: An Effective Graph Isomorphism Agorithm Based on the Discrete-Time Quantum Walk
Graph isomorphism is to determine whether two graphs have the same topological structure. It plays a significant role in areas of image matching, biochemistry, and information retrieval. Quantum walk, as a novel quantum computation model, has been employed to isomorphic mapping detection to optimize the time complexity compared with a classical computation model. However, these quantum-inspired algorithms do not perform well—and even cease to work—for graphs with inherent symmetry, such as regular graphs. By analyzing the impacts of graphs symmetry on isomorphism detection, we proposed an effective graph isomorphism algorithm (MapEff) based on the discrete-time quantum walk (DTQW) to improve the accuracy of isomorphic mapping detection, especially for regular graphs. With the help of auxiliary edges, this algorithm can distinguish the symmetric nodes efficiently and, thus, deduct the qualified isomorphic mapping by rounds of selections. The experiments tested on 1585 pairs of graphs demonstrated that our algorithm has a better performance compared with other state-of-the-art algorithms.
Open AccessMapEff: An Effective Graph Isomorphism Agorithm Based on the Discrete-Time Quantum Walk
Graph isomorphism is to determine whether two graphs have the same topological structure. It plays a significant role in areas of image matching, biochemistry, and information retrieval. Quantum walk, as a novel quantum computation model, has been employed to isomorphic mapping detection to optimize the time complexity compared with a classical computation model. However, these quantum-inspired algorithms do not perform well—and even cease to work—for graphs with inherent symmetry, such as regular graphs. By analyzing the impacts of graphs symmetry on isomorphism detection, we proposed an effective graph isomorphism algorithm (MapEff) based on the discrete-time quantum walk (DTQW) to improve the accuracy of isomorphic mapping detection, especially for regular graphs. With the help of auxiliary edges, this algorithm can distinguish the symmetric nodes efficiently and, thus, deduct the qualified isomorphic mapping by rounds of selections. The experiments tested on 1585 pairs of graphs demonstrated that our algorithm has a better performance compared with other state-of-the-art algorithms.
- Open Access
Marking Vertices to Find Graph Isomorphism Mapping Based on Continuous-Time Quantum Walk
The isomorphism problem involves judging whether two graphs are topologically the same and producing structure-preserving isomorphism mapping. It is widely used in various areas. Diverse algorithms have been proposed to solve this problem in polynomial time, with the help of quantum walks. Some of these algorithms, however, fail to find the isomorphism mapping. Moreover, most algorithms have very limited performance on regular graphs which are generally difficult to deal with due to their symmetry. We propose IsoMarking to discover an isomorphism mapping effectively, based on the quantum walk which is sensitive to topological structures. Firstly, IsoMarking marks vertices so that it can reduce the harmful influence of symmetry. Secondly, IsoMarking can ascertain whether the current candidate bijection is consistent with existing bijections and eventually obtains qualified mapping. Thirdly, our experiments on 1585 pairs of graphs demonstrate that our algorithm performs significantly better on both ordinary graphs and regular graphs.
Open AccessMarking Vertices to Find Graph Isomorphism Mapping Based on Continuous-Time Quantum Walk
The isomorphism problem involves judging whether two graphs are topologically the same and producing structure-preserving isomorphism mapping. It is widely used in various areas. Diverse algorithms have been proposed to solve this problem in polynomial time, with the help of quantum walks. Some of these algorithms, however, fail to find the isomorphism mapping. Moreover, most algorithms have very limited performance on regular graphs which are generally difficult to deal with due to their symmetry. We propose IsoMarking to discover an isomorphism mapping effectively, based on the quantum walk which is sensitive to topological structures. Firstly, IsoMarking marks vertices so that it can reduce the harmful influence of symmetry. Secondly, IsoMarking can ascertain whether the current candidate bijection is consistent with existing bijections and eventually obtains qualified mapping. Thirdly, our experiments on 1585 pairs of graphs demonstrate that our algorithm performs significantly better on both ordinary graphs and regular graphs.
- 3 July 2018
- Published by Springer Nature in International Journal of Theoretical Physics
- Vol. 57 (10) , 2938-2948
An Optimized Quantum Representation for Color Digital Images
- 3 July 2018
- Published by Springer Nature in International Journal of Theoretical Physics
- Vol. 57 (10) , 2938-2948
An Optimized Quantum Representation for Color Digital Images
- 29 October 2017
- Published by Springer Nature
- p. 348-356
Reinforcement Label Propagation Algorithm Based on History Record
- 29 October 2017
- Published by Springer Nature
- p. 348-356
Reinforcement Label Propagation Algorithm Based on History Record
- 30 June 2017
- Published by Springer Nature in International Journal of Theoretical Physics
- Vol. 56 (9) , 2867-2886
Restoration for Noise Removal in Quantum Images
- 30 June 2017
- Published by Springer Nature in International Journal of Theoretical Physics
- Vol. 56 (9) , 2867-2886
Restoration for Noise Removal in Quantum Images