Inclusion relationships among permutation problems

DOI10.1016/S0166-218X(87)90078-3MaRDI QIDQ1106217zbMATH OpenFDO

Authors Daniel P. Bovet, Alessandro Panconesi

Publication date 1987

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0166-218X(87)90078-3

zbMATH Keywords

deadlock avoidancedecision probleminclusion relationshipsNP-complete problemspermutation problemserializability

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) General considerations in statistical decision theory (62C05)

Review text

Let \(X=\{x_ 1,...,x_ n\}\) be a set of n elements. A permutation problem on X is a decision problem in NP which consists of determining whether there exists an n element permutation satisfying a set of ordering constraints expressed as collections of permutations of at most k elements of X. Several well-known NP-complete problems such as cyclic ordering, betweenness, and serializability can be expressed as permutation problems. If we consider symbol preserving polynomial reductions, i.e., reductions that do not make use of additional elements, strict inclusion relationships among permutation problems can be proved. In particular, the serializability problem is shown to be included in the deadlock avoidance one.

Recommendations

• Cyclic ordering is NP-complete
• scientific article; zbMATH DE number 1617282
• On the complexity of theories of permutations
• scientific article; zbMATH DE number 3904502
• On exact algorithms for the permutation CSP

Cited in

(1)

• Remarks on ‘equivalence of stability concepts for discrete time-varying systems’

This page was built for publication: Inclusion relationships among permutation problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1106217)