The exact path length problem.

DOI10.1006/JAGM.2001.1201MaRDI QIDQ2777605zbMATH OpenOpenAlexFDO

Authors Esko Ukkonen, Matti Nykänen

Publication date 2002

Published in Journal of Algorithms (Search for Journal in Brave)

Full work available at URL https://semanticscholar.org/paper/651a2d3e5e3fa91b4459e29e80197e31a90ed606

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Programming involving graphs or networks (90C35)

Recommendations

• The quickest path problem
• scientific article; zbMATH DE number 3865259
• Shortest and longest path problems
• An extremal problem resulting in many paths.
• The optimal path-matching problem
• An approximation algorithm for computing longest paths.
• Simple paths with exact and forbidden lengths

Cited in

(18)

• A pseudo-polynomial algorithm for detecting minimum weighted length paths in a network
• Detectability of labeled weighted automata over monoids
• A complete axiomatization of weighted branching bisimulation
• Shortest-path-preserving rounding
• Efficient timed model checking for discrete-time systems
• Algorithms for the weight constrained shortest path problem
• Gap filling as exact path length problem
• Algorithms for finding paths with multiple constraints
• scientific article; zbMATH DE number 3865259 (Why is no real title available?)
• scientific article; zbMATH DE number 3918399 (Why is no real title available?)
• scientific article; zbMATH DE number 1052832 (Why is no real title available?)
• Simple paths with exact and forbidden lengths
• Negative-weight shortest paths and unit capacity minimum cost flow in \(\tilde{O}(m^{10/7}\log W)\) time (extended abstract)
• Time-dependent shortest path problems with penalties and limits on waiting
• scientific article; zbMATH DE number 7559494 (Why is no real title available?)
• Labeled shortest paths in digraphs with negative and positive edge weights
• State-based opacity of labeled real-time automata
• Diagnosability of labeled \(\mathfrak{D}_{\mathfrak{p}}\)-automata

This page was built for publication: The exact path length problem.

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