Optimal Graph Path

An Optimal Graph Path is a graph path where no other graph path achieves a more optimal distance (according to a edge weight function and requirement function).

• Example(s):
  • a Viterbi Path.
• See: Shortest Graph Path, Longest Graph Path, Optimal Tree, Optimal Subgraph.

---

---

References

2006

• (Alon et al., 2006) ⇒ Noga Alon, Baruch Awerbuch, Yossi Azar, Niv Buchbinder, and Joseph (Seffi) Naor. (2006). “A General Approach to Online Network Optimization Problems.” In: ACM Transactions on Algorithms (TALG) Journal, 2(4). doi:10.1145/1198513.1198522
  • QUOTE: Such problems are associated with an input graph [math]\displaystyle{ G = (V, E) }[/math] (directed or undirected), a cost function [math]\displaystyle{ c : E \rightarrow \mathbb{R}^+ }[/math], and a requirement function [math]\displaystyle{ f }[/math] (to be defined for each problem separately). The goal is to find a minimum cost subgraph that satisfies the requirement function. Our model is online; that is, the requirement function is not known in advance and it is given "step by step" to the algorithm, while the input graph is known in advance.

---