DocumentCode :
2185019
Title :
Parallel algorithms for permutation groups and graph isomorphism
Author :
Luks, Eugene M.
fYear :
1986
fDate :
27-29 Oct. 1986
Firstpage :
292
Lastpage :
302
Abstract :
We develop parallel techniques for dealing with permutation group problems. These are most effective on the class of groups with bounded non-abelian composition factors. For this class, we place in NC problems such as membership testing, finding the center and composition factors, and, of particular significance, finding pointwise-set-stabilisers. The last has applications to instances of graph-isomorphism and we show that NC contains isomorphism-testing for vertex-colored graphs with bounded color multiplicity, a problem not long known to be in polynomial time.
Keywords :
Concurrent computing; Information science; Lagrangian functions; Linear algebra; Machinery; Parallel algorithms; Polynomials; System recovery; Testing; Vectors;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Foundations of Computer Science, 1986., 27th Annual Symposium on
Conference_Location :
Toronto, ON, Canada
ISSN :
0272-5428
Print_ISBN :
0-8186-0740-8
Type :
conf
DOI :
10.1109/SFCS.1986.39
Filename :
4568220
Link To Document :
بازگشت