Article ID Journal Published Year Pages File Type
4649488 Discrete Mathematics 2010 9 Pages PDF
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.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,