A Note on the Complexity of a Simple Transportation Problem

DOI10.1137/0222005MaRDI QIDQ4037683zbMATH OpenOpenAlexFDO

Authors Greg N. Frederickson

Publication date 16 May 1993

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://docs.lib.purdue.edu/cgi/viewcontent.cgi?article=1688&context=cstech

zbMATH Keywords

transportation problemgraph augmentationcircular trackrobot arm motion

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• scientific article; zbMATH DE number 4016592
• scientific article; zbMATH DE number 447202
• The Minimum Spanning Tree Problem with Time Window Constraints
• A strongly polynomial algorithm for the transportation problem
• A note on the $k$-minimum spanning tree problem on circles

Cited in

(8)

• Routing a vehicle of capacity greater than one
• scientific article; zbMATH DE number 4016592 (Why is no real title available?)
• A non improving simplex algorithm for transportation problems
• Serving requests with on-line routing
• A hard dial-a-ride problem that is easy on average
• scientific article; zbMATH DE number 3932761 (Why is no real title available?)
• Better approximation ratios for the single-vehicle scheduling problems on line-shaped networks
• How to sort by walking and swapping on paths and trees

This page was built for publication: A Note on the Complexity of a Simple Transportation Problem

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