Quantum Approach for Vertex Separator Problem in Directed Graphs

17/06/2022

Abstract

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 :

17/06/2022

DOI :

10.1007/978-3-031-08333-4_40

Publication link :

View publication

This project has received funding from the European Union’s Horizon 2020 research and innovation programme under grant agreement No 951821.

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