Some relations between neighbourhood graphs for a permutation problem

DOI10.1080/02331939108843670MaRDI QIDQ3978586zbMATH OpenOpenAlexWikidataFDO

Authors Frank Werner

Publication date 25 June 1992

Published in Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1080/02331939108843670

zbMATH Keywords

block transpositionsmaximum difference of the shortest path lengthmean dilationneighbourhood structurespermutation problems

Mathematics Subject Classification ID

Structural characterization of families of graphs (05C75) Combinatorial optimization (90C27) Programming involving graphs or networks (90C35)

Review text

The author considers some permutation problems on the set of integers \(1,\dots,m\) and analyzes the relationship between certain neighbourhood structures. These neighbourhood structures are defined by certain shifts, transpositions (including block transpositions). For some interesting special cases the maximum difference of the shortest path length in a graph with two different neighbourhood structures are determined as well as the mean dilation, when embedding respectively replacing one neighbourhood structure by the other one.

Recommendations

• scientific article; zbMATH DE number 4020829
• On the theoretical properties of swap multimoves
• scientific article; zbMATH DE number 3857124
• A study of total relative displacements of permutations in paths and cycles
• Interchanging graphs associated with sorting by transpositions

Cites work

• On the Assignment Polytope
• Structural analysis of local search heuristics in combinatorial optimization
• Zu einigen Nachbarschaftsstrukturen fiir Iterationsverfahren zur naherangsweisen Lösung spezieller Reihenfolgeprohleme

Cited in

(6)

• A comparison of heuristic algorithms for flow shop scheduling problems with setup times and limited batch size
• Neighborhoods in problems of discrete mathematics
• On the theoretical properties of swap multimoves
• The 2-neighbourhood covering problem on permutation graphs
• scientific article; zbMATH DE number 3857124 (Why is no real title available?)
• On the heuristic solution of the permutation flow shop problem by path algorithms

This page was built for publication: Some relations between neighbourhood graphs for a permutation problem

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