Finding heaviest H-subgraphs in real weighted graphs, with applications

Details Finding heaviest H-subgraphs in real weighted graphs, with applications Finding heaviest H-subgraphs in real weighted graphs, with applications

2006-09-04

arxiv.org/abs/cs/0609009v1

Computer Science

Data Structures and Algorithms

23 pages

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Finding heaviest H-subgraphs in real weighted graphs, with applications does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Finding heaviest H-subgraphs in real weighted graphs, with applications, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Finding heaviest H-subgraphs in real weighted graphs, with applications will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-727026