A Note on the Complexity of a Simple Transportation Problem

DOI10.1137/0222005zbMATH Open0767.68055OpenAlexW2078969731MaRDI QIDQ4037683FDOQ4037683

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

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

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)

Cited In (8)

• Routing a vehicle of capacity greater than one
• Title not available (Why is that?)
• 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
• Title not available (Why is that?)
• 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)