Minimum Cost Paths in Periodic Graphs

DOI10.1137/S0097539792234378MaRDI QIDQ4857594zbMATH OpenOpenAlexFDO

Authors Franz Höfting, Egon Wanke

Publication date 9 June 1996

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

Full work available at URL https://doi.org/10.1137/s0097539792234378

zbMATH Keywords

infinite homogeneous graphminimum cost pathsperiodic graphstatic graph

Mathematics Subject Classification ID

Distance in graphs (05C12) Paths and cycles (05C38) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Integer programming (90C10)

Recommendations

• scientific article; zbMATH DE number 437576
• Minimum Time and Minimum Cost-Path Problems in Street Networks with Periodic Traffic Lights
• Polynomial-Time Analysis of Toroidal Periodic Graphs
• A strongly polynomial time algorithm for the shortest path problem on coherent planar periodic graphs
• Polynomial time analysis of toroidal periodic graphs

Cited in

(13)

• Powers of matrices over an extremal algebra with applications to periodic graphs
• scientific article; zbMATH DE number 437576 (Why is no real title available?)
• scientific article; zbMATH DE number 3871422 (Why is no real title available?)
• Velocity polytopes of periodic graphs and a no-go theorem for digital physics
• scientific article; zbMATH DE number 17635 (Why is no real title available?)
• Minimum Time and Minimum Cost-Path Problems in Street Networks with Periodic Traffic Lights
• Periodic and non-periodic min-max equations
• Polynomial time analysis of toroidal periodic graphs
• A strongly polynomial time algorithm for the shortest path problem on coherent planar periodic graphs
• Polynomial-Time Analysis of Toroidal Periodic Graphs
• Minimum cost path in a huge graph
• Infinite precedence graphs for consistency verification in P-time event graphs
• Radiocolorings in periodic planar graphs: PSPACE-completeness and efficient approximations for the optimal range of frequencies

This page was built for publication: Minimum Cost Paths in Periodic Graphs

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