高级检索
Given an arbitrary graph G, can you find a sparse graph that approximates G in some sense? We will survey a beautiful line of work, starting with the celebrated notion of cut-approximator in the works of Karger and Benczur-Karger. Intuitively, one tries to approximate the "connectedness" of a given graph. As a special case, if one tries to approximate a complete graph with a d-regular graph for a constant d, such sparsifiers are known as the expander graphs, and it has found applications in networking, coding theory, analysis of algorithms and many more . Besides expanders, we will also discuss a powerful generalization of cut-approximator known as spectral approximations. It turns out that one can find spectral approximations for every weighted graph very efficiently, and this has been a useful and versatile (algorithmic) primitive for many problems in graph theory and beyond.
图稀疏化
刘景铖