Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4649488 | Discrete Mathematics | 2010 | 9 Pages |
Abstract
Given a metric dd on a permutation group GG, the corresponding weight problem is to decide whether there exists an element π∈Gπ∈G such that d(π,e)=kd(π,e)=k, for some given value kk. Here we show that this problem is NP-complete for many well-known metrics. An analogous problem in matrix groups, eigenvalue-free problem, and two related problems in permutation groups, the maximum and minimum weight problems, are also investigated in this paper.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Peter J. Cameron, Taoyang Wu,