Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(2)
Bipartite Graph
Connected Graph
Related Publications
(5)
On the Editing Distance Between Unordered Labeled Trees
A New Algorithm for ErrorTolerant Subgraph Isomorphism Detection
IPR: Automated Interaction Process Reconciliation
StructureBased Similarity Search with Graph Histograms
Distances between graphs under edge operations
Subscribe
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
Edit
Graph similarity and distance in graphs
(
Citations: 29
)
BibTex

RIS

RefWorks
Download
Gary Chartrand
,
Grzegorz Kubicki
,
Michelle Schultz
Summary. For connected graphs G1 and G2 of order n and a onetoone 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 onetoone 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. 129145, 1998
DOI:
10.1007/s000100050025
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.
(
www.springerlink.com
)
(
www.springerlink.com
)
(
www.springerlink.com
)
(
www.springerlink.com
)
More »
Citation Context
(19)
...An example similarity measure based on edit distance has been proposed in [
22
] addressing graph isomorphism, while [23] addresses subgraph isomorphism...
Andreas Wombacher
,
et 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 Bianchin
,
et 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. Iacob
,
et 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 Jiang
,
et 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 Chung
,
et al.
Biological Pathway Extension Using Microarray Gene Expression Data
References
(6)
Average distance in graphs with removed elements
(
Citations: 7
)
D. Bienstock
,
E. Györi
Journal:
Journal of Graph Theory  JGT
, vol. 12, no. 3, pp. 375390, 1988
Distances between graphs under edge operations
(
Citations: 15
)
Wayne Goddard
,
Henda C. Swart
Journal:
Discrete Mathematics  DM
, vol. 161, no. 13, pp. 121132, 1996
Existence of graphs with prescribed mean distance
(
Citations: 3
)
G. R. T. Hendry
Journal:
Journal of Graph Theory  JGT
, vol. 10, no. 2, pp. 173175, 1986
The Wiener polynomial of a graph
(
Citations: 12
)
Bruce E. Sagan
,
YeongNan Yeh
,
Ping Zhang
Published in 1998.
Structural determination of para n boiling points
(
Citations: 385
)
H. Wiener
Sort by:
Citations
(29)
Alternative Approaches for Workflow Similarity
(
Citations: 1
)
Andreas Wombacher
,
Chen Li
Conference:
IEEE International Conference on Services Computing  IEEESCC
, pp. 337345, 2010
RADAR: A reputationdriven anomaly detection system for wireless mesh networks
Zonghua Zhang
,
PinHan Ho
,
Farid NaïtAbdesselam
Journal:
Wireless Networks  WINET
, vol. 16, no. 8, pp. 22212236, 2010
Similarity metric for risk assessment in IT change plans
Luís Armando Bianchin
,
Juliano Araujo Wickboldt
,
Lisandro Zambenedetti Granville
,
Luciano Paschoal Gaspary
,
Claudio Bartolini
,
Maher Rahmouni
Conference:
2010 International Conference on Network and Service Management  CNSM
, pp. 2532, 2010
RADAR: A ReputAtionBased Scheme for Detecting Anomalous Nodes in WiReless Mesh Networks
(
Citations: 8
)
Zonghua Zhang
,
Farid Naïtabdesselam
,
Pinhan Ho
,
Xiaodong Lin
Conference:
Wireless Communications and Networking, IEEE Conference  WCNC
, pp. 26212626, 2008
Optimized dynamic semantic composition of services
(
Citations: 2
)
Sorin M. Iacob
,
João Paulo A. Almeida
,
Mariaeugenia Iacob
Conference:
ACM Symposium on Applied Computing  SAC
, pp. 22862292, 2008