Skip to main content


eCommons@Cornell

eCommons@Cornell >
College of Engineering >
Computer Science >
Computer Science Technical Reports >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1813/6282
Title: Polynomial-Time Algorithms for Permutation Groups
Authors: Furst, Merrick
Hopcroft, John E.
Luks, Eugene
Keywords: computer science
technical report
Issue Date: Oct-1980
Publisher: Cornell University
Citation: http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR80-442
Abstract: A permutation group on n letters may always be represented by a small set of generators, even though its size may be exponential in n. We show that it is practical to use such a representation since many problems such as membership testing, equality testing, and inclusion testing are decidable in polynomial time. In addition, we demonstrate that the normal closure of a subgroup can be computed in polynomial time, and that this procedure can be used to test a group for solvability. We also describe an approach to computing the intersection of two groups. The procedures and techniques have wide applicability and have recently been used to improve many graph isomorphism algorithms.
URI: http://hdl.handle.net/1813/6282
Appears in Collections:Computer Science Technical Reports

Files in This Item:

File Description SizeFormat
80-442.pdf879.72 kBAdobe PDFView/Open
80-442.ps249.75 kBPostscriptView/Open

Refworks Export

Items in eCommons are protected by copyright, with all rights reserved, unless otherwise indicated.

 

© 2014 Cornell University Library Contact Us