Academic
Publications
Graph similarity and distance in graphs

Graph similarity and distance in graphs,10.1007/s000100050025,Aequationes Mathematicae,Gary Chartrand,Grzegorz Kubicki,Michelle Schultz

Graph similarity and distance in graphs   (Citations: 29)
BibTex | RIS | RefWorks Download
Summary. For connected graphs G1 and G2 of order n and a one-to-one mapping : V (G1)! V (G2), the -distance between G1 and G2 is d(G1;G 2 )= X dG 1 (u;v) dG2 (u;v) ; where the sum is taken over all n 2 unordered pairs u;v of vertices of G1. The distance between G1 and G2 is dened by d(G1;G 2) = minfd(G1;G 2 )g, where the minimum is taken over all oneto-one mappings from V (G1 )t o V ( G 2). It is shown that this distance is a metric on the space of connected graphs of a xed order. The maximum distance D(G1;G 2) = maxfd(G1;G 2 )g for connected graphs G1 and G2 of the same order is also explored. The total distance of a connected graph G is d(u;v), where the sum is taken over all unordered pairs u, v of vertices of G. Bounds for d(G1;G 2) are presented both in terms of the total distances of G1 and G2 and also in terms of the sizes of G1, G2, and a greatest common subgraph of G1 and G2 .F or a set S of connected graphs having xed order, the distance graphD(S )o fSis that graph whose vertex set isS and such that two vertices G 1 and G2 ofD(S) are adjacent if and only if d(G1;G 2 )=1 . Furthermore, a graph G is a distance graph if there exists a setS of graphs having xed order such thatD(S) =G. It is shown that every distance graph is bipartite and, moreover, that all even cycles and all forests are distance graphs. Other bipartite graphs are shown to be distance graphs and it is conjectured that all bipartite graphs are distance graphs.
Journal: Aequationes Mathematicae , vol. 55, no. 1, pp. 129-145, 1998
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
    • ...An example similarity measure based on edit distance has been proposed in [22] addressing graph isomorphism, while [23] addresses subgraph isomorphism...

    Andreas Wombacheret al. Alternative Approaches for Workflow Similarity

    • ...As an attempt to determine the similarity between change workflows, these workflows could be modeled as directed graphs and then have their similarity computed by solutions already employed in general graphs, as in Chartrand et al. [7]...

    Luís Armando Bianchinet al. Similarity metric for risk assessment in IT change plans

    • ...In principle, such a similarity measure can be used in the SCS as well, and other graph similarity measures proposed in the literature (e.g., [6]) are also suitable...

    Sorin M. Iacobet al. Optimized dynamic semantic composition of services

    • ...In [21] Chartrand et al. describe an approach for graph distance calculation based on preserving the distance between nodes...
    • ...Given a graph g =( V, E), the distance between two nodes x, y ∈ V , denoted dg(x, y), is defined as the minimum number of edges that need to be traversed when traveling from x to y [21]...
    • ...Further, the φ-distance [21] between two graphs g1 an g2, denoted dφ(g1 ,g 2), is defined as dφ(g1 ,g 2 )= �...
    • ...In [21] the authors also go on to show that we can make some other, less expensive calculations if the graphs meet certain requirements...
    • ...Further theoretical contributions related to this approach can be found in [21]...

    Xiaoyi Jianget al. Graph Matching

    • ...The geodesic distance d (g, h; G ) between nodes g and h is defied by the length of shortest path from g to h in the graph G. This distance represents the global structure of graph (Chartrand et al., 1988)...
    • ...We here note that it is symmetric and satisfies triangle inequality (Chartrand et al., 1988)...

    Tae Su Chunget al. Biological Pathway Extension Using Microarray Gene Expression Data

Sort by: