Difference between revisions of "Open Problems:74"
(Small edits) |
|||
| Line 4: | Line 4: | ||
|who=Robert Krauthgamer | |who=Robert Krauthgamer | ||
}} | }} | ||
| − | Given an undirected graph $G = (V,E_G)$ with weight function $w_G$, one may wish to design a data structure to store the value of the minimum $s | + | Given an undirected graph $G = (V,E_G)$ with weight function $w_G$, one may wish to design a data structure to store the value of the minimum $s$–$t$ cut, for any $s,t \in V$. |
A naive method is to construct a table containing the value for each pair, requiring $O(|V|^2)$ space. | A naive method is to construct a table containing the value for each pair, requiring $O(|V|^2)$ space. | ||
| − | Alternatively, one may construct a | + | Alternatively, one may construct a Gomory–Hu tree {{cite|GomoryH-61}}. |
| − | This is an undirected tree $T = (V,E_T)$ with weight function $w_T$, such that the minimum $s | + | This is an undirected tree $T = (V,E_T)$ with weight function $w_T$, such that the minimum $s$–$t$ cut values from $G$ are preserved. |
Since $T$ is a tree, it requires only $O(|V|)$ space. | Since $T$ is a tree, it requires only $O(|V|)$ space. | ||
For this problem, it turns out the most space-efficient data structure is a graph which preserves the value of the function we wish to query. | For this problem, it turns out the most space-efficient data structure is a graph which preserves the value of the function we wish to query. | ||
| − | But is this the case for all such functions on graphs, or is there a (natural) case where | + | But is this the case for all such functions on graphs, or is there a (natural) case where another—potentially complicated—data structure could out-perform a graph? |
Revision as of 22:01, 12 January 2016
| Suggested by | Robert Krauthgamer |
|---|---|
| Source | Baltimore 2016 |
| Short link | https://sublinear.info/74 |
Given an undirected graph $G = (V,E_G)$ with weight function $w_G$, one may wish to design a data structure to store the value of the minimum $s$–$t$ cut, for any $s,t \in V$. A naive method is to construct a table containing the value for each pair, requiring $O(|V|^2)$ space. Alternatively, one may construct a Gomory–Hu tree [GomoryH-61]. This is an undirected tree $T = (V,E_T)$ with weight function $w_T$, such that the minimum $s$–$t$ cut values from $G$ are preserved. Since $T$ is a tree, it requires only $O(|V|)$ space.
For this problem, it turns out the most space-efficient data structure is a graph which preserves the value of the function we wish to query. But is this the case for all such functions on graphs, or is there a (natural) case where another—potentially complicated—data structure could out-perform a graph?
