• 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