Approaches to unweighted and undirected graph cut sparsification
| dc.contributor.advisor | Dougherty, John P. | |
| dc.contributor.author | Do, Tung | |
| dc.date.accessioned | 2023-12-04T17:40:50Z | |
| dc.date.available | 2023-12-04T17:40:50Z | |
| dc.date.issued | 2023 | |
| dc.description.abstract | Graph sparsification is a type of graph algorithm that approximates a dense graph G by a sparse graph G’, where G’ has fewer edges. The motivation for graph sparsification is that we can perform computation on G’ to derive results with regard to G with much fewer computational resources. In other words, G’ is similar enough to G that computation results of one can be used to approximate those of the other. In this paper, we examine different approaches to cut sparsification. Cut sparsification is one type of sparsification where the sparsified graph G’ should have cuts within certain bounds of the corresponding cuts in the original graph G. There are two cut sparsification algorithms that we examine in this paper: namely uniform sampling and non-uniform sampling. As their names suggest, uniform sampling means that each edge is sampled with the same probability, whereas non-uniform sampling means that each edge is sampled with a different probability. In general, uniform sampling has better asymptotic than non-uniform sampling because each edge is treated indiscriminately. However, non-uniform sampling can reduce a bigger number of edges than uniform sampling in certain cases of dense graph. | |
| dc.description.sponsorship | Haverford College. Department of Computer Science | |
| dc.identifier.uri | http://hdl.handle.net/10066/50040 | |
| dc.language.iso | eng | |
| dc.rights.access | Tri-College users only | |
| dc.rights.uri | http://creativecommons.org/licenses/by-nc/4.0/ | |
| dc.title | Approaches to unweighted and undirected graph cut sparsification | |
| dc.type | Thesis |