Improved lower bounds for the link length of rectilinear spanning paths in grids

DOI10.1016/S0020-0190(98)00178-1MaRDI QIDQ293479zbMATH OpenOpenAlexFDO

Authors Michael J. Collins, Bernard M. E. Moret

Publication date 9 June 2016

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL http://www.sciencedirect.com/science/article/pii/S0020019098001781?np=y

zbMATH Keywords

Hamiltonian pathlink lengthmultidimensional grids

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38)

Recommendations

• scientific article; zbMATH DE number 734472
• Settling the bound on the rectilinear link radius of a simple rectilinear polygon
• Traversing a set of points with a minimum number of turns
• Traversing a set of points with a minimum number of turns
• Improved parameterized algorithms for minimum link-length rectilinear spanning path problem

Cited in

(9)

• An improved linear edge bound for graph linkages
• Covering paths for planar point sets
• On Covering Points with Minimum Turns
• scientific article; zbMATH DE number 734472 (Why is no real title available?)
• COVERING A SET OF POINTS WITH A MINIMUM NUMBER OF TURNS
• Taming the knight's tour: minimizing turns and crossings
• Traversing a set of points with a minimum number of turns
• Improved FPT Algorithms for Rectilinear k-Links Spanning Path
• Improved parameterized algorithms for minimum link-length rectilinear spanning path problem

This page was built for publication: Improved lower bounds for the link length of rectilinear spanning paths in grids

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