Optimal-Subgraph Finding Task
Jump to navigation
Jump to search
An Optimal-Subgraph Finding Task is a subgraph finding task that is a constrained optimization task.
- Context:
- Input: a Graph [math]\displaystyle{ G = (V, E) }[/math], a Graph Edge Weight Function [math]\displaystyle{ c : E \rightarrow \mathbb{R}^+ }[/math], and a Requirement Function.
- output: an Optimal Subgraph.
- It can be solved by a Optimal-Subgraph Finding Algorithm.
- It can range from being a Minimum Cost Subgraph Finding Task to finding a Maximum Cost Subgraph Finding Task.
- Example(s):
- See: Constrained Path Optimization Task.
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.