Difference between revisions of "Open Problems:74"
(Small edits) |
|||
| Line 4: | Line 4: | ||
|who=Robert Krauthgamer | |who=Robert Krauthgamer | ||
}} | }} | ||
| − | + | Suppose we want to design a data structure that stores, for a given edge-weighted (undirected) graph $G = (V,E_G,w_G)$, the values of the minimum $st$-cuts for all $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 (machine words). |
Alternatively, one may construct a Gomory–Hu tree {{cite|GomoryH-61}}. | Alternatively, one may construct a Gomory–Hu tree {{cite|GomoryH-61}}. | ||
| − | This is | + | This is a tree $T = (V,E_T,w_T)$, in which the minimum $st$-cut values are equal to those in $G$. |
Since $T$ is a tree, it requires only $O(|V|)$ space. | Since $T$ is a tree, it requires only $O(|V|)$ space. | ||
| − | + | Thus for this problem, a very space-efficient data structure (perhaps even the best one) is itself a graph $G'$, and it encodes the desired values in a natural manner, just compute the same function (min $st$-cut) on $G'$. | |
| − | 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 a potentially complicated data structure outperforms a graphical encoding? |
Revision as of 14:10, 15 January 2016
| Suggested by | Robert Krauthgamer |
|---|---|
| Source | Baltimore 2016 |
| Short link | https://sublinear.info/74 |
Suppose we want to design a data structure that stores, for a given edge-weighted (undirected) graph $G = (V,E_G,w_G)$, the values of the minimum $st$-cuts for all $s,t \in V$. A naive method is to construct a table containing the value for each pair, requiring $O(|V|^2)$ space (machine words). Alternatively, one may construct a Gomory–Hu tree [GomoryH-61]. This is a tree $T = (V,E_T,w_T)$, in which the minimum $st$-cut values are equal to those in $G$. Since $T$ is a tree, it requires only $O(|V|)$ space.
Thus for this problem, a very space-efficient data structure (perhaps even the best one) is itself a graph $G'$, and it encodes the desired values in a natural manner, just compute the same function (min $st$-cut) on $G'$. But is this the case for all such functions on graphs, or is there a (natural) case where a potentially complicated data structure outperforms a graphical encoding?
