Editing Open Problems:74
Warning: You are not logged in. Your IP address will be publicly visible if you make any edits. If you log in or create an account, your edits will be attributed to your username, along with other benefits.
The edit can be undone.
Please check the comparison below to verify that this is what you want to do, and then save the changes below to finish undoing the edit.
| Latest revision | Your text | ||
| Line 1: | Line 1: | ||
{{Header | {{Header | ||
| + | |title=Space-Efficient Representation for Functions on Graphs | ||
|source=baltimore16 | |source=baltimore16 | ||
|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-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|GomoryHu-61}}. |
| − | This is | + | 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. | |
| − | But is this the case for all such functions on graphs, or is there a | + | But is this the case for all such functions on graphs, or is there a case where another (potentially complicated) data structure could out-perform a graph? |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
