Finding heaviest H-subgraphs in real weighted graphs, with applications
| dc.creator | Vassilevska, Virginia | |
| dc.creator | Williams, Ryan | |
| dc.creator | Yuster, Raphael | |
| dc.date | 2006-09-04 | |
| dc.date.accessioned | 2026-07-07T07:23:46Z | |
| dc.date.available | 2026-07-07T07:23:46Z | |
| dc.description | For a graph G with real weights assigned to the vertices (edges), the MAX H-SUBGRAPH problem is to find an H-subgraph of G with maximum total weight, if one exists. The all-pairs MAX H-SUBGRAPH problem is to find for every pair of vertices u,v, a maximum H-subgraph containing both u and v, if one exists. Our main results are new strongly polynomial algorithms for the all-pairs MAX H-SUBGRAPH problem for vertex weighted graphs. We also give improved algorithms for the MAX-H SUBGRAPH problem for edge weighted graphs, and various related problems, including computing the first k most significant bits of the distance product of two matrices. Some of our algorithms are based, in part, on fast matrix multiplication. | |
| dc.description | 23 pages | |
| dc.identifier | https://arxiv.org/abs/cs/0609009 | |
| dc.identifier | http://arxiv.org/abs/cs/0609009 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/116105 | |
| dc.subject | Data Structures and Algorithms | |
| dc.subject | Discrete Mathematics | |
| dc.title | Finding heaviest H-subgraphs in real weighted graphs, with applications | |
| dc.type | text |