Reconstruction of graphs based on random walks

DOI10.1016/j.tcs.2009.05.026zbMath1173.05033OpenAlexW2024311094WikidataQ59682403 ScholiaQ59682403MaRDI QIDQ837176

Fabian J. Theis, Dominik M. Wittmann, Daniel Schmidl, Florian Blöchl

Publication date: 10 September 2009

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2009.05.026

zbMATH Keywords

graph theoryrandom walkdistance realization problemmean first hitting time

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Paths and cycles (05C38) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Distance in graphs (05C12) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (4)

Stochastic forms of non-negative matrices and Perron-regularity ⋮ Resistance distance distribution in large sparse random graphs ⋮ Commute times of random walks on trees ⋮ On the Adjacency-Jacobsthal numbers

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Random walks and the effective resistance of networks
• Conditionally positive functions and p-norm distance matrices
• A constructive algorithm for realizing a distance matrix
• An algorithm and its role in the study of optimal graph realizations of distance matrices
• Matrix multiplication via arithmetic progressions
• Trees, tight extensions of metric spaces, and the cohomological dimension of certain groups: A note on combinatorial properties of metric spaces
• On optimal realizations of finite metric spaces by graphs
• A fast algorithm for constructing trees from distance matrices
• Submatrices of non-tree-realizable distance matrices
• Free trees and bidirectional trees as representations of psychological distance
• On the use of an inverse shortest paths algorithm for recovering linearly correlated costs
• Distance realization problems with applications to internet tomography
• Emergence of Scaling in Random Networks
• An Optimality Criterion for Graph Embeddings of Metrics
• The distance matrix of a graph and its tree realization
• Distance matrix of a graph and its realizability
• Collective dynamics of ‘small-world’ networks
• Properties of the distance matrix of a tree

This page was built for publication: Reconstruction of graphs based on random walks