Title :
Independent subsets search in a directed graph
Author :
Kureychik, V. ; Kazharov, A.
Abstract :
When the problems of artificial intelligence, transport logistics, design automation, building intelligent CAD, mathematical economic, sociological and other are being solved it´s necessary to solve problems of determining unrelated objects. Unrelated objects search based on different criteria can solve problems of science, technology and production effectively. The paper proposes a quantum algorithm to determine the independent subsets in a directed graph. It allows developing algorithms with polynomial complexity, and in some cases, linear and quadratic complexity.
Keywords :
computational complexity; directed graphs; quantum computing; search problems; set theory; directed graph; independent subsets search; linear complexity; polynomial complexity; quadratic complexity; quantum algorithm; Algorithm design and analysis; Buildings; Complexity theory; Design automation; Partitioning algorithms; Search problems; Vectors; directed graph; independent subsets; maximal independent subset; quantum algorithm; search tree;
Conference_Titel :
Application of Information and Communication Technologies (AICT), 2014 IEEE 8th International Conference on
Conference_Location :
Astana
Print_ISBN :
978-1-4799-4120-9
DOI :
10.1109/ICAICT.2014.7035970
