Quantum Approach for Vertex Separator Problem in Directed Graphs



The Vertex Separator Problem of a directed graph consists in finding all combinations of vertices which can disconnect the source and the terminal of the graph, these combinations are minimal if they contain only the minimal number of vertices. In this paper, we introduce a new quantum algorithm based on a movement strategy to find these separators in a quantum superposition with linear complexity. Our algorithm has been tested on small directed graphs using a real Quantum Computer made by IBM.

Type :
conference proceedings
Authors :
Ahmed Zaiou, Younès Bennani, Mohamed Hibti, Basarab Matei
Location :
IFIP International Conference on Artificial Intelligence Applications and Innovations, online and Crete, Greece
Date :
Publication link :
Our website uses cookies to give you the most optimal experience online by: measuring our audience, understanding how our webpages are viewed and improving consequently the way our website works, providing you with relevant and personalized marketing content. You have full control over what you want to activate. You can accept the cookies by clicking on the “Accept all cookies” button or customize your choices by selecting the cookies you want to activate. You can also decline all cookies by clicking on the “Decline all cookies” button. Please find more information on our use of cookies and how to withdraw at any time your consent on our privacy policy.
Accept all cookies
Decline all cookies
Privacy Policy