专利名称：GENERATING A SPARSIFIER USING GRAPH
SPANNERS
发明人：Rina Panigrahy,Mikhail Kapralov申请号：US13650145申请日：20121012
公开号：US20140104278A1公开日：20140417
专利附图：
摘要：A sparsifier is generated from a union of multiple spanners of a graph. Theedges of the sparsifier are weighted based on a measure of connectivity called robustconnectivity. The robust connectivity of a node pair is the highest edge sampling
probability at which a distance between the pair is likely to drop below a specified length.Each spanner is generated from a subgraph of the graph that is generated using adecreasing sampling probability. For the weight of each edge, a spanner is determinedwhere an estimated distance between the nodes associated with the edge is greater thana threshold distance. The sampling probability of the subgraph used to generate thespanner is an estimate of the robust connectivity of the edge. The weight of the edge isset to the inverse of the estimated robust connectivity.
申请人：MICROSOFT CORPORATION
地址：Redmond WA US
国籍：US
更多信息请下载全文后查看
因篇幅问题不能全部显示，请点此查看更多更全内容