Quantum Algorithm for Finding a Maximum Clique in an Undirected Graph
Journal: Journal of Information and Organizational Sciences (JIOS) (Vol.36, No. 2)Publication Date: 2012-12-13
Authors : Alan Bojić;
Page : 91-98
Keywords : quantum computing; quantum algorithm; maximum clique;
Abstract
The maximum clique in an undirected graph is the largest subset of a set of graph's vertices where each pair of elements in the subset is connected. In this paper I would like to propose an algorithm for quantum computers that finds a maximum clique in an arbitrary undirected graph. An algorithm has O(|V|2|V|/2) worst case time complexity and O(2|V|/2) best case time complexity. Algorithm's space complexity for each case is O(|V|). An algorithm is based on a version of Grover's quantum algorithm for finding element in an unsorted list in which there can be an unknown number of solutions.
Other Latest Articles
- ORCHHA- THE ARCHITECTURAL HERITAGE OF MADHYA PRADESH
- THE IMPACT OF MOTORIZED VEHICLE ACTIVITY ON THE LEVEL OF AIR POLLUTION IN BALI ISLAND
- PROCESSING TECHNOLOGY AND PACKAGING MATERIALS EFFECTS ON ACCEPTABILITY, STORAGE STABILITY AND SHELF LIFE OF “AADUN” (NIGERIAN MAIZE BASED SNACKS)
- EFFECT OF COW DUNGS RATE AND SASAKAWA TECHNOLOGY ON THE PERFORMANCE OF MAIZE (ZEA MAYS) IN MUBI GUINEA SAVANNAH OF NIGERIA
- ALUMNI FROM THE INSTITUTO FEDERAL FLUMINENSE, BOM JESUS DO ITABAPOANA CAMPUS: AN ANALYSIS OF THEIR ENTRY INTO THE WORLD OF WORK
Last modified: 2020-05-04 18:12:28