This 23-page monograph is based on two preliminary papers published in the proceedings of relevant conferences. The H-subgraph problem starts with given graphs G and H, and asks if there is a subgraph in G that is isomorphic to H. The extension here is to provide improved algorithms that start with a real weighted graph G, and find, if it exists, an H-subgraph with the largest total weight. Several applications are also addressed with improved results, and four open questions are posed.
An effective introduction presents a key definition and preliminary discussion, and states the key theorems that are proved later. The second section provides results based on dominance computations that support later results. This section also gives two applications, to the “most significant bits of a distance product” and to “buyer-seller stable matching.” The third and fourth sections consider separately the issues associated with weighted vertices and weighted edges. Here, most of the key theorems are proved. The fifth section provides applications to rainbow H-subgraphs and to monochromatic H-subgraphs.
This monograph is carefully organized, and the authors do justice to the mathematical and computational complexity concepts and details that underlie their work. Effective use is made of earlier results from the 40 references cited. Researchers with interests in algorithm analysis and computation complexity in a graph-theoretic setting should find the presentation and results here worth reading and studying.