https://sublinear.info/api.php?action=feedcontributions&feedformat=atom&user=74.108.164.245 2026-04-25T02:03:35Z User contributions MediaWiki 1.31.10 https://sublinear.info/index.php?title=Open_Problems:74&diff=931 2016-01-15T14:11:26Z

<p>74.108.164.245: </p> <hr /> <div>{{Header<br /> |title=Succinct Representation for Functions on Graphs<br /> |source=baltimore16<br /> |who=Robert Krauthgamer<br /> }}<br /> 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$. <br /> A naive method is to construct a table containing the value for each pair, requiring $O(|V|^2)$ space (machine words).<br /> Alternatively, one may construct a Gomory–Hu tree {{cite|GomoryH-61}}.<br /> This is a tree $T = (V,E_T,w_T)$, in which the minimum $st$-cut values are equal to those in $G$.<br /> Since $T$ is a tree, it requires only $O(|V|)$ space.<br /> <br /> 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'$. <br /> 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? The question applies both to exact and approximate computations of the function.</div>

74.108.164.245 https://sublinear.info/index.php?title=Open_Problems:74&diff=930 2016-01-15T14:10:11Z

<p>74.108.164.245: </p> <hr /> <div>{{Header<br /> |title=Succinct Representation for Functions on Graphs<br /> |source=baltimore16<br /> |who=Robert Krauthgamer<br /> }}<br /> 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$. <br /> A naive method is to construct a table containing the value for each pair, requiring $O(|V|^2)$ space (machine words).<br /> Alternatively, one may construct a Gomory–Hu tree {{cite|GomoryH-61}}.<br /> This is a tree $T = (V,E_T,w_T)$, in which the minimum $st$-cut values are equal to those in $G$.<br /> Since $T$ is a tree, it requires only $O(|V|)$ space.<br /> <br /> 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'$. <br /> 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?</div>

74.108.164.245