How to sort by walking and swapping on paths and trees

DOI10.1007/S00453-017-0282-8MaRDI QIDQ2408166zbMATHOpenAlexFDO

Authors Daniel Graf

Publication date 10 October 2017

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00453-017-0282-8

zbMATH Keywords

robot schedulingpermutation propertiesensemble motion planningphysical sortingrobot transportation problemshortest sorting walkwarehouse reorganization

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Graph theory (including graph drawing) in computer science (68R10) Searching and sorting (68P10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Nonnumerical algorithms (68W05) Artificial intelligence for robotics (68T40)

Recommendations

• How to sort by walking on a tree
• On recursive path ordering
• A sorting network on trees
• Sorting and routing on OTIS-mesh of trees
• Tree traversals and permutations
• scientific article; zbMATH DE number 3921960
• Inorder traversal of splay trees
• scientific article; zbMATH DE number 2121203
• Ordered trees and the inorder traversal
• Permutree sorting

Cites work

• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• scientific article; zbMATH DE number 219265 (Why is no real title available?)
• scientific article; zbMATH DE number 3303654 (Why is no real title available?)
• A Faster and Simpler Algorithm for Sorting Signed Permutations by Reversals
• A Note on the Complexity of a Simple Transportation Problem
• A simple derivation of edmonds' algorithm for optimum branchings
• A survey of stack-sorting disciplines
• Approximation and hardness of token swapping
• Bounds for sorting by prefix reversal
• Class Steiner trees and VLSI-design
• Efficient Solutions to Some Transportation Problems with Applications to Minimizing Robot Arm Travel
• Electronic Data Sorting
• Finding optimum branchings
• Hamilton Paths in Grid Graphs
• How to sort by walking on a tree
• INSERTION SORT is \(O(n \log n)\)
• Nonpreemptive Ensemble Motion Planning on a Tree
• Optimum branchings
• Polynomial-time algorithm for sliding tokens on trees
• Preemptive Ensemble Motion Planning on a Tree
• Routing a vehicle of capacity greater than one
• Shunting for Dummies: An Introductory Algorithmic Survey
• Sorting Using Networks of Queues and Stacks
• Sorting by placement and shift
• Swapping labeled tokens on graphs
• The complexity of finding minimum-length generator sequences

Cited in

(4)

• Efficient algorithms for sorting \(k\)-sets in bins
• Sorting on graphs by adjacent swaps using permutation groups
• Token Swapping on Trees
• How to sort by walking on a tree

This page was built for publication: How to sort by walking and swapping on paths and trees

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