Quantum Algorithm for Finding a Maximum Clique in an Undirected Graph (CROSBI ID 237825)
Prilog u časopisu | izvorni znanstveni rad | međunarodna recenzija
Podaci o odgovornosti
Bojić, Alan
engleski
Quantum Algorithm for Finding a Maximum Clique in an Undirected Graph
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.
quantum computing ; quantum algorithm ; maximum clique
nije evidentirano
nije evidentirano
nije evidentirano
nije evidentirano
nije evidentirano
nije evidentirano
Podaci o izdanju
36 (2)
2012.
91-98
objavljeno
1846-3312
1846-9418
Povezanost rada
Računarstvo