18th AIAI 2022, 17 - 20 June 2022, Greece

Quantum Approach for Vertex Separator Problem in Directed Graphs

Ahmed ZAIOU, Younès BENNANI, Mohamed HIBTI, Basarab MATEI


  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.  

*** Title, author list and abstract as seen in the Camera-Ready version of the paper that was provided to Conference Committee. Small changes that may have occurred during processing by Springer may not appear in this window.