Simulation-Based Graph SimilarityDepartmental Papers (CIS)
Date of this Version3-27-2006
Document TypeConference Paper
AbstractWe present symmetric and asymmetric similarity measures for labeled directed rooted graphs that are inspired by the simulation and bisimulation relations on labeled transition systems. Computation of the similarity measures has close connections to discounted Markov decision processes in the asymmetric case and to perfect-information stochastic games in the symmetric case. For the symmetric case, we also give a polynomial-time algorithm that approximates the similarity to any desired precision.
Citation InformationOleg Sokolsky, Sampath Kannan and Insup Lee. "Simulation-Based Graph Similarity" (2006)
Available at: http://works.bepress.com/sokolsky/33/