You are here
Search results
(1  1 of 1)
 Title
 Distance Preserving Graphs
 Creator
 Zahedi, Emad
 Date
 2017
 Collection
 Electronic Theses & Dissertations
 Description

The computational complexity of exploring distance properties of large graphs such as realworld social networks which consist of millions of nodes is extremely expensive. Recomputing distances in subgraphs of the original graph will add to the cost. One way to avoid this is to use subgraphs where the distance between any pair of vertices is the same as in the original graph. Such a subgraph is called {\em isometric}. A connected graph is {\em distance preserving}, for which we use the...
Show moreThe computational complexity of exploring distance properties of large graphs such as realworld social networks which consist of millions of nodes is extremely expensive. Recomputing distances in subgraphs of the original graph will add to the cost. One way to avoid this is to use subgraphs where the distance between any pair of vertices is the same as in the original graph. Such a subgraph is called {\em isometric}. A connected graph is {\em distance preserving}, for which we use the abbreviation dp, if it has an isometric subgraph of every order. In this framework we study dp graphs from both the structural and algorithmic perspectives. First, we study the structural nature of dp graphs. This involves classifying graphs based on the dp property and the relation between dp graphs to other graph classes. Second, we study the recognition problem of dp graphs. We intend to develop efficient algorithms for finding isometric subgraphs as well as deciding whether a graph is dp or not.
Show less